【原】7-2 树的遍历 (25分)

文章目录

7-2 树的遍历 (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

题解

首先创建树，编写create函数，根据中序遍历和后序遍历的特点创建原本的二叉树，最后进行层序遍历的函数编写，输出结果。后续遍历的最后一个值为根节点，得到根节点后可以利用中序遍历将原来的后续遍历和中序遍历分布划分为两部分，一部分是左子树的后序遍历和中序遍历，另一部分是右子树的后序遍历和中序遍历。

代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

int N = 0;
int PreOrder[33] = { '\0' };// 存储中序遍历
int PostOrder[33] = { '\0' };// 存储后序遍历

// 结点结构体
typedefstruct node
{
int num;
node* left;
node* right;
}node;

struct node *create(int pos[], int pre[], int n);
void sequence(node *T);//层序排序输出

int main()
{
node *T = NULL;
scanf("%d", &N);
int i = 0;
for (i = 0; i < N; i++)
scanf("%d", &PostOrder[i]);
for (i = 0; i < N; i++)
scanf("%d", &PreOrder[i]);
T = create(PostOrder, PreOrder, N);
sequence(T);

return 0;
}

// 层序遍历
void sequence(node *T)
{
struct node *p[33], *q;
int f = 0, r = 0;
int count = 0;
if (T)
{
p[r++] = T;
while (f != r)
{
// 队头不等于队尾时
q = p[f++];// 出队
printf("%d", q->num);
count++;// 计数输出空格
if (count < N)
{
printf(" ");
}
if (q->left)// 左树不为空，入队
p[r++] = q->left;
if (q->right)// 右树不为空，入队
p[r++] = q->right;
}
}
}

// 后序遍历:看根节点
// 中序遍历:左右子树长度

struct node *create(int pos[], int pre[], int n)
{
int i = 0, k = 0, root = 0;
if (n == 0)
{
return NULL;
}
struct node *T;
T = (node *)malloc(sizeof(struct node));
if (T == NULL)//分配结点内存及判断是否成功
return NULL;

root = pos[n - 1];//根节点就是后序遍历的最后一位
T->num = root;
// 通过中序遍历确认左右子树 的长度
for (int i = 0; i < n; i++)
{
if (pre[i] == root)
{
k = i;
break;
}
}
//递归左右子树 找当前结点的左右子树
T->left = create(pos, pre, k);
T->right = create(pos + k, pre + k + 1, n - k - 1);

return T;
}