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
#include
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;iif(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"%d",&a[i]);
}
for(int i=0;i"%d",&b[i]);
}
struct Tree * p=build(a,b,n);
levelorder(p);
return 0;
}
谢指点!
#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)
{
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[30];
int front = 0, rear = 0;
q[rear++] = p;
while(front != rear)
{
struct Tree * r = q[front++];
if(r->left) q[rear++] = r->left;
if(r->right) q[rear++] = r->right;
// 根据是否为根节点输出相应的格式
if(front == 1) printf("%d", r->data);
else printf(" %d", r->data);
}
}
}
int main()
{
int n;
scanf("%d", &n);
int a[30], b[30];
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;
}
段错误是C/C++程序编写中常见的错误,在程序运行过程中会出现该错误时,程序的运行会突然停止,经常会让程序员感到十分困惑。在上述代码中,似乎没有明显的语法错误。通常而言,程序出现段错误是由程序运行过程中访问了没有被分配的内存地址所导致的。可能是在程序中具有记忆功能的数组数据类型长度太小,而程序在处理时对数组进行操作而导致的,也可能是程序中的指针没有得到初始化直接使用也会导致程序运行错误。但是如果程序输出的结果和你所预期不符,也可能导致程序出现段错误,在这种情况下,需要仔细地检查程序是否符合了题目要求,或者是否程序本身的逻辑上存在错误。仔细地检查程序常常有助于解决问题。