给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）
二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
样例输入：
ABC
BAC
FDXEAG
XDEFAG
样例输出:
B C A
X E D G A F 示例代码：
#include <iostream>
#include <string.h>
using namespace std;
typedef struct BinTree
{
char data;
BinTree* lchild;
BinTree* rchild;
} BinTree;
void RebuildTree(BinTree* &Tree,char *pre,char *in,int len)
{
Tree = new BinTree;
if(Tree!=NULL)
{
if(len<=0)//递归截止条件
{
Tree = NULL;
return ;
}
int index = 0;
while(index<len&&*(pre)!=*(in+index))
{
//寻找当前的root结点（包含子树）
index++;
}
Tree->data = *(pre);
RebuildTree(Tree->lchild,pre+1,in,index);//去掉root结点
RebuildTree(Tree->rchild,pre+1+index,in+1+index,len-(index+1));//去掉左边和根节点
}
return ;
}
void PostOrderTravese(BinTree* Tree)
{
//后序遍历输出
if(Tree==NULL)
return;
PostOrderTravese(Tree->lchild);
PostOrderTravese(Tree->rchild);
cout<<Tree->data<<" ";
}
int main()
{
char pre[101]; //string pre;
char in[101]; //string in;
while(cin>>pre>>in)
{
BinTree* tree;
int length = strlen(pre);
RebuildTree(tree,pre,in,length);
PostOrderTravese(tree);
cout<<endl;
}
return 0;
}
查看5道真题和解析