题目描述 已知某二叉树的先序序列和中序序列，编程计算并输出该二叉树的后序序列。  
输入 有多组数据，每组分为两行输入，第一行表示指定二叉树的先序序列，第二行表示该二叉树的中序序列，序列元素均为大写英文字符，表示二叉树的结点。  
输出 对于每组数组，在一行上输出该二叉树的后序序列。  
样例输入 ABDGCEFH
DGBAECHF
 
样例输出 GDBEHFCA  
提示 [+] *** 提示已隐藏，点击上方 [+] 可显示 ***  
来源 2009年西电计算机研究生复试上机题  
这道题是考先序 中序 求后序。如果看后序 中序 求先序 看我的博文：点击打开链接 /********************************* * 日期：2013-3-11 * 作者：SJF0115 * 题号: 天勤OJ 题目1218: Problem D * 来源：http://acmclub.com/problem.php?id=1218 * 结果：AC * 来源：2009年西电计算机研究生复试上机题 * 总结： **********************************/ #include #include #include //二叉树结点 typedef struct BiTNode{ //数据 char data; //左右孩子指针 struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; /* PreIndex: 前序序列字符串中子树的第一个节点在PreArray[]中的下标 InIndex: 中序序列字符串中子树的第一个节点在InArray[]中的下标 subTreeLen: 子树的字符串序列的长度 PreArray： 先序序列数组 InArray：中序序列数组 */ char PreArray[101],InArray[101]; void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){ //subTreeLen < 0 子树为空 if(subTreeLen <= 0){ T = NULL; return; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //创建根节点 T->data = PreArray[PreIndex]; //找到该节点在中序序列中的位置 int index = strchr(InArray,PreArray[PreIndex]) - InArray; //左子树结点个数 int LenF = index - InIndex; //创建左子树 PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF); //右子树结点个数(总结点 - 根节点 - 左子树结点) int LenR = subTreeLen - 1 - LenF; //创建右子树 PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR); } } //后序遍历 void PostOrder(BiTree T){ if(T != NULL){ //访问左子结点 PostOrder(T->lchild); //访问右子结点 PostOrder(T->rchild); //访问根节点 printf("%c",T->data); } } int main(){ while(scanf("%s %s",PreArray,InArray) != EOF){ BiTree T; PreInCreateTree(T,0,0,strlen(InArray)); PostOrder(T); printf(" "); } }