PTA 7-4 按层遍历二叉树
用先序和中序序列构造一棵二叉树（树中结点个数不超过10个），通过用队记录结点访问次序的方法实现对二叉树进行按层遍历，即按层数由小到大、同层由左到右输出按层遍历序列。
输入格式:
第一行输入元素个数
第二行输入先序序列，以空格隔开
第三行输入中序序列，以空格隔开
输出格式:
输出此二叉树的按层遍历序列，以空格隔开，最后也有一个空格。
输入样例:
5
10 20 40 30 50
20 40 10 50 30
输出样例:
10 20 30 40 50 代码实现：
#include<stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
#include<queue>
using namespace std;
typedef struct node{ int data; struct node *lson,*rson;
} Bnode, *Bptr; Bptr creat(int a[], int b[], int i, int j,int s,int t){ int k;Bptr p;if(i>j)return NULL;p=new Bnode;p->data=a[i];k=s;while((k<=t)&&(b[k]!=a[i])){k++;}if(b[k]!=a[i]){return NULL;}p->lson=creat(a,b,i+1,i+k-s,s,k-1);p->rson=creat(a,b,i+k-s+1,j,k+1,t);return p;
} void anceng(Bptr p){ queue<Bptr> q; if (p != NULL) q.push(p); while(!q.empty()){ Bptr temp = q.front(); q.pop();printf("%d ", temp->data); if(temp->lson!=NULL){ q.push(temp->lson); } if(temp->rson!=NULL){ q.push(temp->rson);} }
} void freeTree(Bptr p){if(p != NULL){ freeTree(p->lson); freeTree(p->rson); free(p); }
} int main(){ Bptr q; int xianxu[10], zhongxu[10], x; scanf("%d", &x); for(int i = 0; i < x; i++){ scanf("%d", &xianxu[i]); } for(int i = 0; i < x; i++){ scanf("%d", &zhongxu[i]); } q = creat(xianxu,zhongxu,0,x-1,0,x-1); anceng(q); freeTree(q); return 0;
}