2009西电计算机研究生复试上机题（2）

题目描述

已知某二叉树的先序序列和中序序列，编程计算并输出该二叉树的后序序列。

输入有多组数据，每组分为两行输入，第一行表示指定二叉树的先序序列，第二行表示该二叉树的中序序列，序列元素均为大写英文字符，表示二叉树的结点。

输出

对于每组数组，在一行上输出该二叉树的后序序列。

样例输入

ABDGCEFH
DGBAECHF

样例输出

GDBEHFCA

提示 [+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

来源

2009年西电计算机研究生复试上机题

这道题是考先序 中序 求后序。如果看后序 中序 求先序 看我的博文：点击打开链接

/*********************************  *    日期：2013-3-11 *    作者：SJF0115  *    题号: 天勤OJ 题目1218: Problem D *    来源：http://acmclub.com/problem.php?id=1218 *    结果：AC  *    来源：2009年西电计算机研究生复试上机题  *    总结： **********************************/ #include<stdio.h>#include<string.h>#include<malloc.h>//二叉树结点  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("\n");}}