外观
本题说明
本题分三问,输入用同一种格式:一张二叉树的结点表。第一问在学完二叉树的存储结构之后做,第二问在学完遍历之后做,第三问在学完属性计算之后做。后面的问可以直接使用第一问读入、建树的代码。
输入格式(两问相同)
第一行一个整数 n,表示结点个数,结点编号为 0 到 n−1。
接下来 n 行,每行四项:编号 值 左孩子编号 右孩子编号,没有孩子用 -1 表示。各行的顺序是任意的,不一定按编号排列,第一行也不一定是根。
这张表就是二叉链表,只是把左右孩子的地址换成了编号:编号就是结点在数组里的下标。
数据范围(两问相同)
读入结点表,找出根结点,求出每个结点的双亲和度,并统计度为 0、1、2 的结点各有几个。
见本题说明。
共 n + 2 行:
双亲编号 度。根结点没有双亲,双亲编号输出 -1。n0 n1 n2,即度为 0、1、2 的结点个数。6
0 D -1 -1
1 A 3 2
2 C 4 5
3 B -1 0
4 E -1 -1
5 F -1 -11
3 0
-1 2
1 2
1 1
2 0
2 0
3 1 21 号结点 A 没有在任何一行里当过孩子,它是根。B 只有右孩子 D,度为 1。最后一行 3 = 2 + 1,正好是 n₀ = n₂ + 1。
4
0 X -1 -1
1 X 0 -1
2 Y -1 -1
3 X 1 23
1 0
3 1
3 0
-1 2
2 1 1根在最后一行。三个结点的值都是 X,只能靠编号分清谁是谁。
1
0 A -1 -10
-1 0
1 0 0只有一个结点,它就是根,也是叶子。
一个结点只要在某一行里当过孩子,就不是根。双亲也是这样得来的:读到结点 i 的左孩子是 j,j 的双亲就是 i。
评测只看输出。想把两种链式存储都练到,可以再用 malloc 把这张表建成二叉链表,从根出发通过指针输出同样的信息。
#include <stdio.h>
int main(void) {
return 0;
}
1 3 0 -1 2 1 2 1 1 2 0 2 0 3 1 2