外观
本题说明
本题分三问,输入用同一种格式:一张二叉树的结点表。第一问在学完二叉树的存储结构之后做,第二问在学完遍历之后做,第三问在学完属性计算之后做。后面的问可以直接使用第一问读入、建树的代码。
输入格式(两问相同)
第一行一个整数 n,表示结点个数,结点编号为 0 到 n−1。
接下来 n 行,每行四项:编号 值 左孩子编号 右孩子编号,没有孩子用 -1 表示。各行的顺序是任意的,不一定按编号排列,第一行也不一定是根。
这张表就是二叉链表,只是把左右孩子的地址换成了编号:编号就是结点在数组里的下标。
数据范围(两问相同)
读入结点表,求出整棵树的高度,以及以每个结点为根的子树的高度。
高度的算法和属性计算那一节相同:空树的高度是 0,只有一个结点的树高度是 1。
见本题说明。
共 n + 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 -13
1
3
2
2
1
1输入和第一问的样例 1 相同。叶子 D、E、F 的高度是 1;B 和 C 的高度是 2;根 A 的高度是 3,也就是整棵树的高度。
3
0 C -1 -1
1 B 0 -1
2 A 1 -13
1
2
3一条只往左走的链,根 A 在最后一行。
整棵树的高度就是根的那一棵子树的高度。从根做一次 Depth,每个结点的高度在合上来的时候记下来,就全有了,不必对每个结点各算一遍。
#include <stdio.h>
int main(void) {
return 0;
}
3 1 3 2 2 1 1