[트리] 이진트리의 연산 (C언어)

[트리] 이진트리의 연산 (C언어)

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

다양한 연산들이 있다.

이번 포스팅에서는

트리의 전체 노드 개수 세기

단말 노드의 개수 구하기

트리의 높이 구하기

를 알아보고자 한다.

p.276 Quiz

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

트리를 보면 알 수 있듯이

전체 노드는 7개이다.

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

트리의 높이는 4이다.

#include #include 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

", get_node_count(root)); printf("단말 노드의 개수 : %d

", get_leaf_count(root)); printf("트리의 높이 : %d

", get_height(root)); }

출력 결과

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

from http://sxyzn.tistory.com/18 by ccl(A) rewrite - 2021-08-17 23:26:15