7-2 重构二叉树
分数 10
作者 李廷元
单位 中国民用航空飞行学院
给出两个字符串，分别表示二叉树的先序遍历（根、左子树、右子树）和中序遍历（左子树、根、右子树）的结果。
例如，对于下面的二叉树，先序遍历结果是DBACEGF，中序遍历结果是ABCDEFG。
binary_tree.jpg
假定二叉树的每个节点都用大写的字母标识，且对于同一棵二叉树，同一个字母不会用两次。现在请你根据给出的先序遍历和中序遍历，重构这棵二叉树。
输入格式:
输入包含一个或多个测试用例。每个测试用例一行，给出两个字符串，表示对二叉树进行先序遍历和中序遍历的结果。这两个字符串都是由大写字母组成（因此它们的长度不超过26）。
输出格式:
将每个测试用例转化为一棵二叉树，并在一行中输出树的后序遍历（左子树、右子树、根）的结果。
输入样例:
DBACEGF ABCDEFG
BCAD CBAD
输出样例:
ACBFGED
CDAB
代码长度限制
16 KB
时间限制
1000 ms
内存限制
我的代码
#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef int ElemType;
typedef struct BiTreeNode
{
ElemType data;
struct BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;
BiTree PreInOrder (char preord[ ],char inord[ ],int i,int j,int k,int h);
void show(BiTree bt);
int main()
{
BiTree t;
int i,j,k,h,n,q;
char preord[26],inord[26];
scanf("%d",&n);
for(int q=1;q<=n;i++)
{
gets(preord);
gets(inord);
j=strlen(preord);
h=strlen(inord);
t=PreInOrder(preord,inord,i,j,k,h);
show(t);
}
}
BiTree PreInOrder (char preord[], char inord[], int i , int j , int k , int h)
{
BiTree t;
int m ;
t=(BiTreeNode *)malloc(sizeof(BiTreeNode));
t-> data = preord[i] ;
m= k ;
while ( inord[m] != preord[i] ) m++ ;
if(m == k ) t-> lchild =NULL ;
else
t-> lchild =PreInOrder ( preord , inord , i+1 , i+m-k , k , m-1 );
if( m == h ) t -> rchild = NULL ;
else
t->rchild =PreInOrder (preord ,inord ,i+m-k+1,j ,m+1 , h);
return t;
}
void show(BiTree t)
{
if(t)
{
show(t->lchild);
show(t->rchild);
printf("%c",t->data);
}
}
