数据结构答案

第
7章二叉树


7.1选择题。
（1）前序遍历和中序遍历结果相同的二叉树为（ F ）；前序遍历和后序遍历结果相同的
二叉树为（ B ）。
A．一般二叉树 B．只有根结点的二叉树
C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树
E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树。
（2）以下有关二叉树的说法正确的是（ B ）。
A．二叉树的度为 2 B．一棵二叉树的度可以小于 2
C．二叉树中至少有一个结点的度为 2 D．二叉树中任一个结点的度均为 2
（3）一棵完全二叉树上有 1001个结点，其中叶子结点的个数为（ D ）。
A．250 B．500 C．254 D．501
（4）一棵完全二叉树有 999个结点，它的深度为（ B ）。
A．9 B．10 C．11 D．12
（5）一棵具有 5层的满二叉树所包含的结点个数为（ B ）。
A．15 B．31 C．63 D．32
7.2用一维数组存放完全二叉树： ABCDEFGHI，则后序遍历该二叉树的结点序列为
（ HIDEBFGCA ）。
7.3有 n个结点的二叉树，已知叶结点个数为 n0，则该树中度为 1的结点的个数为
（ n-2n0+1 ）；若此树是深度为 k的完全二叉树，则 n的最小值为（ 2k-1 ）。
7.4设 F是由 T1、T2和 T3三棵树组成的森林，与 F对应的二叉树为 B。已知 T1、T2
和 T3的结点数分别是 n1、n2和 n3，则二叉树 B的左子树中有（ n1-1）个结点，二叉树
B的右子树中有（ n2+n3）结点。
7.5高度为 k的二叉树的最大结点数为（ 2k-1 ），最小结点数为（ k ）。
7.6对于一棵具有 n个结点的二叉树，该二叉树中所有结点的度数之和为（ n-1 ）。
7.7已知一棵二叉树如图 7.12所示，试求：
（1）该二叉树前序、中序和后序遍历的结果；
【答】：前序： abdgecfh；中序： dgbcafhc；后序：gdebhfca
（2）该二叉树是否是满二叉树？是否是完全二叉树？
【答】：该二叉树不是满二叉树，也不是完全二叉树。
（3）将它转换成对应的树或森林；
【答】：
图7.12 一棵二叉树



（4）这棵二叉树的深度为多少？（4）这棵二叉树的深度为多少？
【答】：该二叉树的深度为
4。

（5）试对该二叉树进行前序线索化；
【答】：
abcdefgh`
（6）试对该二叉树进行中序线索化。
【答】：
7.8试述树和二叉树的主要区别。

【答】：

（1）树的结点个数至少为
1，而二叉树的结点个数可以为
0。
（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为
2。
（3）树分为有序树与无序树，而二叉树一定是有序树，它的结点有左，右之分。
7.9试分别画出具有
3个结点的树和具有
3个结点的二叉树的所有不同形态。
【答】：
三个结点的树有两种形态：
三个