이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력
50 30 24 5 28 45 98 52 60
출력
5 28 24 45 30 60 52 98 50
코드
#include <iostream>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
node* MakeNode(int n)
{
node* nd = new node;
nd->data = n;
nd->left = NULL;
nd->right = NULL;
return nd;
}
node* root = NULL;
void Insert(node* r, node* node) //노드를 삽입하는 코드
{
if (root == NULL) root = node;
else if (r->data < node->data)
{
if (r->right == NULL)
r->right = node;
else
Insert(r->right, node);
}
else if ((r->data > node->data))
{
if (r->left == NULL)
r->left = node;
else
Insert(r->left, node);
}
}
void postorder(node* nd) //후위 순회하는 코드
{
//left 먼저 찾아주기
if (nd->left != NULL)
postorder(nd->left);
if (nd->right != NULL)
postorder(nd->right);
cout << nd->data << "\n";
}
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int value;
while (cin >> value)
{
Insert(root, MakeNode(value));
}
postorder(root);
return 0;
}
