給出一個(gè)樹的中序遍歷和先序遍歷，求它的后序遍歷。
遞歸求解即可。
先序遍歷中的第一個(gè)值必為中間結(jié)點(diǎn)的值，然后在中序遍歷中找到這個(gè)值。這個(gè)值左邊的為左子樹的中序遍歷，右邊為右子樹的中序遍歷。
先序遍歷中，前半部分為左子樹的先序遍歷，其長(zhǎng)度和中序子左子樹的長(zhǎng)度相同。因此兩個(gè)子樹的中序和先序遍歷都可以確定了。
構(gòu)造出完整的樹之后，再后序遍歷即可。
#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;
}
其實(shí)不需要建樹，再后序遍歷。直接在建樹過程中后序輸出即可。
#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;
}