백준 5639 이진 검색 트리 C++

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

이진 검색 트리를 구현해주면 된다.

왼쪽 자식은 부모보다 작은 값이고, 오른쪽 자식은 부모보다 큰 값이다.

이진 검색 트리의 서브트리는, 마찬가지로 이진 검색 트리이다.

이 문제에서는 node 구조체를 root값 자체를 인덱스로 하도록 잡았다.

이전에 트리 순회 문제에서도 봤듯이, 순회가 문제에 섞일 때에는 인덱스를 루트의 값과 연결시켜서 잡아주는 것이 좋은 것 같다.

이 문제에서 주의할 사항은, 루트의 값 자체를 인덱스로 사용하기 때문에, 전체 노드의 개수가 아닌, root값의 허용 범위를

인덱스로 잡아줘야하다는 것이다.

#include<iostream>
using namespace std;
 
struct NODE{
    int l, r;
}n[1000002]; //인덱스가 root
//노드의 개수는 1000개인데, 인덱스를 루트로 쓰고 있기 때문에 루트의 허용 범위만큼 인덱스 필요
 
void postOrder(int rt) {
    if (rt == 0) return;
    postOrder(n[rt].l);
    postOrder(n[rt].r);
    cout << rt << '\n';
}
 
int main(void) {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    int root;
    cin >> root; //전위순회니까 처음 나오는 게 무조건 tree의 root
    int num;
    while (cin >> num) {
        int cur = root;
        while (1) {
            if (num < cur) {
                if (n[cur].l != 0) cur = n[cur].l;
                else {
                    n[cur].l = num;
                    break;
                }
            }
            else {
                if (n[cur].r != 0) cur = n[cur].r;
                else {
                    n[cur].r = num;
                    break;
                }
            }
 
        }
    }
    postOrder(root);
    return 0;
}