[ 개념 ] 02. 이진트리에 관하여

> 이진트리

1. 후위 순회(postorder)

이진 트리(binary tree)의 후위 순회 알고리즘이 사용될 수 있는 대표적인 예는 특정 디렉토리(directory)의 용량 계산이다. 단, 이진 트리이기 때문에 특정 디렉토리(=폴더)의 서브 디렉토리의 개수는 2개 이하로만 존재해야 한다. 삼진 트리(ternary tree)였다면 서브 디렉토리는 총 3개까지 존재할 수 있다.

1.1 디렉토리의 용량 계산

디렉토리의 용량 계산을 위해서는 어떤 알고리즘이 사용되야하는가를 먼저 고민해보자. 생각을 할 때 구체적인 상황을 두고 예시를 들어보면 이해가 빠르다. 현재 사용하는 컴퓨터에 datastructure 라는 디렉토리가 있다고 가정해보자. 이 datastructure 디렉토리 내부에는 stack, queue 라는 서브 디렉토리가 존재한다.

• datastructure/stack
• datastructure/queue 이 때 datastructure 디렉토리의 크기를 구하려면 어떻게 해야할까?

서브 디렉토리인 stack 디렉토리와 queue 디렉토리의 크기를 각 계산하여 합하면 datastructure 폴더의 크기를 계산할 수 있다. 서브 디렉토리의 크기를 더해 현재 디렉토리의 크기를 계산한다는 아이디어를 생각해보면 서브 디렉토리의 크기를 먼저 계산하는데, 바로 이러한 특징 때문에 후위 순회 알고리즘을 사용해야 한다.

1.2 코드

후위 순회: 트리를 탐색할 때 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문하는 순회 알고리즘을 일컫는 말이다. 후위 순회 알고리즘은 아래와 같다.

// 후위 순회 알고리즘
void postorder(TreeNode *root){
    if(root){
        postorder(root->left);        // 왼쪽 서브 트리를 가장 먼저 순회
        postorder(root->right);        // 다음으로 오른쪽 서브 트리를 순회
        printf("%d", root->data);    // 마지막으로 루트의 노드를 방문
    }
}

위와 같은 후위 순회를 사용하여 디렉토리 크기를 계산하는 코드를 작성해보도록 한다. 순환 호출되는 함수가 용량을 반환하도록 만들어줘야 한다.

// 디렉토리 용량 계산 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

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

int calc_dir_size(TreeNode *root);

// 아래와 같은 트리 구조를 생성한다.
//                n1
//            n3        n2
//        n4        n5
int main(){
    TreeNode n4 = { 500, NULL, NULL };
    TreeNode n5 = { 200, NULL, NULL };
    TreeNode n3 = { 100, &n4, &n5 };
    TreeNode n2 = { 50, NULL, NULL };
    TreeNode n1 = { 0, &n2, & n3 };

    printf("디렉토리의 크기 = %d\n", calc_dir_size(&n1));
}

int calc_dir_size(TreeNode *root){
    if(!root) return 0;        // 존재하지 않는 노드일 경우
    else{
        int left = calc_dir_size(root->left);        // 왼쪽 서브트리를 먼저 순회한다
        int right = calc_dir_size(root->right);        // 오른쪽 서브트리를 그 다음으로 순회한다.
        return left + right + root->data;            // 순회한 노드에 해당하는 데이터를 계속해서 더해간다.
    }
    return 0;
}

2. 이진트리의 높이 구하기

트리의 높이를 구할 때의 핵심 개념은 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이를 비교하여 더 큰 쪽을 택한다는 것이다. 그렇다면 우리에게 필요한 건 서브트리의 높이와 오른쪽 서브트리의 높이다. 높이는 어떻게 구할 수 있을까?

2.1 코드

typedef struct TreeNode{
    int data;
    struct TreeNode *left, *right;
} TreeNode;
int get_height(TreeNode *root);
// 아래와 같은 트리 구조를 생성한다.
//      n1
//    n3    n2
//  n4    n5
void main(){
    TreeNode n4 = { 500, NULL, NULL };
    TreeNode n5 = { 200, NULL, NULL };
    TreeNode n3 = { 100, &n4, &n5 };
    TreeNode n2 = { 50, NULL, NULL };
    TreeNode n1 = { 0, &n2, &n3 };

    printf("디렉토리의 크기 = %d\n", calc_dir_size(&n1));
}

int get_height(TreeNode *root){        // 트리의 높이를 구한다
    if(!root) return 0;
    else{
        int left_h = get_height(root->left);        // 왼쪽 서브트리의 높이를 순환호출을 통해 얻는다.
        int right_h = get_height(root->right);        // 같은 방법으로 오른쪽 서브트리의 높이를 얻는다.
        return 1 = (left_h > right_h ? left_h : right_h);        // 둘 중 큰 값에 1을 더해 반환한다.
    }
}

위 코드를 이해해보자. 순환 알고리즘이 적용된 코드를 작성하거나 읽을 때는 탈출 조건 보다는 순환호출 되는 부분을 먼저 살펴봐야 한다. 호출되는 부분은 int left_h = get_height(root->left), int right_h = get_height(root->right) 이 두 부분이다.

