描述
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及某一种遍历，要求输出另一种遍历。
输入
输入包括若干个测试用例，第一行为一个自然数n，表示用例个数，接下来4n行，即每个用例占4行，其中第一行表示第一种遍历方式，第二行为第一种遍历结果，第三行为第二种遍历方式，第4行为第二种遍历结果。注明：先序遍历方式用“pre”表示，中序遍历方式用“in”表示，后序遍历方式用“post”表示。
输出
对每个测试用例，输出相应的另一种遍历方式及结果。每个用例用一行输出，输出格式为先输出相应的遍历方式，然后一个冒号，再加一个空格，最后输出相应的遍历结果。
样例输入
1
pre
ABDFCEG
in
BFDAEGC
pre
ABDFCEG
in
BFDAEGC
样例输出
post: FDBGECA
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char pre[30],in[30];
int l;
typedef struct node
{
struct node *ld,*rd;
char data;
}tree;
tree * creat1(int low,int high,int x)
{
if(low>high) return NULL;
int i;
for(i=low;i<=high;i++)
if(in[i]==pre[x]) {break;}
tree *p=new tree;
p->data=pre[x];
p->ld=creat1(low,i-1,x+1);
p->rd=creat1(i+1,high,x+1+i-low);
return p;
}
tree * creat2(int low,int high)
{
if(low>high) return NULL;
tree *p=new tree;
int i,j,f;
for(f=0,i=l-1;i>=0;i--)
{
for(j=low;j<=high;j++)
if(in[j]==pre[i]) {f=1;break;}
if(f) break;
}
p->data=in[j];
p->ld=creat2(low,j-1);
p->rd=creat2(j+1,high);
return p;
}
void preorder(tree *t)
{
if(t)
{
cout<<t->data;
preorder(t->ld);
preorder(t->rd);
}
}
void postorder(tree *t)
{
if(t)
{
postorder(t->ld);
postorder(t->rd);
cout<<t->data;
}
}
int main()
{
int n,m,f;
string s;
tree *t;
scanf("%d",&n);
while(n--)
{
m=2;
while(m--)
{
cin>>s;
if(s=="pre"||s=="post") {if(s=="pre") f=1; else f=2; cin>>pre;}
if(s=="in") cin>>in;
}
l=strlen(in);
if(f==1) {t=creat1(0,l-1,0); cout<<"post: "; postorder(t); cout<<endl;}
else {t=creat2(0,l-1); cout<<"pre: "; preorder(t); cout<<endl;}
}
return 0;
}