[Data Structure] 이진 트리 연산 (노드, 높이)

노드의 개수

1. 트리안의 노드들을 전체적으로 순회 (함수 순환 호출)

2. 노드에 대한 각 서브트리들을 계속 순환 호출 (노드 != NULL)

3. 반환되는 값(왼쪽 서브트리, 오른쪽 서브트리 순회하면서 얻은 노드 개수)에 1을 더하기

• 더하기 1 : 자기 자신의 개수를 포함해야 하기 때문

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;
}

 

 

단말 노드의 개수

1. 트리안의 노드들을 전체적으로 순회 (함수 순환 호출)

2. 순회하면서 해당 노드의 왼쪽자식 = 오른쪽자식 = NULL 이면, 해당 노드가 단말노드이므로 1 반환 

int get_leaf_count(treenode* node) {
	int count = 0;
	if (node != NULL) {
		if (node->left == NULL && node->right == NULL) // 왼쪽, 오른쪽자식 모두 NULL이면 단말노드
			return 1;
		else
			count = get_leaf_count(node->left) + get_leaf_count(node->right);
	}
	return count;
}

 

 

높이 계산

1. 왼쪽 서브트리의 높이 h1, 오른쪽 서브트리의 높이 h2를 함수 순환호출을 통해 구하기

2. h1, h2 중 max값을 선택해서 최상위 노드 자기자신의 높이 1을 더하기

#define max(a, b) ((a<b)?b:a)

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

 

 

※ Example

---