5.2　习题解答

1. 在一棵度为3的树中，度为1的结点数为 2个，度为2的结点数为1个，度为3的结点数为2个，则度为0的结点数为( )个。

A. 4　　　B. 5　　　C. 6　　　D. 7

【解答】 度为0的结点数为：n₀=1+( i-1)n_i=1+(1-1)·2+(2-1)·1+(3-1)·2=6，故选C。

2. 在一棵二叉树的中序遍历序列中，根结点的左边( )。

A. 只有左子树上的部分结点　　　C. 只有右子树上的部分结点

B. 只有左子树上的全部结点　　　D. 只有右子树上的全部结点

【解答】 根据二叉树中序遍历的定义：先遍历根结点的左子树，然后访问根结点，最后遍历根结点的右子树。故选B。

3. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是( )，层次遍历序列是( )。

① FEGHDCB　　　　　② EFGHBCD　　　　③ BCDEFGH

④ EFBGCHD　　　　　⑤ FEGBHDC　　　　⑥ BECFGDH

【解答】 由前序序列可知，二叉树的根结点为B，最后的叶结点为H，而后序遍历中根结点必定排在最后，因此使用“排除法”，第一空选①；而层次遍历序列中最后一个元素必定是最后一个结点，即H，因此第二空只能在③和⑥中选择，又由中序序列可知左分支有两个结点F和E，再由前序序列可知左分支的根结点为E，所以层次遍历序列的前两个元素为BE，因此再次使用“排除法”，第二空选⑥。

当然也可以利用前序遍历序列和中序遍历序列确定(画出)二叉树，然后再写出后序遍历序列和层次遍历序列。

4. 二叉树经过某种顺序线索化后，每个结点都有( )。

A. 指向其前驱的线索　　　　　C. 指向其前驱和后继的线索

B. 指向其后继的线索　　　　　D. 以上都不对

【解答】 二叉树经过某种顺序线索化后，每个结点都有指向其前驱和后继的指针或线索。故选C。

5. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为( )。

A.n-1　　 B.

C.　　D.

【解答】 在构造度为m的哈夫曼树的过程中，每次把m个子结点合并为一个父结点(第一次可能合并少于m个子结点)，每次合并减少m-1个结点，从n个叶结点减少到最后只剩下一个父结点，共需次合并，每次合并增加一个非叶节点。故选C。

由此也可以看到：度为2的哈夫曼树不存在度为1的结点；m阶(m＞2) 哈夫曼树(最优归并树)至多存在一个度为k(1≤k＜m)的结点。

6. 下列说法中正确的是( )。

A. 树的前根遍历序列与其对应的二叉树的前序遍历序列相同

B. 树的层次遍历序列与其对应的二叉树的中序遍历序列相同

C. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同

D. 以上说法都正确

【解答】 根据树转换成对应的二叉树的规则，根结点的第一个孩子作为它的左孩子L，这个左孩子的第一个右兄弟作为L的右孩子，因此，只有前序遍历的次序保持不变。而树的后根遍历序列与其对应的二叉树的中序遍历序列相同。故选A。

7. 一棵124个叶结点的完全二叉树最多有( )个结点。

A. 247　　B. 248　　C. 249　　D. 25l

【解答】 由完全二叉树的性质可知，它的最后一层h(1≤h)层上的结点全部是叶结点且叶结点的个数t满足：2^h-2＋l≤t≤ 2^h-1。

将t＝124代入上式，解得：h=8

则该二叉树一共有8层，它的总结点个数为2⁰＋2¹＋…＋2⁶＋124＝251。故选D。

8. 一棵完全二叉树第6层有7个结点，则共有( )个结点，其中度为1的结点有( )个，度为0的结点有( )个，编号最大的非叶结点是( )，编号最小的叶结点是( )。

【解答】 一棵完全二叉树除去最底层结点，则是一棵满二叉树，而一棵5层的满二叉树有2⁵-1=31个结点，因此共有31+7=38个结点，最底层的结点数是奇数，因此度为1的结点有1个，度为0的结点数为38/2=19，度为2的结点数为19-1=18，编号最大的非叶结点是38/2=19，编号最小的叶结点是19+1=20。

9. 一棵完全二叉树有200个结点，则度为1的结点有( )个，度为0的结点有( )个，度为2的结点有( )个。

【解答】 度为1的结点数为(200+1) mod 2=1，度为0的结点数为200/2=100，度为2的结点数为100-1=99。

