模板：二叉树的遍历问题。

遍历方法：

前序遍历（pre）：按照根节点->左子树->右子树
中序遍历（in）：按照左子树->根节点->右子树
后序遍历（post）：按照左子树->右子树->根节点
按层次遍历：根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序结点逐个访问。
叶节点遍历

一些问题：

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历。

　　　　前序第一个为根，找到根在中序中的位置tmp，tmp左侧为当前节点左子树，右侧为右子树，继续递归寻找下一个根节点。

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 string in, pre;
 5 void tree(int l1,int r1,int l2,int r2){
 6     int tmp=in.find(pre[l1]);              
 7     if(tmp>l2) tree(l1+1, l1+tmp-l2, l2, tmp-1);              
 8     if(tmp<r2) tree(l1+tmp-l2+1, r1, tmp+1, r2); 
 9     cout<<pre[l1];               
10 }
11 int main(){
12     cin>>pre>>in;                              
13     tree(0,pre.size()-1,0,in.size()-1);   
14     return 0;                         
15 }

　　 2.给出一棵二叉树的中序与后序排列。求出它的先序排列。

　　　　类似于问题1，后序遍历的最后一个为根。

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 string in, post;
 5 void tree(int l1,int r1,int l2,int r2){
 6     if(l1>r1) return;                       
 7     cout<<post[r2];                    
 8     int tmp=l1;                                
 9     while(in[tmp]!=post[r2]) tmp++;    
10     int cnt=tmp-l1;                    
11     tree(l1, tmp-1, l2, l2+cnt-1);              
12     tree(tmp+1, r1, l2+cnt, r2-1);                
13 }
14 int main(){
15     cin>>in>>post;               
16     int n=in.length()-1;                
17     tree(0,n,0,n);   
18     return 0;                         
19 }

　　 3.给出中序和按层遍历的字符串，求该树的先序遍历字符串。

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 string s1, s2;
 5 void tree(int l1,int r1,int l2,int r2){
 6     int i,j;  
 7     for(i=l2; i<=r2; i++){  
 8         int b=0;  
 9         for(j=l1; j<=r1; j++){  
10             if(s2[i]==s1[j]){  
11                 cout<<s1[j];
12                 b=1;  
13                 break;  
14             }  
15         }  
16         if(b) break;  
17     }  
18     if(j>l1) tree(l1,j-1,0,r2); 
19     if(j<r1) tree(j+1,r1,0,r2);          
20 }
21 int main(){
22     cin>>s1>>s2;                              
23     tree(0,s1.size()-1,0,s2.size()-1);   
24     return 0;                         
25 }

"Hello World!"