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

5639번: 이진 검색 트리

---

 

---

---

• 제목

이진 검색 트리

---

• 조건

시간 제한 : 1 초

메모리 제한 : 256 MB 

---

• 문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

---

• 입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

---

• 출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

---

예제 입력1	예제 출력1
50 30 24 5 28 45 98 52 60	5 28 24 45 30 60 52 98 50

---

#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
class node {
public:
	int value;
	node* left = NULL;
	node* right = NULL;
};
class binary_tree {
public:
	node* head = NULL;
	void insertion(int val) {
		node* tmp = new node;
		tmp->value = val;
		if (this->head == NULL) {
			this->head = tmp;
			return;
		}
		else {
			node* ptr = this->head;

			while (true) {
				if (ptr->value < val) {
					if (ptr->right == NULL) {
						ptr->right = tmp;
						return;
					}
					ptr = ptr->right;
				}
				else { // ptr->value > val
					if (ptr->left == NULL) {
						ptr->left = tmp;
						return;
					}
					ptr = ptr->left;
				}
			}
		}
	}
};

void postorder(node* ptr) {
	if (ptr->left != NULL) postorder(ptr->left);
	if (ptr->right != NULL) postorder(ptr->right);
	cout << ptr->value << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int val;
	binary_tree bt;
	
	while (cin >> val){
		bt.insertion(val);
	}
    
	postorder(bt.head);
	return 0;
}