给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数
N（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
思路就是先建树,然后遍历找出对应序即可.
(通过三种遍历顺序的特点,对应先找出根节点，然后判断左右子树的结点个数有好多,且分别在那些位置.然后跟着建树就可以了.)
具体看代码注释:
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int mid[50],hou[50];
int n;
struct node{
int l , r;
}a[50]; //存树!.
int build(int la,int ra,int lb,int rb){ //前面两个是中序遍历的左边的位置和右边的位置,后面两个是后序遍历的左右两边的位置.
if(la > ra) return 0;//表示访问到了叶结点了,就不能再访问下去了,否则会出事情.//这个用la也行,lb也行.
int rt = hou[rb];
int p1 = la , p2 ;
while(mid[p1] != rt) p1++;
p2 = p1 - la; //记个数.(即记下左子树有多少个结点,方便后面建树时给定数组一个范围.)
//printf("%d %d %d %d %d %d %d\n",p1,p2,rt,la,ra,lb,rb); //搞不太清楚就把每一步打出来看看.
a[rt].l = build(la,p1-1,lb,lb+p2-1); //根据关系来确定左右子树的个数和是那些.
a[rt].r = build(p1+1,ra,lb+p2,rb-1);
return rt; //返回根节点.
}
//其实只有把第一层建立左右子树关系弄清楚就可以了,剩下的模仿着来写就可以了,如果非要弄清楚每一步怎么来的,就只有把每一步都退出来看了.!
void bfs(int x)
{
queue<int> q;
q.push(x);
int cnt=0;
while(!q.empty()){
int w = q.front();
q.pop();
printf("%d",w);
cnt++;
cnt==n ? printf("\n"):printf(" ");
if(a[w].l != 0){
q.push(a[w].l);
}
if(a[w].r != 0){
q.push(a[w].r);
}
}
}
int main()
{
scanf("%d",&n);
for(int i = 0 ; i < n ; i++)
scanf("%d",&hou[i]);
for(int i = 0 ; i < n ; i++)
scanf("%d",&mid[i]);
printf("\n\n\n");
build(0,n-1,0,n-1); //把相应位置穿进去,开始建树.
printf("\n\n\n");
int root = hou[n-1];
bfs(root);//层序遍历树,然后输出.
}
再附上如果是前序和中序的话:(只需要改点地方就是了,思路不要混乱!)
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int mid[50],qian[50];
int n;
struct node{
int l , r;
}a[50]; //存树!.
int build(int la,int ra,int lb,int rb){ //前面两个是前序遍历的左边的位置和右边的位置,后面两个是中序遍历的左右两边的位置.
if(lb > rb) return 0; //这个用la也行,lb也行.
//printf("%d %d %d %d \n",la,ra,lb,rb);//我原先还是弄错了好久,所以打出来后就可以知道了.
int rt = qian[la];
int p1 = lb , p2 ;
while(mid[p1] != rt) p1++; //统计在中序遍历中的位置.
p2 = p1 - lb; //统计个数,方便接下来的建树.
//printf("%d %d %d \n",p1,p2,rt); //搞不太清楚就把每一步打出来看看.
a[rt].l = build(la+1,la+p2,lb,p1-1); //根据关系来确定左右子树的个数和是那些.
a[rt].r = build(la+p2+1,ra,p1+1,rb);
return rt; //返回根节点.
}
//其实只有把第一层建立左右子树关系弄清楚就可以了,剩下的模仿着来写就可以了,如果非要弄清楚每一步怎么来的,就只有把每一步都退出来看了.!
void bfs(int x)
{
queue<int> q;
q.push(x);
int cnt=0;
while(!q.empty()){
int w = q.front();
q.pop();
printf("%d",w);
cnt++;
cnt==n ? printf("\n"):printf(" ");
if(a[w].l != 0){
q.push(a[w].l);
}
if(a[w].r != 0){
q.push(a[w].r);
}
}
}
int main()//前序加中序.
{
scanf("%d",&n);
for(int i = 0 ; i < n ; i++)
scanf("%d",&qian[i]);
for(int i = 0 ; i < n ; i++)
scanf("%d",&mid[i]);
printf("\n\n\n");
build(0,n-1,0,n-1); //把相应位置穿进去,开始建树.
printf("\n\n\n");
int root = qian[0];
bfs(root); //层序遍历树,然后输出.
}
记住任意两种遍序中必须有中序才能唯一确定一颗二叉树!!否则是不能建起来树的!!!
再附上通过前序和中序输出后序,如果想手敲这个建树过程就看这篇文章,有许多小技巧可以学！
(已知后序和中序,输出前序. 稍微改点地方就是了)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
using namespace std;
const int maxn=1e6;
const int eps=1e-6;
const int inf=1e9;
const ll INF=1e15;
int qian[1005];
int mid[1005];
int n;
struct tree
{
int l,r;
}s[1005];
int bulid(int la,int ra,int lb,int rb) //其他序类似.
{
if(lb>rb) return 0;
//printf("%d %d %d %d \n",la,ra,lb,rb);
int p1=lb,p2; //p1计数器算出左子树的节点个数.然后是给中序用的.
int root=qian[la]; //记住p1,p2的作用和用于那个序!!!
while(root != mid[p1]) p1++;
p2=p1-lb; //p2通过p1算出在前序或后序中左右子树的分界点,然后是给前后序用的.!//记好了才能手敲.
//printf("%d %d\n",p1,p2);
s[root].l=bulid(la+1,la+p2,lb,p1-1);
s[root].r=bulid(la+p2+1,ra,p1+1,rb);
return root;
}
int cnt; //用于控制输出格式
void bianli(int t)
{
if(t){
//前序(printf语句加在这就行了).
bianli(s[t].l);
bianli(s[t].r);
printf("%d",t); //后序
cnt++; //技巧怎样才能最后才输换行符.
cnt==n? printf("\n") : printf(" ") ;
}
}
int main()
{
while(scanf("%d",&n)!=EOF){
CLR(s);
for(int i=0;i<n;i++){
scanf("%d",&qian[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&mid[i]);
}
int rt=bulid(0,n-1,0,n-1);
cnt=0;
bianli(rt);
}
}
