习题解答
4．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是 B 。 A．无左、右孩子 B．有左孩子，无右孩子 C．有右孩子，无左孩子 D．有左、有孩子 5．深度为6的二叉树，最多可以有 A 个结点。 A．63 B．64 C．127 D．128 6．在一棵非空二叉树的中序遍历序列里，根结点的右边 D 结点。 A．只有左子树上的部分 B．只有左子树上的所有 C．只有右子树上的部分 D．只有右子树上的所有 7．在任何一棵二叉树的各种遍历序列中，叶结点的相对次序是 A 。 A．不发生变化 B．发生变化 C．不能确定 D．以上都不对 8．权值为1、2、6、8的四个结点，所构造的哈夫曼树的带权路径长度是 D 。 A．18 B．28 C．19 D．29 9．一棵二叉树度2的结点数为7，度1的结点数为6。那么它的叶结点数是 C 。 A．6 B．7 C．8 D．9 10．在一棵二叉树中，第5层上的结点数最多是 C 个。 A．8 B．15 C．16 D．32
三、问答
1．试问满二叉树与完全二叉树之间有何关系？ 答：由满二叉树与完全二叉树的定义可知，满二叉树一定是一棵完全二叉树，但完全二叉树却不一定是一棵满二叉树。如果一棵二叉树不是完全二叉树，那么它绝对不可能是一棵满二叉树。这就是满二叉树与完全二叉树之间的关系。 2． 请画出由3个结点构成的所有二叉树，它们的高度分别是多少？ 答：大小为3的不同的二叉树共有5种，如下图所示。
其中，4棵树的高度为2，1棵树的高度为1。 3．一棵高度为3的满二叉树有多少个叶结点？有多少个度为2的结点？总共有多少个结点？ 答：有23=8个叶结点，有度为2的结点23-1=7个，总共有23+1-1=24-1=15个结点。 4．有人说，任何一棵非空满二叉树，它的叶结点数等于其分支结点数加1。这样的一个结论正确吗？请说明理由。（提示：利用性质5-3） 答：在我们介绍的二叉树性质中，只有性质5-3是涉及叶结点数与（度为2的）分支结点数的关系的。对于满二叉树来说，所有的分支结点都是度为2的结点。因此，正好可以直接利用性质5-3得出所需要的结论。所以，此人说的结论是完全正确的。 5．有人说，有一棵结点数为n>1的二叉树，只包含有一个叶结点。这可能吗？如果可能的话，这样一棵二叉树应该是个什么样子呢？ 答：这是完全可能的，这种二叉树是从根结点开始只有左子树，或只有右子树的单支二叉树，如图所示。
- 21 -
习题解答
6．试问，什么样的二叉树其先序遍历序列与中序遍历序列相同？ 答：先序遍历序列与中序遍历序列相同的二叉树，或是空二叉树，或是任一结点都没有左孩子的非空二叉树。
7．分别写出如图5-32所示二叉树的先序、中序、后序遍历序列。
图5-32 二叉树示例
答：先序遍历序列为：A-B-C-D-F-G-H-E，中序遍历序列为：B-A-D-G-F-H-C-E，后序遍历序列为：B-G-H-F-D-E-C-A。
四、应用 1．对一个二叉树进行顺序存储，各结点的编号及数据如表所示： 编号i 数据x 1 A 2 B 3 C 4 D 5 E 7 F 10 G 11 H 试画出对应的二叉树，并给出先序、中序、后序遍历该二叉树后，所得到的各种结点序列。 答：对应的二叉树如图所示。
其先序遍历序列是：A-B-D-E-G-H-C-F；中序遍历序列是：D-B-G-E-H-A-C-F；后许遍历序列是：D-G-H-E-B-F-C-A。 2．已知中序遍历序列为：A-B-C-E-F-G-H-D，后序遍历序列为：A-B-F-H-G-E-D-C。试画出这棵二叉树。 答：这棵二叉树如应用题2答案图所示。 3．已知前序遍历序列为：A-B-C-D-E-F，中序遍历序列为：C-B-A-E-D-F。试画出这棵
- 22 -
习题解答
二叉树。 答：这棵二叉树如应用题3答案图所示。 4．若一棵二叉树的左、右子树均有3个结点，其左子树的先序遍历序列与中序遍历序列相同，右子树的中序遍历序列与后序遍历序列相同。请画出这棵二叉树。 答：这棵二叉树如应用题4答案图所示。
5．理解算法5-10。在图5-25(b)的基础上，进行下一次组合。试给出第2次组合后数组的情形，以及那时二叉树的样子。 答：第2次组合后数组的情形如下图(a)所示，那时二叉树的样子如下图(b)所示。
6．权值序列为：10、16、20、6、30、24，请用图示来表达构造一棵哈夫曼树的全过程。 答：构造这棵哈夫曼树的全过程如下所示。
- 23 -
习题解答
7．一棵有11个结点的二叉树的顺序存储情况如表所示，序号3的结点是根结点。画出该二叉树，并给出它的先序、中序、后序遍历序列（其中“^”表示空）。 序 号 Lchild Data Rchild 1 6 M ^ 2 ^ F ^ 3 7 A ^ 4 ^ K 9 5 8 B ^ 6 ^ L 10 7 5 C 4 8 ^ R 11 9 2 D ^ 10 ^ S ^ 11 ^ E ^ 答：二叉树如图所示，先序遍历序列为：A-C-B-R-S-E-D-F-M-L-K，中序遍历序列为：R-B-S-C-E-A-F-D-L-K-M，后序遍历序列为：R-S-B-E-C-F-K-L-M-D-A。
第6章习题解答
一、填空
1．树中结点的度，是指结点拥有 子树 的个数。 2．树中除根结点外，其他结点有且只有 一个 前驱结点，但可以有 零个或多个 后继结点。 3．树中一个结点的 直接后继 ，或一个结点 子树的根结点 ，被称作是该结点的孩子结点。 4．树中一个结点的子树中的任何结点，都被称作是该结点的 子孙 结点。 5．树中有 同一双亲 的结点，被互称为兄弟结点。 6．所谓结点的深度，即是指该结点位于树的 层次 数。 7．双亲位于树中相同层次上的结点，互称为 堂兄弟 结点。 8．在数据结构中，把n（n≥0）棵互不相交的树的集合称为 森林 。 9．在如图6-21所示的树中，，结点H的祖先是 A、D、G 。
图6-21 树示例 图6-22 树示例
10．在树中，一个结点的孩子个数，称为该结点的 度 。
11．一棵树的形状如图6-22所示。它的根结点是 A ，叶结点是 E、G、I、J、K、L、- 24 -