[백준 - 5639] 이진 검색 트리 - C++

분류: 트리 구현, 그래프 탐색, 트리 순회 /

 

문제

문제 링크

문제 설명

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

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

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

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

입력

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

출력

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

 

풀이

#include <iostream>
using namespace std;
const int ROOT = 1;

int V[10001], L[10001], R[10001], len;

inline int makeNode(int val) {
    V[++len] = val;
    return len;
}
void push(int node, int val) {
    if(V[node] == 0) {
        makeNode(val);
        return;
    }
    if(val < V[node]) {
        if(L[node]) push(L[node], val);
        else L[node] = makeNode(val);
    }
    else {
        if(R[node]) push(R[node], val);
        else R[node] = makeNode(val);
    }
}

void printTree(int node) {
    if(node < ROOT or node > len) return;
    printTree(L[node]);
    printTree(R[node]);
    cout << V[node] << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int x;
    while(cin >> x) push(ROOT, x);
    printTree(ROOT);
}

입력으로 트리를 만드는 함수 `push()`

후위 순회로 출력하는 함수 `printTree()`

트리의 전위 순회, 중위 순회 출력은 [백준 - 1991] 트리 순회 문제에서 확인 할 수 있다.

 

입력으로 트리를 만드는 `push()`는 전위 순회 입력과 관계없이 루트부터 내려가며 트리를 생성한다.

`len`은 트리의 길이이며 가장 마지막에 트리에 추가된 노드의 인덱스는 `len`이다.

 

인덱스가 `i`인 노드의 값은 `V[i]`, 왼쪽 자식 노드의 인덱스는 `L[i]`, 오른쪽 자식 노드의 인덱스는 `R[i]`