문제
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
출력
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
50
30
24
5
28
45
98
52
60
예제 출력 1
5
28
24
45
30
60
52
98
50
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
};
Node* AddNode(Node* node, int data)
{
if (node == NULL)
{
node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;
}
else if (node->data > data)
{
node->left = AddNode(node->left, data);
}
else
{
node->right = AddNode(node->right, data);
}
return node;
}
void postorder(Node * node)
{
if (node == NULL)
{
return;
}
postorder(node->left);
postorder(node->right);
cout << node->data << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int input;
Node* root = NULL;
while (cin >> input)
{
if (input == EOF)
{
break;
}
root = AddNode(root, input);
}
postorder(root);
return 0;
}
728x90
반응형
'알고리즘 > solved.ac' 카테고리의 다른 글
[class4] (백준 11660) 구간 합 구하기 5 (0) | 2022.01.30 |
---|---|
[class4] (백준 9465) 이진 검색 트리 (0) | 2022.01.29 |
[class4] (백준 1191) 트리 순회 (0) | 2022.01.27 |
[class4] (백준 1932) 정수 삼각형 (0) | 2022.01.26 |
[class4] (백준 1629) 곱셈 (0) | 2022.01.24 |