[자료 구조] Binary tree

March 21, 2023

이진 트리

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 자료 구조입니다.

각 노드는 부모 노드와 두 개의 자식 노드로 구성되어 있습니다.

이진 트리

최대 2개의 자식 노드를 가질 수 있음, 자식 노드를 표현하기 위해서 보통 포인터로 구현

이진 트리는 자식이 최대 2개이므로 다양한 형태로 존재할 수 있습니다. 그중 특수한 이진 트리들을 살펴 보겠습니다.

binary-trees

다양한 이진 트리

https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

Full

Complete

Degenerate

Perfect

Balanced

구현

노드 구조

typedef struct tnode {
    int data;
    struct tnode *left_child, *right_child;
} tnode;

순회 함수들

각각의 순회함수들은 재귀로 구현이 되어 있습니다. 각 특성에 맞게 data를 언제 방문하냐에 따라 3가지로 나눌 수 있습니다.

// 중위 순회: 왼쪽 자식 -> 자신 -> 오른쪽 자식
void inorder(tnode *ptr) {
    if (ptr) {
        inorder(ptr->left_child);
        printf("%c ", ptr->data);
        inorder(ptr->right_child);
    }
}

// 전위 순회: 전위 -> 왼쪽 자식 -> 오른쪽 자식
void preorder(tnode *ptr) {
    if (ptr) {
        printf("%c ", ptr->data);
        preorder(ptr->left_child);
        preorder(ptr->right_child);
    }
}

// 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 자신
void postorder(tnode *ptr) {
    if (ptr) {
        preorder(ptr->left_child);
        preorder(ptr->right_child);
        printf("%c ", ptr->data);
    }
}

중위와 전위로 후위 출력

어느 이진트리에 대해서, inorder와 preorder가 주어진다면 postorder를 출력할 수 있습니다.

inorder - 왼쪽/오른쪽 자식을 구분
preorder - 부모/자식을 구분

int search(char arr[], char x, int n) {
    for (int i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}

// inporder와 preorder로부터 post order 출력
void printPostOrder(char in[], char pre[], int n) {
    // The first element in pre[] is always root, search it
    // in in[] to find left and right subtrees
    int root = search(in, pre[0], n);

    // If left subtree is not empty, print left subtree
    if (root != 0)
        printPostOrder(in, pre + 1, root);

    // If right subtree is not empty, print right subtree
    if (root != n - 1)
        printPostOrder(in + root + 1, pre + root + 1, n - root - 1);

    // Print root
    printf("%c ", pre[0]);
}

root 인덱스가 inorder에서 몇 번째 인덱스인지 확인합니다. inorder에서 root는 전체 이진 트리를 반으로 나누는 기준이 됩니다.

크게 4단계로 나눌 수 있습니다.

printPostOrder 함수는 세 개의 매개변수를 받습니다
- in (inorder 배열), pre (preorder 배열), n (배열의 길이)
search 함수를 호출하여 현재 subtree의 루트가 inorder 배열에서 몇 번째에 위치하는지를 찾아냅니다. 이 인덱스를 root 변수에 저장합니다.
preorder의 맨 앞은 루트입니다. 그러므로 루트를 기준으로 왼쪽 자식트리와 오른쪽 자식 트리를 처리할 수 있습니다.
- 왼쪽 자식 트리가 존재하는 경우:
  
  printPostOrder 함수를 재귀적으로 호출하여 왼쪽 자식 트리를 처리합니다.
  
  이때, preorder 배열의 시작 위치는 현재 루트의 다음 위치이며, 길이는 현재 루트의 인덱스(root)까지 입니다.
- 오른쪽 자식 트리가 존재하는 경우:
  
  printPostOrder 함수를 재귀적으로 호출하여 오른쪽 자식 트리를 처리합니다.
  
  이때, inorder 배열에서 현재 루트 다음 위치부터, preorder 배열에서 현재 루트의 다음 위치부터, 길이는 전체 길이에서 현재 루트의 인덱스(root)와 왼쪽 서브트리의 길이를 뺀 값입니다.
후위 순회이기 때문에 현재 루트를 제일 마지막으로 출력합니다. 루트는 현재 preorder 배열의 맨 앞에 위치합니다.

실행

int main() {
    char input_inorder[] = {'4', '1', '6', '3', '2', '5'};
    char input_preorder[] = {'1', '4', '2', '3', '6', '5'};

    int n = sizeof(input_inorder) / sizeof(inorder1[0]);
    printPostOrder(input_inorder, input_preorder, n);

    return 0;
}

결과

4, 2, 5, 1, 3, 6    in order
1, 2, 4, 5, 3, 6    pre order
4 5 2 6 3 1         post order

b-post-result

참고

https://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/