L2-006 树的遍历 （25 分）
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
作者: 陈越
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
根据给定序列建出二叉树，然后进行层序遍历。
#include<bits/stdc++.h>
#define MAX 125
using namespace std;
struct Node{ //二叉树建立
int x,l,r;
}tree[MAX];
int h[MAX],z[MAX];
int c;
int find(
int h[],
int z[],
int len){
//找中序的父节点
for(
int i=
0;i<len;i++
){
if(z[i]==h[len-
1]){
return i;
}
}
}
int build(
int h[],
int z[],
int len){
//建树
if(len<=
0)
return -
1;
int k=
find(h,z,len);
c++
;
int f=
c;
tree[f].x=
z[k];
tree[f].l=
build(h,z,k);
tree[f].r=build(h+k,z+(k+
1),len-(k+
1));
return f;
}
void bfs(
int x){
//层序遍历
int f=
0,i;
queue<
int>
q;
q.push(x);
while(q.size()){
int x=
tree[q.front()].x;
int l=
tree[q.front()].l;
int r=
tree[q.front()].r;
if(f==
0) f=
1;
else printf(
" ");
printf("%d",x);
if(l>-
1) q.push(l);
if(r>-
1) q.push(r);
q.pop();
}
}
int main()
{
int n,i,j;
scanf("%d",&
n);
for(i=
0;i<n;i++
){
scanf("%d",&
h[i]);
}
for(i=
0;i<n;i++
){
scanf("%d",&
z[i]);
}
c=
0;
build(h,z,n);
bfs(1);
return 0;
}
转载于:https://www.cnblogs.com/yzm10/p/10498905.html
