二叉树给出前序中序得到后序遍历（需记忆）
题目描述
二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍
历与中序遍历能够唯一确定后序遍历）。
输入：
两个字符串，其长度 n 均小于等于 26。
第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表
示：A，B，C....最多 26 个结点。
输出：
输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。
样例输入：
ABC
BAC
FDXEAG
XDEFAG
样例输出：
BCA
XEDGAF
#include <stdio.h>
#include <string.h>
struct Node
{ //树结点结构体
Node *lchild; //左儿子指针
Node *rchild ; //右儿子指针
char c; //结点字符信息
}Tree[50]; //静态内存分配数组
int loc; //静态数组中已经分配的结点个数
Node *creat() { //申请一个结点空间 ,返回指向其的指针
Tree[loc].lchild = Tree[loc].rchild = NULL ; //初始化左右儿子为空
return & Tree[loc ++]; //返回指针 ,且loc累加
}
char str1[30] , str2[30]; //保存前序和中序遍历结果字符串
void postOrder(Node * T ) { //后序遍历
if (T -> lchild != NULL ) { //若左子树不为空
postOrder(T -> lchild); //递归遍历其左子树
}
if (T -> rchild != NULL ) { //若右子树不为空
postOrder(T -> rchild ); //递归遍历其右子树
}
printf ("%c" ,T -> c); //遍历该结点 ,输出其字符信息
}
Node *build(int s1,int e1,int s2,int e2) { //由字符串的前序遍历和中序遍历还
原树 ,并返回其根节点 ,其中前序遍历结果为由 str1[s1]到str2[e1]，中序遍历结果为 str2[s2]
到str2[e2]
Node* ret = creat(); //为该树根节点申请空间
ret -> c = str1[s1]; //该结点字符为前序遍历中第一个字符
int rootIdx ;
for (int i = s2;i <= e2;i ++)
{//查找该根节点字符在中序遍历中的位置
if (str2[i] == str1[s1]) {
rootIdx = i;
break ;
}
}
if (rootIdx != s2) { //若左子树不为空
ret -> lchil d = build(s1 + 1,s1 + (rootIdx - s2),s2,rootIdx - 1); //
递归还原其左子树
}
if (rootIdx != e2) { //若右子树不为空
ret -> rchild = build(s1 + ( rootIdx - s2) + 1,e1,rootIdx + 1,e2); //
递归还原其右子树
}
return ret; //返回根节点指针
}
int main () {
while (scanf ("%s" ,str1) != EOF ) {
scanf ("%s" ,str2); //输入
loc = 0; //初始化静态内存空间中已经使用结点个数为 0
int L1 = strlen(str1);
int L2 = strlen(str2); //计算两个字符串长度
Node * T = build(0,L1 - 1,0,L2 - 1); //还原整棵树 ,其根结点指针保存在 T中
postOrder(T); //后序遍历
printf( "\n" ); //输出换行
}
return 0;
}