10. 设高度为H(H＞0)的二叉树上只有度为0或2的结点，则该二叉树包含的结点个数不少于( )。

【解答】

设二叉树的结点个数为n，则

(1) 当H＝1时，二叉树只有一个根结点，n＝1。

(2) 当H＞1时，二叉树结点最少时是第2层到第H-1层都是一个叶结点，另一个是度为2的结点；而第H层是2个叶结点。

因此，结点个数n＝2·(H-2+1)+1＝2H-1。

11. 一棵满二叉树，包含n个结点，深度为h，则用h表示n的表达式为( )。

【解答】 根据二叉树的性质2：深度为k的二叉树中至多含有 2^k-1 个结点 (k≥1)，因此对于满二叉树，有n=2^h-1(h≥1)。

12. 如果一棵二叉树的前序序列为abcde，中序序列为cdbea，则它的后序序列是( )。

【解答】 根据二叉树的前序序列abcde和中序序列cdbea，可以推出，根结点为a，且根结点只有左子树，没有右子树。a的左子树的根结点为b，结点b的左子树包括结点c、d(其中c是下一级子树的根结点，d是c的右孩子)，b的右子树包括结点e。由此画出这棵二叉树如图5-1所示，所以后序序列是：dceba。

图　5-1

13. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根( )。

【解答】 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

14. 由树转换成二叉树，其根结点的右子树总是( )。

【解答】 由树转换成二叉树时，树的根结点的第一个孩子成为它的左孩子，而根结点的其他孩子依次成为左孩子的右孩子，因此根结点的右子树总是空的。

15. 将下面的树(如图5-2所示)转换为二叉树并画出来。

图5-2

图5-3

【解答】 根据树转换为二叉树的步骤即可画出，如图5-3所示。

16. 由如图5-4所示的二叉树，回答以下问题：

图5-4

(1) 写出前序遍历序列，中序遍历序列和后序遍历序列。

(2) 画出该二叉树的中序线索二叉树。

(3) 画出该二叉树对应的森林。

【解答】

(1) 前序遍历序列，中序遍历序列和后序遍历序列分别为：abdgcefhi，dgbaechif，gdbeihfca

(2) 中序线索二叉树如图5-5所示。

图5-5

(3) 对应的森林如图5-6所示。

图5-6

17. 由二叉树的前序遍历和后序遍历序列能否唯一地确定这棵二叉树?

【解答】 两棵形状不同的二叉树如图5-7所示，它们的前序遍历序列都是abc，后序遍历序列都是cba，分别对应相同。因此由二叉树的前序遍历和后序遍历序列不能唯一地确定这棵二叉树。

图5-7

18. 利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树?

【解答】

因为一棵树的先根次序遍历的结果与其对应二叉树表示的前序遍历结果相同，树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同，而根据二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树，所以，利用树的先根次序遍历结果和后根次序遍历结果能够唯一地确定一棵树。

19. 采用二叉链表的形式存储二叉树，编写一个算法判定两棵二叉树是否相似。所谓两棵二叉树S和T相似，要么它们都为空或都只有一个根结点，要么它们的左右子树均相似。

【解答】

判断两棵二叉树是否相似的过程，实际上是对这两棵二叉树同时进行前序遍历的过程。很自然地采用递归算法来描述，具体实现如下：

20. 假定用于通信的电文由8个字母A，B，C，D，E，F，G，H组成，各字母在电文中出现的概率为0.04，0.05，0.07，0.08，0.09，0.12，0.25，0.3，试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点。

【解答】 8个字母所对应的权值取为对应的出现概率乘100，即取为(4，5，7，8，9，12，25，30)，且n=8。按照左分支权值小于右分支权值的限制得到哈夫曼树如图5-8所示。

图5-8

将哈夫曼树的左分支标0而右分支标1，得到各字母的哈夫曼编码如下所示。

A：0000　　B：0001　　C：1010　　D：1011

E：001　　F：100　　　G：01　　　H：11

若使用0～7的二进制表示可得到对应编码如下：

A：000　　B：001　　C：010　　D：011

E：100　　F：101　　G：110　　H：111

WPL=(0.04+0.05+0.07+0.08)·4+(0.09+0.12)·3+(0.25+0.3)·2=2.69，即采用哈夫曼编码时的平均编码长度。

而采用0～7的二进制编码时，平均编码长度为3。

故采用哈夫曼编码可以节省码长，但采用哈夫曼编码的编码和解码比直接采用二进制编码要复杂些。