题意：已知中序遍历和后序遍历得出层序遍历
思路：先将中序遍历和后序遍历还原出树，在bfs打印出来。
后续遍历是左右根，所以最后一个是根，由根再到中序遍历中寻找左右子树的元素。利用递归的方法还原出树。树是用结构体数组保存，用链表应该也行。
1 #include <iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<string> 5 #include<cstring> 6 #include<vector> 7 #include<queue> 8 using namespace std; 9 const int N = 50; 10 int hou[N]; 11 int zhong[N]; 12 struct node 13 { 14 int l,r; 15 }a[N]; 16 int n; 17 //la,ra是中序遍历 lb,rb是后序遍历 18 int creat(int la,int ra,int lb,int rb) 19 { 20 if(la > ra)return 0; 21 int root = hou[rb],p1,p2; 22 p1 = la; 23 while(zhong[p1]!=root)p1++;//找根节点 24 p2 = p1-la;//p2是左子树的个数 25 a[root].l=creat(la,p1-1,lb,lb+p2-1); 26 a[root].r=creat(p1+1,ra,lb+p2,rb-1); 27 return root; 28 } 29 void bfs() 30 { 31 queue<int>q; 32 vector<int>v; 33 q.push(hou[n-1]); 34 while(!q.empty()) 35 { 36 int w = q.front(); 37 q.pop(); 38 if(w==0) 39 { 40 break; 41 } 42 v.push_back(w); 43 if(a[w].l!=0)q.push(a[w].l); 44 if(a[w].r!=0)q.push(a[w].r); 45 } 46 for(int i = 0; i < n; i ++) 47 { 48 if(i == 0) 49 printf("%d",v[i]); 50 else 51 printf(" %d",v[i]); 52 } 53 } 54 int main() 55 { 56 scanf("%d",&n); 57 for(int i = 0; i < n; i ++) 58 { 59 scanf("%d",&hou[i]); 60 } 61 for(int i = 0; i < n; i ++) 62 { 63 scanf("%d",&zhong[i]); 64 } 65 creat(0,n-1,0,n-1); 66 bfs(); 67 return 0; 68 }