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

문제

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

풀이

문제 자체는 별로 어렵지 않은데, 입력 부분이 뭔가 까다롭다. 프로그램을 강제 종료할 때 까지 계속 입력하게 하는 방식인데, 프로그램을 강제 종료하면 출력하고 끝내면 된다. C++ 기준으로 강제 종료 전까지 무한 입력을 하는 방법은 아래와 같다. 형태는 여러가지가 나올 수 있지만 cin.eof() == true 일 때 입력을 종료할 수 있다.

while(true){
        int t; cin >> t;
        if(cin.eof() == true) break;
    }

이제 문제는 어렵지 않다. 매 입력 시에 입력으로 받은 숫자를 문제의 조건에 따라 적절한 위치를 탐색해서 배치해주기만 하면 된다. 즉, root 노드 부터 탐색하면서 현재 노드보다 크면 오른쪽, 작으면 왼쪽으로 이동하고, 이 때 현재 노드의 오른쪽 또는 왼쪽에 child 노드가 없다면 이 숫자를 child 노드에 배치하면 된다.

입력이 모두 끝나면 후위 순회로 탐색한 결과를 출력해주면 된다. 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

int tree2[1000000][2];

void postorder(int root){
    
    if(tree2[root][0] != 0) postorder(tree2[root][0]);
    if(tree2[root][1] != 0) postorder(tree2[root][1]);
    
    if(root != -1) cout << root << '\n';
}


void preorder2(int curr, int root){
    if(curr > root){
        if(tree2[root][1] == 0){
            tree2[root][1] = curr; return;
        }
        else{
            preorder2(curr, tree2[root][1]);
        }
    }
    else if(curr < root){
        if(tree2[root][0] == 0){
            tree2[root][0] = curr; return;
        }
        else{
            preorder2(curr, tree2[root][0]);
        }
    }
}


int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    int n, root = -1;

    while(true){
        cin >> n; 
        if(cin.eof() == 1) break;
        if(root == -1) root = n;
        else preorder2(n, root);
    }

    postorder(root);
    
    return 0;
}