7-1 树的遍历
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数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<stdio.h>
#include<stdlib.h>
struct Tree
{
int data;
struct Tree * left;
struct Tree * right;
};
struct Tree * build(int a[],int b[],int n);
void levelorder(struct Tree * p);
struct Tree * build(int a[],int b[],int n)
{
if(n<=0)return NULL;
struct Tree * p=(struct Tree *)malloc(sizeof(struct Tree));
p->data=a[n-1];
p->left=p->right=NULL;
int i;
for(i=0;i<n;i++)
{
if(b[i]==a[n-1]) break;
}
p->left=build(a,b,i);
p->right=build(a+i,b+i+1,n-i-1);
return p;
}
void levelorder(struct Tree * p)
{
if(p)
{
struct Tree * q[100];
struct Tree * r;
int front=0;
int rear=0;
q[rear++]=p;
while(front!=rear)
{
r=q[front++];
if(r==p)printf("%d",p->data);
else printf(" %d",p->data);
if(p->left)q[rear++]=p->left;
if(p->right)q[rear++]=p->right;
}
}
}
int main()
{
int n;
scanf("%d",&n);
int a[100];
int b[100];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
}
struct Tree * p=build(a,b,n);
levelorder(p);
return 0;
}
谢指点!