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

문제링크 : https://noj.am/5639

이진 트리를 구성하고 있는 각 노드는 다음과 같이 표현한다.

V - 부모 노드

L - 왼쪽 자식 노드

R - 오른쪽 자식 노드

이진 트리의 순회 방식은 다음과 같다.

전위 순회 : V-L-R

중위 순회 : L-V-R

후위 순회 : L-R-V

문제에서 주어진 다음 조건을 보면 힌트를 유추할 수 있다.

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

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

입력으로 전위순회를 시행했을 때의 결과가 주어진다고 했기 때문에 위의 원리를 그대로 적용해보면 각 노드별 서브트리를 구할 수 있다.

50 30 24 5 28 45 98 52 60

V-L-R의 순서로 순회할 때 가장 먼저 방문하는 노드(빨간색)는 루트 노드(V)이고,

조건1에 따라 50보다 작은 모든 노드(파란색)는 왼쪽 서브트리이고,

조건2에 따라 50보다 큰 모든 노드(초록색)는 오른쪽 서브트리이다.

우리는 이 V-L-R의 순서를 L-R-V로 바꿔야한다.

따라서, L sub와 R sub를 재귀적인 방법으로 다시 탐색하고 모든 탐색이 끝난 후 V를 출력해주면 될 것이다.

재귀적인 방법을 쭉 나열해보면 아래와 같이 시행된다.

* 각 시행마다 진하게 표시된 글자는 다음 시행에서 실행될 프로시저를 의미

* 컬러로 표시된 글자는 이전 시행에서의 결과를 의미

위 이미지가 너무 빠르다면 클릭

↓↓↓

50 30 24 5 28 45 98 52 60

<1회>

L sub 탐색 - 30 24 5 28 45

R sub 탐색 - 98 52 60

50 출력

<2회>

LL sub 탐색 - 24 5 28

LR sub 탐색 - 45

30 출력

R sub 탐색 - 98 52 60

50 출력

<3회>

LLL sub 탐색 - 5

LLR sub 탐색 - 28

24 출력

LR sub 탐색 - 45

30 출력

R sub 탐색 - 98 52 60

50 출력

<4회>

(탐색할 서브트리 없음)

5 출력

LLR sub 탐색 - 28

24 출력

LR sub 탐색 - 45

30 출력

R sub 탐색 - 98 52 60

50 출력

<5회> : 5

5 출력

(탐색할 서브트리 없음)

28 출력

24 출력

LR sub 탐색 - 45

30 출력

R sub 탐색 - 98 52 60

50 출력

<6회> : 5 28 24

28 출력

24 출력

(탐색할 서브트리 없음)

45 출력

30 출력

R sub 탐색 - 98 52 60

50 출력

<7회> : 5 28 24 45 30

45 출력

30 출력

RL sub 탐색 - 52 60

98 출력

50 출력

<8회> : 5 28 24 45 30

RLR sub 탐색 - 60

52 출력

98 출력

50 출력

<9회> : 5 28 24 45 30

(탐색할 서브트리 없음)

60 출력

52 출력

98 출력

50 출력

<종료> : 5 28 24 45 30 60 52 98 50

60 출력

52 출력

98 출력

50 출력

// BOJ 5639 이진 검색 트리
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> arr;
 
void preToPost(int l, int r) {
    int ans = l; // 현재 노드(부모노드)
    int sub = l++; // 좌,우 서브트리를 나누는 인덱스
    while (arr[++sub] < arr[ans]); // 인덱스 계산
    // 좌측 서브트리
    if (l <= sub - 1)
        preToPost(l, sub - 1);
    // 우측 서브트리
    if (sub <= r)
        preToPost(sub, r);
    cout << arr[ans] << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
    int input;
    while (cin >> input) arr.push_back(input);
    arr.push_back(INT32_MAX); // segment fault 방지
    preToPost(0, arr.size() - 2);
 
    return 0;
}

참고로 다음 코드는

arr.push_back(INT32_MAX); // segment fault 방지

이 부분에서 arr.size()를 초과하는 범위를 탐색했을 경우 컴파일 에러가 나기 때문에 아무 의미 없는 int의 MAX 값을 넣은 것이다.

while (arr[++sub] < arr[ans]); // 인덱스 계산

아니면 다음과 같이 표현해도 된다.

while (++sub < arr.size() && arr[sub] < arr[ans]); // 인덱스 계산