[백준 5639번] [트리] 이진 검색 트리

종만북에서 본 적이 있는 유형이라 쉽게 푼 편이다.

 

이분트리 탐색의 경우에는 재귀를 활용해줘서 처리해주면 된다. 부분과 전체를 보면서 코드를 구현할 수 있어야 한다.

이 문제를 요약하면 전위 순회를 후위 순회로 돌려야하는 것이다.

 

이분트리를 보면 각 노드를 기준으로 왼쪽은 자신보다 더 작고, 오른쪽은 자신보다 크다.

이러한 성질은 전체적으로 보아도 성립하고 최소 단위로 보아도 성립한다.

 

즉, 전위 순회를 한 데이터를 기준으로 자신보다 큰 숫자가 나올 때 그것이 오른쪽 노드의 시작을 의미함을 이해할 수 있다.

그러므로 자신보다 큰 숫자가 어느 시점에 나오는지를 확인하고 그것을 기준으로 왼쪽과 오른쪽 노드를 구분하면 된다.

 

후위 순회의 경우, 이 과정에서 자식 노드의 왼쪽과 오른쪽을 출력하고 자기자신을 출력해주면 되는 것이다.

즉, 계속해서 부분으로 찢어나가면서 왼쪽, 오른쪽, 자기자신을 출력해주면 된다.

 

위의 알고리즘을 통해 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

void down_cycle(const vector<int> &upper_cycle, int check, int start, int end){
    int end_point = -1;
    if(start >= end){
        return;
    }
    for(int i = start; i < end; i++){
        if(upper_cycle[check] < upper_cycle[i]){
            end_point = i;
            break;
        }
    }
    if(end_point != -1){
        down_cycle(upper_cycle, check + 1, check + 1, end_point);
        down_cycle(upper_cycle, end_point, end_point, end);
        cout << upper_cycle[check] << "\n";
    }
    else{
        down_cycle(upper_cycle, check + 1, check + 1, end); 
        cout << upper_cycle[check] << "\n";
    }
    return;   
}

int main(void){
    vector<int> upper_cycle;

    int temp;
    while(true){
        cin >> temp;
        if(cin.eof() == true) break;
        else upper_cycle.push_back(temp);   
    }// data_store until EOF
    down_cycle(upper_cycle, 0, 0, upper_cycle.size());
    return 0;
}