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

문제

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

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

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

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

 

입력

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

 

출력

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

---

이진 탐색 트리와 후위 순회만 구현하면 간단하게 풀 수 있는 문제.. 라고 생각했지만 함수까지 짜놓고 제대로 쓰는 방법을 몰라서 생각보다 오래걸렸다....ㅜㅜ

 

코드

#include <cstdio>

struct node {
    int data;
    node* left;
    node* right;
};

node* insert(node* tree, int data);
void post(node* tree);

int main(void) {
    node* tree;
    tree = NULL;

    int num;
    while(scanf("%d", &num) != EOF) {
        tree = insert(tree, num);
    }

    post(tree);
    return 0;
}

node* insert(node* tree, int data) {
    if(tree == NULL) {
        tree = new node();
        tree->data = data;
        tree->left = tree->right = NULL;
    }

    else if(data > tree->data) {
        tree->right = insert(tree->right, data);
    }
    else {
        tree->left = insert(tree->left, data);
    }

    return tree;
}

void post(node* tree) {
    if(tree->left != NULL) post(tree->left);
    if(tree->right != NULL) post(tree->right);
    printf("%d\n", tree->data);
}