Skip to content
← 第4章练习:二叉树的结点表

第二问:三种遍历 ​

本题说明

本题分三问,输入用同一种格式:一张二叉树的结点表。第一问在学完二叉树的存储结构之后做,第二问在学完遍历之后做,第三问在学完属性计算之后做。后面的问可以直接使用第一问读入、建树的代码。

输入格式(两问相同)

第一行一个整数 n,表示结点个数,结点编号为 0 到 n−1。

接下来 n 行,每行四项:编号 值 左孩子编号 右孩子编号,没有孩子用 -1 表示。各行的顺序是任意的,不一定按编号排列,第一行也不一定是根。

这张表就是二叉链表,只是把左右孩子的地址换成了编号:编号就是结点在数组里的下标。

数据范围(两问相同)

  • 1 ≤ n ≤ 1000,输入一定是一棵二叉树。
  • 值是一个大写字母。值可以重复,结点靠编号区分。

题目描述 ​

读入结点表,从根结点出发,输出这棵二叉树的先序、中序、后序遍历序列。

输入格式 ​

见本题说明。

输出格式 ​

三行,依次是先序、中序、后序遍历序列。每行输出结点的值,值之间用一个空格隔开。

样例 ​

样例 1
输入
6
0 D -1 -1
1 A 3 2
2 C 4 5
3 B -1 0
4 E -1 -1
5 F -1 -1
输出
A B D C E F
B D A E C F
D B E F C A

输入和第一问的样例 1 相同。B 没有左孩子,中序里 B 排在 D 前面。

样例 2
输入
3
0 C -1 -1
1 B 0 -1
2 A 1 -1
输出
A B C
C B A
C B A

一条只往左走的链,根 A 在最后一行。

提示 ​

遍历要从根开始,根不一定是 0 号结点。找根的办法第一问已经写过了。

C
#include <stdio.h>

int main(void) {
    
    return 0;
}
期望输出
A B D C E F
B D A E C F
D B E F C A