习题解答
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 -
习题解答
N、O、P、Q、R ，这棵树的度是 3 ，这棵树的深度是 4 ，结点F的孩子结点是 J、K ，结点G的父结点是 C ，结点 M、H、D、A 是结点R的祖先。
二、选择
1．已知一棵单右支的二叉树，如下左图所示。把它还原成森林，应该是 D 。
A．
B．
C．
D．
2．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的先序遍历是对Bt的 A 。 A．先序遍历 B．中序遍历 C．后序遍历 D．无法确定 3．将一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的 B 。 A．先序遍历 B．中序遍历 C．后序遍历 D．无法确定
4．设森林F中有3棵树，依次有结点n1、n2、n3个。把该森林转换成对应的二叉树后，该二叉树的右子树上的结点个数是 D 。
A．n1 B．n1+n2 C．n3 D．n2+n3
5．设有由三棵树T1、T2、T3组成的森林，其结点个数分别为n1、n2、n3。与该森林相应的二叉树为Bt。则该二叉树根结点的左子树中应该有结点 A 个。 A．n1-1 B．n1 C．n1+1 D．n1+n2 6．现有一棵度为3的树，它有两个度为3的结点，一个度为2的结点，两个度为1的结点。那么其度为0的结点的个数应该是 C 。 A．5 B．8 C．6 D．9 注意：有n个结点的树，树中所有结点的度之和为n-1。现在这棵树应该满足条件： n-1 = 2*3 + 1*2 + 2*1 = 10 这表示该树共有11个结点（加上一个根结点）。在11个结点里，减去度为3、2、1的结点数5，剩下的就是度为0的结点。所以，该树有叶结点6个。 7．一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有 B 个结点。 A．n-2 B．n-1 C．n+1 D．n+2 8．一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的右子树上共有 A 个结点。 A．0 B．n C．n+1 D．n+2 9．下列说法中，正确的是 A 。 A．树的先序遍历序列与其对应的二叉树的先序遍历序列相同 B．树的先序遍历序列与其对应的二叉树的后序遍历序列相同 C．树的后序遍历序列与其对应的二叉树的先序遍历序列相同 D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同
三、问答
1． 如图6-23所示的两棵树是一样的吗？为什么？
答：从图6-23(a)知，该树的根结点为A，下面有两棵子树，其中的一棵子树是最小树，只有根结点为B；另一棵子树的根结点为C，下面又有一棵最小子树，它的根结点为D。
从图6-23(b)知，该树的根结点也是A，它的下面也有两棵子树，这两棵子树的构成也与图6-23(a)里的相同。因此如果把树的子树视为是无序的，那么该图所展示的两棵树是一
- 25 -