已知中序和後序，求前序

例子，後序周遊為 gbdehfca，中序周遊為 dgbaechf 

後序周遊中的最後一個元素是根節點，a，然後查找中序中a的位置 

把中序周遊分成 dgb a echf，而因為節點個數要對應 

後序周遊分為 gbd ehfc a，gbd為左子樹，ehfc為右子樹，這樣又可以遞歸計算了

最後形成的二叉樹如下圖檔所示：

具體代碼如下：

遞歸：

[cpp]  view plain copy print ?

1. #include<iostream.h>  
2. #include<string.h>  
3. #include<stdlib.h>  
4. #define MAX 20   
5. typedef struct tnode   
6. {  
7.        char data;  
8.        struct tnode *lchild;  
9.        struct tnode *rchild;  
10. } *bt;  
11. void in_post_to_bt(char *in,char *post,int len,bt &T)   
12. {  
13.        int k;  
14.        if(len<=0)  
15.        {  
16.               T=NULL;  
17.               return;  
18.        }  
19.        for(char *temp=in;temp<in+len;temp++)   
20.               if(*(post+len-1)==*temp)  
21.               {  
22.                      k=temp-in;    
23.                      T=(bt)malloc(sizeof(struct tnode));  
24.                      T->data =*temp;  
25.                      break;  
26.               }  
27.        in_post_to_bt(in,post,k,T->lchild );   
28.        in_post_to_bt(in+k+1,post+k,len-k-1,T->rchild );   
29. }  
30. void in_visit(bt T)  
31. {  
32.        if(T)  
33.        {  
34.               in_visit(T->lchild );  
35.               cout<<T->data ;  
36.               in_visit(T->rchild );  
37.        }  
38. }  
39. void post_visit(bt T)  
40. {  
41.        if(T)  
42.        {  
43.               post_visit(T->lchild );  
44.               post_visit(T->rchild );  
45.               cout<<T->data ;  
46.        }  
47. }  
48. main()  
49. {  
50.        char in[MAX+1],post[MAX+1];  
51.        cout<<"輸入中序序列：";  
52.        cin>>in;  
53.        cout<<"輸入後序序列：";  
54.        cin>>post;  
55.        bt T;  
56.        int len_in=strlen(in),len_post=strlen(post);  
57.        if(len_in<=MAX&&len_post<=MAX)  
58.               in_post_to_bt(in,post,len_in,T);  
59.        cout<<endl<<"輸出中序序列：";  
60.        in_visit(T);  
61.        cout<<endl<<"輸出後序序列：";  
62.        post_visit(T);  
63.        cout<<endl;  
64. }  

原文位址：http://blog.csdn.net/wuchuanpingstone/article/details/6860453