题目描述：
二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
输入描述：
两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
输出描述：
可能有多组样例，对于每组样例输出一行为后序遍历的字符串。
exp：
input output
ABC BCA
BAC
FDXEAG XEDGAF
XDEFAG
解题思路：
二叉树通过先序遍历和中序遍历以推出后序遍历序列
首先把输入的中序遍历和先序遍历存在两个字符串中
通过递归方法建立二叉树。
如：
前序：FDXEAG
中序：XDEFAG
记前序首位为l1，末位为r1
记中序首位为l2，末位为r2
分析：
前序遍历的第一个结点必然是二叉树的根结点(也可以是部分分支的根部节点,每一次调用建树函数可以唯一确定一个根部节点)
在中序遍历中找到这一节点位置记为i
记中序遍历首位开始到i的前一位【字符串长度】为len1=i-l2
记i后一位到中序遍历末位【字符串长度】为len2=r2-i
判断：如果len1>0 即有左子树情况 则对左子树部分递归调用建树函数（右子树同理）
如上例输入中，F为前序的第一个节点，此时在中序遍历中寻找F，在第4位，从而XDE为F的左子树的中序遍历，AG为F的右子树的中序遍历
XDE长度为3，即F后面连续的3位为F左子树的前序遍历，前序遍历序列倒数2位为F右子树的前序遍历
每次调用递归函数时，将上一次调用函数分出来的左右子树视为一个新的二叉树，按规则继续建树
建立完一棵树后再后序遍历输出结果即可。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 typedef struct BNode 5 { 6 char data; 7 struct BNode *lchild,*rchild; 8 } BNode,*btree; 9 btree buildtree(char preod[],int l1,int r1,char inod[],int l2,int r2) 10 { 11 BNode *t; 12 int i; 13 t=(BNode *)malloc(sizeof(BNode)); 14 t->data=preod[l1]; 15 for(i=l2; inod[i]!=t->data; i++); //寻找根在中序遍历的位置 16 int len1=i-l2,len2=r2-i; 17 if(len1>0)//如果有左子树 18 t->lchild=buildtree(preod,l1+1,l1+len1,inod,l2,l2+len1-1); 19 else t->lchild=NULL; 20 if(len2>0) 21 t->rchild=buildtree(preod,r1-len2+1,r1,inod,r2-len2+1,r2); 22 else t->rchild=NULL; 23 return t; 24 } 25 void postorder(btree t) 26 { 27 if(t->lchild) postorder(t->lchild); 28 if(t->rchild) postorder(t->rchild); 29 printf("%c",t->data); 30 return; 31 } 32 int main() 33 { 34 BNode *t; 35 int i=0; 36 char str1[30],str2[30]; 37 while(scanf("%s",str1)!=EOF) 38 { 39 scanf("%s",str2); 40 int l1=strlen(str1); 41 int l2=strlen(str2); 42 t=buildtree(str1,0,l1-1,str2,0,l2-1); 43 postorder(t); 44 printf(" "); 45 } 46 return 0; 47 }