[5639] 이진 검색 트리

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

5639번: 이진 검색 트리

<문제>

숫자의 대소관계로 탐색범위를 두개씩 쪼개준다. 분할정복같은 느낌으로 접근하면 되며, 이를 재귀로 구현했다.

 

<소스코드>

#include<stdio.h>
#include<iostream>
using namespace std;
int a[10001], x, cnt;
void f(int start, int end) {
    if (start == end)return;
    else if (start == end - 1) {
        printf("%d\n", a[start]);
        return;
    }
    int i;
    for (i = start + 1; i < end && a[i] < a[start]; i++);
    f(start + 1, i);
    f(i, end);
    printf("%d\n", a[start]);
}
int main(void) {
    int i=0;
    while (1) {
        cin >> x;
        if (cin.eof() == true)break;
        a[cnt] = x;
        cnt++;
    }
    f(0, cnt);
    return 0;
}