题目：树的遍历
思路：
（1）分别用中序和后序利用递归建树；
（2）按层输出的话用bfs即可。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define ms(x) memset(x,0,sizeof(x)) using namespace std; const int maxn = 35; int lch[maxn],rch[maxn],amid[maxn],rear[maxn],n; int build(int l1,int r1,int l2,int r2){//递归建树 l1,r1代表后序的左右值，l2,r2代表中序的 if(l1 > r1) return 0;//叶子节点 int root = rear[r1];//后序的最后一个值为根 int p = 0; for(int i=l2;i<=r2;i++){if(amid[i] != root)p++;else break;}//从中序中找根的位置 lch[root] = build(l1,l1+p-1,l2,l2+p-1);//分别将中序和后序的左子树存放到左子树数组中 rch[root] = build(l1+p,r1-1,l2+p+1,r2);//分别将中序和沟洫的右子树存放在右子树数组中 return root;//返回根结点 } void bfs(int start){//bfs按层输出 queue<int>Q; Q.push(start); while(!Q.empty()){ int cur = Q.front();Q.pop();//每次将根输出 printf("%d",cur); if(lch[cur]) Q.push(lch[cur]);//将当前层的左值入队 if(rch[cur]) Q.push(rch[cur]);//将当前层的右值入队 if(!Q.empty()) printf(" "); } printf("\n"); } int main() { while(~scanf("%d",&n)){ for(int i=0;i<n;i++) scanf("%d",&rear[i]); for(int i=0;i<n;i++) scanf("%d",&amid[i]); ms(lch);ms(rch); build(0,n-1,0,n-1); bfs(rear[n-1]); } return 0; }
