BOJ_5639) 이진 검색 트리

# 문제

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

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

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

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

---

# 입력

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

---

# 출력

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

---

# 코드

#include <iostream>

using namespace std;

class TreeNode {
	int data;
	TreeNode* left;
	TreeNode* right;
public:
	TreeNode(int data) {
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
	~TreeNode() { delete left; delete right; }
	int getData() { return data; }
	TreeNode* getLeft() { return left; }
	TreeNode* getRight() { return right; }
	void setLeft(TreeNode* left) { this->left = left; }
	void setRight(TreeNode* right) { this->right = right; }
};

class Tree {
	TreeNode* root;
public:
	Tree() {
		root = NULL;
	}
	~Tree() { delete root; }
	TreeNode* getRoot() { return root; }
	void insertData(int data);
	void postorder(TreeNode* root);
};

void Tree::insertData(int data) {
	TreeNode *tn, *cur = NULL, *next = this->getRoot();
	while (next) {
		cur = next;
		if (data < cur->getData()) next = cur->getLeft();
		else next = cur->getRight();
	}
	tn = new TreeNode(data);
	if (!cur) this->root = tn;
	else if (data < cur->getData()) cur->setLeft(tn);
	else cur->setRight(tn);
}

void Tree::postorder(TreeNode* root) {
	if (root) {
		postorder(root->getLeft());
		postorder(root->getRight());
		cout << root->getData() << endl;
	}
}

int main() {
	int num;
	Tree* T = new Tree();
	while (cin >> num) T->insertData(num);
	T->postorder(T->getRoot());
	return 0;
}

참조링크

왠만하면 STL을 사용하려고 했지만, 이진 탐색 트리의 경우 적절한 STL이 없는 것 같아서 class로 정의하여 사용하는게 좋다고 생각하였다. C++의 Class관련 문법을 몰라서 문제를 검색해 보다가 위 링크의 코드가 가장 깔끔한 것 같아서 따라서 써봤다.

---