[5639] 이진 검색 트리

### Tree Traversal ###

[5639] 이진 검색 트리 : http://boj.kr/5639

<소스코드>

#include <stdio.h>
 
int arr[10001];
 
void post(int L, int R)
{
    if(L >= R) return ;
    int k = L+1;
    while(k < R && arr[k] < arr[L]) k++;
    post(L+1, k);
    post(k, R);
    printf("%d\n", arr[L]);
}
 
int main()
{
    int n;
    int idx=0;
    while(scanf("%d", &n) == 1) {
        arr[idx++] = n;
    }
    
    post(0, idx);
    return 0;
}
 

>> 전위위회의 결과를 준 상태에서 후위순휘의 결과를 출력하는 문제.

>> 전위순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회를 한다. 

>> 후위순회를 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 순회를 한다.

>> 이진탐색트리는 왼쪽 서브트리는 루트보다 작은 키값들을 가지며, 오른쪽 서브트리는 루트보다 큰 키 값을 가진다. 

>> 이 특징을 이용하여 왼쪽 서브트리와 오른쪽 서브트리의 데이터들을 구분할 수 있다.

     그럼 왼쪽 서브트리의 데이터 - 오른쪽 서브트리의 데이터 - 루트 순으로 출력을 하면 된다.