[백준 5639] 이진 검색 트리 (C++)

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

문제

---

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

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

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

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

입력

---

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

출력

---

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

 

문제 풀이

---

트리 문제.

 

입력은 트리를 전위 순회한 결과이므로, 가장 첫번째 입력은 트리의 루트가 된다. 이를 바탕으로 BST를 구성해준다. 노드 자체의 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 가지는 struct를 만들어 첫 번째 입력을 값으로 가지는 트리의 루트를 생성한다. 그 이후 다른 입력들 값으로 하는 노드를 생성하여 BST의 조건에 맞게 반복하여 트리의 자식을 방문하며 삽입할 자리를 찾아낸다. 현재 방문한 트리의 왼쪽 자식 노드 혹은 오른쪽 자식 노드가 존재하지 않는다면 입력으로 만들어진 새 노드가 현재 방문한 트리의 자식 노드가 된다. 

 

후위 순회는 재귀를 이용하여 왼쪽 자식 노드릍 방문하고, 그 후 오른쪽 자식 노드를 방문하고, 마지막으로 루트를 출력해주면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

struct node
{
	int value;
	node* leftChild;
	node* rightChild;
	node(int v)
	{
		value = v;
		leftChild = NULL;
		rightChild = NULL;
	}
};

void postOrder(node* node)
{
	if (node->leftChild != NULL)
	{
		postOrder(node->leftChild);
	}
	if (node->rightChild != NULL)
	{
		postOrder(node->rightChild);
	}
	cout << node->value << "\n";
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	node* root = NULL;
	node* currentNode;
	int num;
	while (true)
	{
		cin >> num;
		if (cin.eof() == true)
		{
			break;
		}
		currentNode = root;
		if (currentNode == NULL)
		{
			root = new node(num);
			continue;
		}
		node* newNode = new node(num);
		node* prevNode = root;
		while (true)
		{
			prevNode = currentNode;
			if (num < currentNode->value)
			{
				currentNode = currentNode->leftChild;
				if (currentNode == NULL)
				{
					prevNode->leftChild = newNode;
					break;
				}
			}
			else
			{
				currentNode = currentNode->rightChild;
				if (currentNode == NULL)
				{
					prevNode->rightChild = newNode;
					break;
				}
			}
		}
	}
	postOrder(root);
	return 0;
}