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

5639번 : 이진 검색 트리

---

문제)

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

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

 

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

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

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

#include <iostream>
using namespace std;
 
int arr[10010];
 
void postorder(int s, int e)
{
    if (s >= e) return;
 
    int idx = s + 1;
    while (idx < e)
    {
        if (arr[s] < arr[idx]) break;
        idx++;
    }
 
    postorder(s + 1, idx);
    postorder(idx, e);
 
    cout << arr[s] << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int num, idx = 0;
 
    while (cin >> num)
    {
        arr[idx++] = num;
    }
 
    postorder(0, idx);
 
    return 0;
}
 
// 전위 순회
// 50 30 24 5 29 45 98 52 60 이 들어왔을 때
// 처음 50은 루트 노드가 되고,
// 이후 50보다 큰 수가 들어올때까지 
// 30 24 5 29 45는 왼쪽 노드가 된다.
// 다시 30을 기준으로 45전 까지의 수들은 왼쪽 노드가 되고,
// 24 기준으로는 29 전까지의 수가 왼쪽 노드가 된다.
 
// 50 // 30 24 5 29 45 // 98 52 60
// 30 // 24 5 29 // 45
// 24 // 5 // 29
 
 

---

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

5639번: 이진 검색 트리