[C] 트리 : 이진트리의 연산

앞에서 본 이진트리는 순회하는 것 말고도

다양한 연산들이 있다.

 

이번 포스팅에서는

• 트리의 전체 노드 개수 세기
• 단말 노드의 개수 구하기
• 트리의 높이 구하기

를 알아보고자 한다.

 

p.276 Quiz

앞에서 사용한 이 트리를 이용해보자

 

트리를 보면 알 수 있듯이

전체 노드는 7개이다.

단말 노드는 3개이다. (22 35 95)

트리의 높이는 4이다.

 

#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode {
	struct TreeNode* left;
	int data;
	struct TreeNode* right;
}TreeNode;

TreeNode n7 = { NULL,22,NULL };
TreeNode n6 = { NULL,95,NULL };
TreeNode n5 = { &n7,35,NULL };
TreeNode n4 = { NULL,5,NULL };
TreeNode n3 = { &n5,93,&n6 };
TreeNode n2 = { &n4,15,NULL };
TreeNode n1 = { &n2,17,&n3 };
TreeNode* root = &n1;

int get_node_count(TreeNode* root) {
	int count = 0;
	if (root != NULL)
		//재귀함수 이용, 해당 노드를 카운트하기 위해 1을 더하고 왼-오른쪽 노드 카운트
		count = 1 + get_node_count(root->left) + get_node_count(root->right);
		return count;
}

int get_leaf_count(TreeNode* root) {
	int count = 0;
	if (root != NULL) {
		//단말 노드인 경우 count값을 1 증가시켜주기 위해 return 1
		if (root->left == NULL && root->right == NULL) return 1;
		else count = get_leaf_count(root->left) + get_leaf_count(root->right);
	}
	return count;
}

int get_height(TreeNode* root) {
	int height = 0;
	if (root != NULL)
		//왼쪽 노드와 오른쪽 노드를 탐색해보면서 최대 레벨 구하기
		//단말노드가 나올 때 까지 카운트 (+1)
		height = 1 + max(get_height(root->left), get_height(root->right));
	return height;
}

int main() {
	printf("트리의 전체 노드의 개수 : %d\n", get_node_count(root));
	printf("단말 노드의 개수 : %d\n", get_leaf_count(root));
	printf("트리의 높이 : %d\n", get_height(root));
}

 

출력 결과

 

 

[참고자료] C언어로 쉽게 풀어 쓴 자료구조, 생능출판, 천인국 공용해 하상호 지음