时间限制: 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 }
