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

第三问:树的高度 ​

本题说明

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

输入格式(两问相同)

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

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

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

数据范围(两问相同)

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

题目描述 ​

读入结点表,求出整棵树的高度,以及以每个结点为根的子树的高度。

高度的算法和属性计算那一节相同:空树的高度是 0,只有一个结点的树高度是 1。

输入格式 ​

见本题说明。

输出格式 ​

共 n + 1 行:

  • 第一行:整棵树的高度。
  • 接下来 n 行,按编号从 0 到 n−1,每行输出以这个结点为根的子树的高度。

样例 ​

样例 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
输出
3
1
3
2
2
1
1

输入和第一问的样例 1 相同。叶子 D、E、F 的高度是 1;B 和 C 的高度是 2;根 A 的高度是 3,也就是整棵树的高度。

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

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

提示 ​

整棵树的高度就是根的那一棵子树的高度。从根做一次 Depth,每个结点的高度在合上来的时候记下来,就全有了,不必对每个结点各算一遍。

C
#include <stdio.h>

int main(void) {
    
    return 0;
}
期望输出
3
1
3
2
2
1
1