이진 트리의 연산(노드개수+단말노드개수+높이)

트리를 이용한 순회기법들을 알아봤고 그 외에 더 몇가지 살펴볼만한 트리의 연산 몇가지를 구현해보았습니다.

노드의갯수+ 단말노드의갯수+ 트리의 높이를 구하는 3가지 연산인데, 각 연산이 순환 호출이 주된 연산이므로

코드를 잘 살펴보고 이해해야합니다. 각 연산의 핵심 키워드는 아래와 같습니다.

1. 노드의 갯수

각 노드를 전체적으로 순회하여 각 서브트리에 대해 순환호출 한 뒤 반환되는 값에 1을 더하여 반환합니다.

(반환된 서브트리의 갯수와 루트노드의 갯수1을 더한값을 반환해야합니다.) 

2. 단말 노드의 갯수

역시 각 노드를 전체적으로 순회하면서 만약 왼쪽, 오른쪽 자식이 동시에 0이면 단말노드이므로 1을 반환합니다.

그렇지않으면 더 깊게 내려가 서브트리에 대해 순환 호출하여 단말노드를 탐색합니다.

*3. 트리의 높이

전체 순회하되 1,2처럼 반환된 값을 단순히 더하는게 아니라 서브트리에서 반환된 서브트리의 높이 중  최댓값을 구하여 반환합니다.

1,2 번에 비해 약간 까다로운 편인데 노드의 갯수가 작은 경우를 직접그려서 이해해보면 쉽게 이해할 수 있습니다.

주의: 매크로함수 정의 시 괄호를 잘 설정해야합니다.(괄호 설정 오류 시 높이 0출력)

수식 사이에는 괄호를 하나씩 더 쳐주는게 좋습니다. 

계산할 수식트리는 아래와 같습니다.

코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a,b) (((a)>(b))?(a):(b))//괄호를 무조건 둘러싸자
 
//#define max(a,b) (((a)>(b))?(a):(b)) => 오류발생 
typedef struct treeNode
{
    int  data;
    struct treeNode* left, * right;
}treeNode;
 
treeNode n1 = { 0,NULL,NULL };
treeNode n2 = { 1,NULL,NULL };
treeNode n3 = { 3,&n1,&n2 };
treeNode n4 = { 2,NULL,NULL };
treeNode n5 = { 4,&n3,&n4 };
treeNode* root = &n5;
int calc_node_count(treeNode* root)
{
    int cnt = 0;
    if (root != NULL)
    {
        cnt = 1 + calc_node_count(root->left) + calc_node_count(root->right);
    }
    return cnt;
}
int calc_leaf_count(treeNode* root)
{
    int cnt = 0;
    if (root != NULL)
    {
        if (root->left == NULL && root->right == NULL)//단말 노드이면
        {
            return 1;
        }
        else
        {
            cnt = calc_leaf_count(root->left) + calc_leaf_count(root->right);
        }
    }
    return cnt;
}
int calc_height(treeNode* root)
{
    int height = 0;
    if (root != NULL)
    {
        height = 1 + max(calc_height(root->left), calc_height(root->right));
    }
    return height;
}
int main()
{
    printf("트리의 전체노드 갯수는 %d개입니다.\n",calc_node_count(root));
    printf("트리의 단말노드 갯수는 %d개입니다.\n",calc_leaf_count(root));
    printf("트리의 높이는 %d입니다.\n", calc_height(root));
}

결과