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

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

 Input 

50

30

24

5

28

45

98

52

60

　 

 Output 

5

28

24

45

30

60

52

98

50

[Jungol] 1716 이진트리 탐색와 비슷한 유형

노드를 얼마나 입력받는지 알 수 없으므로 아래와 같이 입력이 없어질 때까지 정점(노드)을 입력 받습니다.

이진 검색 트리가 형성되는 조건을 이용해서 왼쪽/오른쪽 서브트리를 확장해갑니다.

　

전위/중위/후위 순회에서 차이는 ( ① 왼쪽 서브 트리 ② 오른쪽 서브 트리 ③ ) 탐색 순서에서

Root Node ① ~ ③ 중에서 언제 방문하느냐 입니다.

① 전위 순회

② 중위 순회

③ 후위 순회

---

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
struct Node {
    int data;
    Node* lch, *rch;
    Node* alloc(int nd) {
        data = nd;
        lch = rch = NULL;
        return this;
    }
}buf[10010];
int N, num, bcnt;
 
struct Tree {
    Node* head = NULL;
    void build(int num) {
        // 트리가 비어있는 경우 (Root Node 추가)
        if (head == NULL) { 
            head = buf[bcnt++].alloc(num);
            return;
        }
        // 트리에 노드가 적어도 1개 이상 존재.
        Node *p = head;
        while (p) {
            // 왼쪽 서브 트리 탐색
            if (p->data > num) {
                // 왼쪽 자식 노드가 없는 경우
                if (p->lch == NULL) {
                    p->lch = buf[bcnt++].alloc(num);
                    return;
                }
                p = p->lch;
            }
            // 오른쪽 서브 트리 탐색
            else if (p->data < num) {
                // 오른쪽 자식 노드가 없는 경우
                if (p->rch == NULL) {
                    p->rch = buf[bcnt++].alloc(num);
                    return;
                }
                p = p->rch;
            }
        } 
    }
};
 
void postOrder(Node* now) {
    if (now == NULL) return;
    postOrder(now->lch);
    postOrder(now->rch);
    printf("%d\n", now->data);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    Tree* tree = new Tree;
 
    while (cin >> num) {
        tree->build(num);
    }
    
    postOrder(tree->head);
}