[Data Structure] 이진 트리 노드 개수 세기 (Counting TreeNode)

 요즘 들어서 하는 일이 많아져서 조금씩 밖에 못하고 있다. 이정도는 금방하고 넘어가야 하는데 조금 게을러졌다. 여튼 잡설은 여기까지 하고 ..

 이번에 볼 내용은 이진 트리에서 노드의 개수를 세는 방법이다. 어차피 현재 재귀 형식을 사용하기 때문에 직관적이고 쉽다. 또한 두번째로 단말 노드를 세는 메서드가 추가되어 있다. 단말 노드는 알다시피 자식 노드가 없는 마지막 노드를 의미한다.

 코드를 보자.

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

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

// 노드 개수 세는 메서드
int get_node_count(TreeNode *root){
    if (root == NULL) return 0;
    int result = 1;
    result += get_node_count((TreeNode*)root->left) + get_node_count((TreeNode*)root->right);
    return result;
} 

// 단말 노드 개수 세는 메서드
int get_leaf_count(TreeNode *root){
    int result = 0;
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL){
        return 1;
    }
    result += get_leaf_count((TreeNode*)root->left) + get_leaf_count((TreeNode*)root->right);
    return result;
} 

int main(){
    TreeNode n6 = {300,NULL,NULL};
    TreeNode n5 = {500,NULL,NULL};
    TreeNode n4 = {200,&n6 ,NULL};
    TreeNode n3 = {100,&n4 ,&n5 };
    TreeNode n2 = {50 ,NULL,NULL};
    TreeNode n1 = {0  ,&n2 ,&n3 };
    printf("전체 노드의 수 : %d\n",get_node_count(&n1));
    printf("자식 노드가 없는 노드의 수 : %d\n",get_leaf_count(&n1));
    return 0;
}