12_02 <백준>5639번 이진 검색 트리

출처:https://www.acmicpc.net/problem/5639

문제

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

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

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

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

문제 해결 과정: 

-전위 순회한 결과로 이진트리 생성. tree라는 구조체를 만들어 오른쪽 왼쪽 노드의 키를 저장하는 배열을 만든다.

-루트를 먼저 넣고 숫자가 작으면 왼쪽 크면 오른쪽에 넣는다

- 그 이후에 후위 순회로 출력한다.

-이진트리를 안만들고 바로 하는 방법은 없을까?

#include<iostream>
#include<cstdio>
using namespace std;
 
struct Tree {
    int left = 0;
    int right = 0;
};
 
Tree tree[100001];
 
void postOrder(int node) {
    if (tree[node].left != 0) {
        postOrder(tree[node].left);
    }
    if (tree[node].right != 0) {
        postOrder(tree[node].right);
    }
    printf("%d\n", node);
 
    
}
 
int main() {
    int root;
    int value;
    scanf_s("%d", &root);
    while (scanf_s("%d", &value)!=EOF) {
        int node = root;
        while (true) {
            if (node < value) {
                if (tree[node].right != 0) {
                    node = tree[node].right;
                }
                else {
                    tree[node].right = value;
                    break;
                }
            }
            else {
                if (tree[node].left != 0) {
                    node = tree[node].left;
                }
                else {
                    tree[node].left = value;
                    break;
                }
            }
        }
    }
    postOrder(root);
    return 0;
}