codevs 2010 求后序遍历

时间限制: 1 s空间限制: 64000 KB
题目描述 Description
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
输入描述 Input Description
共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。
输出描述 Output Description
仅一行，表示树的后序遍历序列。
样例输入 Sample Input
abdehicfg
dbheiafcg
样例输出 Sample Output
dhiebfgca
数据范围及提示 Data Size & Hint
输入长度不大于255。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<malloc.h>
 4 typedef char ElemType;
 5 typedef struct node 
 6 {    
 7     ElemType data;            //数据元素
 8     struct node *lchild;    //指向左孩子结点
 9     struct node *rchild;    //指向右孩子结点
10 } BTNode;
11 BTNode *CreateBT1(char *pre,char *in,int n)
12 /*pre存放先序序列,in存放中序序列,n为二叉树结点个数,
13 本算法执行后返回构造的二叉链的根结点指针*/
14 {
15     BTNode *s;
16     char *p;
17     int k;
18     if (n<=0) return NULL;
19     s=(BTNode *)malloc(sizeof(BTNode));        //创建二叉树结点*s
20     s->data=*pre;
21     for (p=in;p<in+n;p++)                    //在中序序列中找等于*ppos的位置k
22         if (*p==*pre)                        //pre指向根结点
23             break;                            //在in中找到后退出循环
24     k=p-in;                                    //确定根结点在in中的位置
25     s->lchild=CreateBT1(pre+1,in,k);        //递归构造左子树
26     s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); //递归构造右子树
27     return s;
28 }
29 void PostOrder(BTNode *b) /*后序遍历递归算法*/
30 {
31     if (b!=NULL)  
32     {
33         PostOrder(b->lchild);
34         PostOrder(b->rchild);
35         printf("%c",b->data); /*访问根结点*/
36     }
37 }
38 int main(int argc, char *argv[])
39 {
40     freopen("2010.in","r",stdin);
41     char pre[260],in[260];
42     BTNode *root;
43     
44     scanf("%s%s",pre,in);
45     root=CreateBT1(pre,in,strlen(in));
46     PostOrder(root);
47     return 0;
48 }