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

第一问:结点信息 ​

本题说明

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

输入格式(两问相同)

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

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

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

数据范围(两问相同)

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

题目描述 ​

读入结点表,找出根结点,求出每个结点的双亲和度,并统计度为 0、1、2 的结点各有几个。

输入格式 ​

见本题说明。

输出格式 ​

共 n + 2 行:

  • 第一行:根结点的编号。
  • 接下来 n 行,按编号从 0 到 n−1,每行输出这个结点的 双亲编号 度。根结点没有双亲,双亲编号输出 -1。
  • 最后一行:n0 n1 n2,即度为 0、1、2 的结点个数。

样例 ​

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

1 号结点 A 没有在任何一行里当过孩子,它是根。B 只有右孩子 D,度为 1。最后一行 3 = 2 + 1,正好是 n₀ = n₂ + 1。

样例 2
输入
4
0 X -1 -1
1 X 0 -1
2 Y -1 -1
3 X 1 2
输出
3
1 0
3 1
3 0
-1 2
2 1 1

根在最后一行。三个结点的值都是 X,只能靠编号分清谁是谁。

样例 3
输入
1
0 A -1 -1
输出
0
-1 0
1 0 0

只有一个结点,它就是根,也是叶子。

提示 ​

一个结点只要在某一行里当过孩子,就不是根。双亲也是这样得来的:读到结点 i 的左孩子是 j,j 的双亲就是 i。

评测只看输出。想把两种链式存储都练到,可以再用 malloc 把这张表建成二叉链表,从根出发通过指针输出同样的信息。

C
#include <stdio.h>

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