[자료구조] 이진 트리의 노드, 단말 노드 개수, 높이 구하기 연산

 

전체 노드의 개수

 

루트 노드 + 왼쪽 서브 트리의 노드들 + 오른쪽 서브 트리의 노드들

 

// 전체 노드의 개수 (루트 노드 + 왼쪽 서브 트리 + 오른쪽 서브트리)
int get_node_count(TreeNode* node) {
	int count = 0;

	if (node != NULL)
		count = 1 + get_node_count(node->left) + get_node_count(node->right);

	return count;
}

 

 

단말 노드의 개수

 

노드의 왼쪽/오른쪽 서브 노드가 없는 경우 count값 증가

 

// 단말 노드 개수 (왼쪽/오른쪽 자식이 동시에 0인 경우)
int get_leaf_count(TreeNode* node) {
	int count = 0;

	if (node != NULL)
		if (node->left == NULL && node->right == NULL)
			return 1;
		else
			count = get_node_leaf(node->left) + get_node_leaf(node->right);

	return count;
}

 

 

트리의 높이

 

루트 노드 + 왼쪽 서브 트리와 오른쪽 서브 트리의 노드 중 큰 값 반환

// 트리 높이 구하기 (왼쪽 서브트리, 오른쪽 서브트리 중 더 높은 값)
int get_height(TreeNode* node) {
	int height = 0;

	if (node != NULL)
		height = 1 + max(get_height(node->left), get_height(node->right));
	return height;
}