[5639] 이진 검색 트리

문제 링크 : https://www.acmicpc.net/problem/5639

5639 - 이진 검색 트리

본문

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 $10^6$보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 $10000$개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

일단 입력으로 주어지는 숫자는 몇 개가 입력되는지 모른다. 입력이 들어오는 만큼 전부 사용해야하니까 EOF로 핸들링하자.

입력으로 주어지는 숫자들은 어떠한 트리의 전위 순회 순서이다. 전위 순회는 루트-왼쪽-오른쪽 순서로 순회하는 방법을 말한다. 즉, 제일 먼저 입력되는 숫자가 전체 트리의 루트 노드가 된다는 의미이다. 그리고 이진트리의 특성에 의해 루트보다 작은 값들은 왼쪽, 루트보다 큰 값들은 오른쪽에 배치될 것이다. 즉, 첫번째로 입력된 수보다 작은 수들이 왼쪽에서 서브트리를 만들 것이고, 큰 수들이 오른쪽에서 서브트리를 만들 것이다. 그럼 그 부분을 분할하여 서브트리를 만들고, 그 트리를 루트에 붙인다고 생각할 수 있다.

문제의 예제를 보고 진행해보자. 문제에서 사용된 예제는 아래와 같다.

50
30
24
5
28
45
98
52
60

이 문제에서 루트 노드는 $50$이 될 것이다. 50보다 작은 수는 30, 24, 5, 28, 45 이다. 이 수들은 50의 왼쪽에서 또 다른 서브트리를 만들게 될 것이다. 그 서브트리의 루트 노드는 30이 될 것이다.

생각해보면 수들의 범위가 계속해서 줄어들고 있지만, 현재 수들을 이용하여 트리를 만든다 라는 문제는 변하지 않는 것을 알 수 있다. 큰 문제를 작은 문제로 바꿔가며 재귀적으로 풀어간다 = 분할 정복 알고리즘을 활용하면 간단하다.

나머지는 만들게 된 트리를 후위순회하여 결과를 출력하기만 하면 된다. 후위순회는 왼쪽-오른쪽-루트 순서대로 출력하면 된다.

• 참고 알고리즘 : 분할정복

코드

사용 언어 : C

최종 수정일 : 2023 / 2 / 8

#include <stdio.h>

typedef struct Node {
    int left, right;
} ND;

#define MAX_IDX 10000
int input[MAX_IDX];
int len;

#define MAX_VAL (int)(1e6)
#define NOTEXIST -1
ND tree[MAX_VAL + 1];

int makeTree(int s, int e) {
    if (s == e) {
        return NOTEXIST;
    } else if (s + 1 == e) {
        tree[input[s]] = (ND){NOTEXIST, NOTEXIST};
        return input[s];
    }

    // current value = input[s]
    int temp = s + 1;
    while (temp < len && input[temp] < input[s]) {
        ++temp;
    }
    tree[input[s]] = (ND){makeTree(s + 1, temp), makeTree(temp, e)};

    return input[s];
}

void printPostOrder(int x) {
    if (x == NOTEXIST) {
        return;
    }

    printPostOrder(tree[x].left);
    printPostOrder(tree[x].right);
    printf("%d\n", x);
    return;
}

int main() {
    int temp;
    while (~scanf("%d", &temp)) {  // input until EOF
        input[len++] = temp;
    }

    int root = makeTree(0, len);

    printPostOrder(root);
    return 0;
}

• tree[] : 트리의 노드를 기록. 이진 트리이므로 왼쪽과 오른쪽을 가리키는 정보가 있다. 노드의 값은 index 자체이다.