위 순환 호출되는 코드로 왼쪽 서브트리의 높이 left_h와 오른쪽 서브트리의 높이 right_h를 구하기 위해 순환 함수로 각 서브트리의 끝(단말 노드)까지 방문할 수 있다. 방문 순서는 get_height(root->left가 먼저 호출되었으므로 먼저 왼쪽 서브트리의 단말노드까지 방문할 것이고 탈출 조건 if (!root)를 만나면서 왼쪽 서브트리를 빠져나오면 오른쪽 서브트리로 진입한다(get_height(root->right).

다음으로 탈출되는 조건을 살펴보자. 위 코드에서 상정한 탈출 조건은 단말노드를 만났을 때다. 단말노드란 자식이 없는 노드를 뜻한다. 그렇다면 단말노드인 것은 어떻게 알 수 있을까?

자식이 없는 노드가 단말노드이므로 아래와 같은 두 조건을 생각해볼 수 있다.

/**
* if (root->left == NULL && root->right == NULL) // 왼쪽 서브트리와 오른쪽 서브트리가 없을 때
* if (root == NULL) or if (!root)    // 방문을 했는데 존재하지 않는 노드였을 경우
*/

root == NULL의 의미를 좀 더 풀어서 설명하자면 자식 노드가 있나 살펴보려 서브 트리를 방문했는데 아무것도 발견할 수 없었다라는 의미다. 위 코드는 이 조건을 적용한 코드다.

마지막으로 ger_height함수에서 맨 아래 리턴하는 부분을 살펴보자. 왜 1을 더해서 리턴해주는 걸까?라는 의문이 든다면 그 이전에 어떤 작업을 시행했는지를 살펴보자. 특히 첫번째 완전한 순환이 끝났을 때를 생각해보자. 순환을 계속하면서 각 서브 트리의 끝까지 방문한 상태(정확히는 오른쪽 서브트리를 끝까지 방문한 상태)에서 한 단계 더 내려가 root == NULL이라는 탈출 조건을 만났다. 그렇게 탈출 조건을 만나 빠져나오면 마지막 리턴문을 만나게 되는데 이때의 상황은 더 이상의 자식노드, 서브트리가 없는 상황이므로 리턴문에 있는 left_h와 right_h는 둘 다 0이 될 것이다.

위 상황에 대한 결론을 내려보면 나에게 자식노드, 서브트리는 존재하지 않지만 적어도 나는 존재한다는 것을 입증했다는 것이다. 따라서 나 자신을 하나의 개수로 칠 수 있다. 그래서 1을 더하는 것이다. 1을 더한 후에는 왼쪽 서브트리와 오른쪽 서브트리의 높이 중 더 큰 값을 택하기만 하면 되는 것이다.

순환의 개념을 접할 때는 추상적으로 이해하면 이해에 좀 더 도움이 된다. 큼지막한 매커니즘, 예를 들어 왼쪽 서브트리 높이 구하기, 오른쪽 서브트리 높이 구하기들이 대략 어떤 순서로 실행되는지를 파악하고 리턴은 언제 되고 탈출 조건은 어떻게 되는지를 살펴보는 것이다. 실행 흐름을 하나 하나 다 따지려 하기보다는 먼저 이렇게 개념적으로 접근한 후에 세부적으로 이해하려고 하면 좀 더 편하다.

3. 이진트리의 단말 노드 개수 구하기

2번에서 살펴본 알고리즘을 그대로 적용하면 의외로 쉽게 구할 수 있다. 아래의 코드만 보고 개념을 이해하도록 해보자.

3.1 코드

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

int get_leaf(TreeNode *root);
// 아래와 같은 트리 구조를 생성한다.
//      n1
//    n3    n2
//  n4    n5

void main(){
    TreeNode n4 = { 500, NULL, NULL };
    TreeNode n5 = { 200, NULL, NULL };
    TreeNode n3 = { 100, &n4, &n5 };
    TreeNode n2 = { 50, NULL, NULL };
    TreeNode n1 = { 0, &n2, &n3 };

    printf("단말 노드의 갯수 = %d\n", get_leaf(&n1));
}

int get_leaf(TreeNode *root){        // 트리에 존재하는 단말노드의 갯수를 구한다.
    if(!root) return 0;
    if(root->left == NULL & root->right == NULL) return 1;
    else return get_leaf(root->left) + get_leaf(root->right);
}

위 코드의 탈출 조건은 if (root->left == NULL && root->right == NULL)다. 즉 자식노드 혹은 서브트리가 존재하지 않을 때가 탈출 조건이다. 의미는 자식 노드는 존재하지 않지만 내가 존재한다는 건 적어도 증명했으니 난 1개로 셀 수 있다는 것이다. 첫번째 if (!root)의 조건은 누군가 이 함수를 사용할 때 존재하지 않는 노드를 매개변수로 넘겼을 때를 대비하기 위함이다 .오류를 방지하는 용도로서의 의미를 가진 조건이다. 이 조건을 탈출 조건으로 쓸 수 없는 것은 이 조건 만으로는 단말 노드의 여부를 증명할 수 없기 때문이다. 아무것도 존재하지 않으므로 개수를 셀 수 없다.