给出一个树的中序遍历和先序遍历，求它的后序遍历。
递归求解即可。
先序遍历中的第一个值必为中间结点的值，然后在中序遍历中找到这个值。这个值左边的为左子树的中序遍历，右边为右子树的中序遍历。
先序遍历中，前半部分为左子树的先序遍历，其长度和中序子左子树的长度相同。因此两个子树的中序和先序遍历都可以确定了。
构造出完整的树之后，再后序遍历即可。
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("heritage.in");
ofstream fout("heritage.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
char in_order[27];
char pre_order[27];
struct tree_node{
char value;
tree_node*left,*right;
tree_node(){
left = right = NULL;
}
};
tree_node* build_tree(int in_start,int in_end,int pre_start,int pre_end)
{
tree_node *node = new tree_node;
node->value = pre_order[pre_start];
if(pre_start>pre_end) return NULL;
if(pre_start!=pre_end){
int pos;
for(pos=in_start;pos<=in_end;++pos){
if(in_order[pos]==pre_order[pre_start])
break;
}
node->left = build_tree(in_start,pos-1,pre_start+1,pre_start+pos-in_start);
node->right = build_tree(pos+1,in_end,pre_start+pos-in_start+1,pre_end);
}
return node;
}
void post_traverse(const tree_node*node)
{
if(node==NULL) return;
if(node->left!=NULL){
post_traverse(node->left);
}
if(node->right!=NULL){
post_traverse(node->right);
}
out<<node->value;
}
void solve()
{
in>>in_order;
in>>pre_order;
post_traverse( build_tree(0,strlen(in_order)-1,0,strlen(pre_order)-1) );
out<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}
其实不需要建树，再后序遍历。直接在建树过程中后序输出即可。
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("heritage.in");
ofstream fout("heritage.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
char in_order[27];
char pre_order[27];
char post_order[27];
struct tree_node{
char value;
tree_node*left,*right;
tree_node(){
left = right = NULL;
}
};
void build_tree(int in_start,int in_end,int pre_start,int pre_end)
{
if(pre_start>pre_end) return;
if(pre_start!=pre_end){
int pos;
for(pos=in_start;pos<=in_end;++pos){
if(in_order[pos]==pre_order[pre_start])
break;
}
build_tree(in_start,pos-1,pre_start+1,pre_start+pos-in_start);
build_tree(pos+1,in_end,pre_start+pos-in_start+1,pre_end);
}
out<<pre_order[pre_start];
}
void solve()
{
in>>in_order;
in>>pre_order;
build_tree(0,strlen(in_order)-1,0,strlen(pre_order)-1);
out<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}