数据结构实验之求二叉树后序遍历和层次遍历

Problem Description
 已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历和层序遍历。

Input
 输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。

Output
每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列。

Example Input
2
abdegcf
dbgeafc
xnliu
lnixuExample Output
dgebfca
abcdefg
linux
xnuliHint
Author

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree creat(char *pre,char *in,int n){//前序、中序建树
BiTree T;
char *p;
if(n==0)
return NULL;
int m;
T=new BiTNode;
T->data=*pre;
for(p=in;p!=NULL;p++)
if(*p==*pre)
break;
m=p-in;
T->lchild=creat(pre+1,in,m);
T->rchild=creat(pre+m+1,p+1,n-m-1);
return T;
}
void preorder(BiTree T){//后序
if(T){
preorder(T->lchild);
preorder(T->rchild);
printf("%c",T->data);
}
}
void postorder(BiTree T){//层次
int rear=1,front=0;
BiTree p[51];
p[0]=T;
while(rear>front){
if(p[front]){
printf("%c",p[front]->data);
p[rear++]=p[front]->lchild;
p[rear++]=p[front]->rchild;
front++;
}
else
front++;
}
}
int main(){
int n,k;
char pre[51],in[51];
BiTree T;
T= (BiTree)malloc(sizeof(BiTNode));
scanf("%d%*c",&n);
while(n--){
scanf("%s%s",pre,in);
k=strlen(pre);
T=creat(pre,in,k);
preorder(T);
printf("\n");
postorder(T);
printf("\n");

}
return 0;
}