| Accept:28 | Submit:223 |
| Time Limit:1000MS | Memory Limit:65536KB |
Description
给定一个二叉排序树的前序遍历，输出其后序遍历。
此二叉排序树中元素互不相同，节点的左儿子比节点小，右儿子比节点大。
Input
第一行有一个整数T，表示一共有T组测试数据。
对于每组测试数据，第一行一个整数N，表示排序树中有N个元素(0 < N < = 100)。
接下来有N个互不相同的整数，表示此二叉树的前序遍历序列。
Output
每组测试数据输出一行，包含N个整数，表示该组排序树的后序遍历，整数之间用空格隔开。
Sample Input
1
3
2 1 3
Sample Output
1 3 2
#include<iostream>
#include<cstdio>
using namespace std;
typedef struct node{
int date;
struct node * lchild,*rchild;
};
node* root;
int n;
int cnt;
void insert_tree(struct node *root, int e)
{
struct node *p=root;
struct node *A=new node;
A->date=e;
A->lchild=NULL;
A->rchild=NULL;
while(1)
{
if(e>p->date)
{
if(p->rchild!=NULL)
p=p->rchild;
else {p->rchild=A; break;}
}
else {
if(p->lchild!=NULL)
p=p->lchild;
else {p->lchild=A; break;}
}
}
}
void pastorder(struct node *root)
{
if(root==NULL)
return ;
else {
pastorder(root->lchild);
pastorder(root->rchild);
cout<<root->date;
if(cnt++<n-1)
cout<<" ";
}
}
int main()
{
int t,i,temp;
cin>>t;
while(t--)
{
scanf("%d",&n);
scanf("%d",&temp);
root=new node;
root->date=temp;
root->lchild=NULL;
root->rchild=NULL;
for(i=1; i<n; i++)
{
scanf("%d",&temp);
insert_tree(root,temp);
}
cnt=0;
pastorder(root);
cout<<endl;
}
//system("pause");
return 0;
}