트리 - 이진 트리의 노드 개수/ 단말 노드 개수/ 높이 구하기

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다.

 

// 해당 단원인 '트리'의 목차가 업데이트 될 예정입니다.

이전글: 수식트리(후위표기수식)

 

이진트리의 노드 개수 구하기

이진트리에서 전체 노드의 개수를 세기 위해서는 모든 노드들을 한 번씩 방문해야 한다. 즉, 노드의 개수를 셀 때도 순회 알고리즘이 사용된다. 그렇다면, 어떤 순회 알고리즘을 사용하는 것이 가장 적합할까?

어떤 노드를 루트로 하는 이진트리의 노드의 개수는, 왼쪽 서브트리의 노드 개수와 오른쪽 서브트리의 노드 개수에 루트 노드의 수 1 을 더해주면 된다. 즉 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 노드 순으로 방문하여 셈하는 알고리즘은 후위순회임을 알 수 있다.

 

이를 pseudo-code로 표현하면 다음과 같다.

// Pseudo Code
get_node_count(root):
	if root != NULL 
		return 1 + get_node_count(root.left) + get_node_count(root.right)

이를 c언어로 구현하면 다음과 같다.

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으로 초기화된다는 점이다. 

---

이진트리의 단말 노드 개수 구하기

단말 노드는 트리의 말단 노드이다. 단말 노드 개수를 세기 위해서는 트리 안의 노드들을 전체적으로 순회해야 한다. 순회하면서 왼쪽 자식과 오른쪽 자식이 동시에 없으면 단말노드이므로 셈한다. 만약 그렇지 않으면 비단말 노드이므로 각각의 서브 트리에 대해 순환 호출하여 자식노드의 유무를 검사한다. 

이를 알고리즘으로 표현하면 다음과 같다. 

// Pseudo Code
get_leaf_count(root):
	if root != NULL
		if root.left == NULL and root.right == NULL
			return 1
		else
			return get_leaf_count(root.left) + get_leaf_count(root.right)

이를 c언어로 구현하면 다음과 같다. 단, 아래의 코드를 이해할 때 주의해야 할 점은 함수를 호출할 때마다 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_leaf_count(node->left) + get_leaf_count(node->right)
	return count;
}

이 경우에 대한 함수 호출 과정을 표현한 그림은 생략한다.

---

이진트리의 높이 구하기

이진트리의 높이는 '최대 레벨' 또는 '최대 깊이'로 해석할 수 있다. 이 중에서 '최대 레벨'로 설명을 이어본다. 

이진트리의 높이를 계산하기 위해서는 왼쪽 서브트리의 레벨과 오른쪽 서브트리의 레벨을 비교해 구한 MAXIMUM 값에 1을 더한다. 이를 알고리즘으로 표현하면 다음과 같다.

// Pseudo Code
get_height(root):
	if root != NULL
		return 1 + MAX(get_height(root.left), get_height(root.right))

이를 c언어로 구현하면 다음과 같다.

int get_height(TreeNode* root)
{
	int height = 0;
	if (root != NULL){
		height = 1 + max(get_height(root.left), get_height(root.right));
	}
	return height;
}

위의 코드가 어떻게 흘러가는지 아래의 그림으로 이해해할 수 있다.