各章节复习题树结构.pdfVIP

填空

1、在结点个数为n(n1)的各棵树中，高度最小的树的高度是（2），高度最大的树的高度是

（n）。

解：题目要求是树，并且结点个数大于1，所以最大高度n，最小高度2。

k-1k

2、深度为k的完全二叉树，结点数至少有（2）个，至多有（2-1）。

解：深度为k的完全二叉树，结点数至少比深度为k-1的满二叉树多一个，所以是2k-1个，

k

至多与深度为k的满二叉树结点个数相同，即2-1。

3、具有n个结点的二叉链表表示的二叉树中，一共有（2n）个指针域，其中只有（n-1）个

用来指向结点的左右孩子，其余的（n+1）个指针域为NULL。

解：二叉链表中，每个结点有2个指针域，所以n个结点有2n个指针域。

二叉树中只可能包含度为0（即没有分支，也就是2个指针域都为NULL）的结点n0，

度为1（即只有1个分支，也就是有1个指针域为NULL）的结点n1，度为2（即有2个分

支，也就是2个指针域都不为NULL）的结点n2。所以空指针域的个数为：2n0+n1。由于

n0+n1+n2=n，n2=n0-1，所以2n0+n1=n+1。

4、具有3个结点的二叉树有（5）种不同形态。



分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

树二叉树

5、具有n个结点的完全二叉树，按层次编号（根结点为1号），则分支结点编号最大的序号

是（n/2下取整），编号最小的序号是（1），叶子结点编号最大的序号是（n），编号最小的

序号是（n/2上取整）。

解：完全二叉树：只可能包含度为0的结点n0，度为1的结点n1（由于对于深度为k的完

全二叉树，前k-1层是满二叉树，第k层必须向左充满，所以度为1的结点最多只能有1

个，即n1取值为0或者1），度为2的结点n2。由于n0+n1+n2=n，n2=n0-1，所以：

n0（n+1-n1）/2。即n/2上取整。

6、任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为

（n-2m+1）个。

解：n0=n2+1;n=n0+n2+n1

7、设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子

结点的个数是（8）个。

解：n=n0+n1+n2