abcdefgh 图6-5 1 棵二叉树
9. 深度为 5 的二叉树至多有 个结点。 A. 16 B. 32 C.31 D.10
10. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数至少有 个。
A.k+1 B.2k C.2k-1 D.2k+1
11. 对含有 B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A.0 B.1 C.2 D.不存在这样的二叉树
1-5 ACDBB 6-10 填空题
1. 有一棵树如图6-7 所示，回答下面的问题：
k1DDCCC
k2k3k4k5k6k7 图6-7 1 棵二叉树
（1）这棵树的根结点是 ； （2）这棵树的叶子结点是 ； （3）结点 k3 的度是 ； （4）这棵树的度为 ；
11
（5）这棵树的深度是 ； （6）结点 k3 的孩子是 ； （7）结点 k3 的双亲结点是 。
2. 深度为 k 的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从 1 开始），则编号最小的叶子结点的编号是 。 答：①2
k?1
②2-1 ③2
kk?2+1
3. 一棵二叉树的第 i（i≥1）层最多有 个结点；一棵有 n（n>0）个结点的满二叉树共有 个叶子和 个非终端结点。 答：① 2
4. 具有n个结点的完全二叉树的深度为 。
5. 哈夫曼树是带权路径度_______的树，通常权值较大的结点离根_______。 ①最短 ②较近
6．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
1.答：① k1 ② k2 k5 k7 k4 ③ 2 ④ 3 ⑤ 4 ⑥ k5，k6 ⑦ k1 2. ① ② ③ 3. ① ② ③ 4.floor(log2n)+1 5. ① ② 6. 先根
例题解析
【例6-1】由如图 6-1 所示的二叉树，回答以下问题。 （1）其中序遍历序列为 ① ； （2）其前序遍历序列为 ② ； （3）其后序遍历序列为 ③ ；
（4）该二叉树的中序线索二叉树为 ④ ； （5）该二叉树的后序线索二叉树为 ⑤ ； （6）该二叉树对应的森林是 ⑥ 。
i?1 ②
2?logn? ③ 2?logn??1
12
abcdgehfi 图6-1 1棵二叉树
解：
① 中序遍历序列为dgbaechif ② 前序遍历序列为abdgcefhi
③ 后序遍历序列为gdbeihfca ④ 该二叉树的中序线索二叉树如图 6.1.1(a)所示 ⑤ 该二叉树的后序线索二叉树如图6-1-1 (b)所示 ⑥ 该二叉树对应的森林如图6-1-2所示
图6-1-1 二叉树的中序线索二叉树和后序线索二叉树
agf
beddhi
图6-1-2 二叉树对应的森林
13
综合题
1．二叉树结点数值采用顺序存储结构，如表6-2所示。
表6-2 二叉树的顺序存储结构
1 e 2 a 3 f 4 5 d 6 7 g 8 9 10 11 12 13 14 15 16 17 18 19 20 c j h i b （1）画出二叉树表示；
（2）写出前序遍历，中序遍历和后序遍历的结果； （3）写出结点值 c 的父结点，其左、右孩子。 解：
（1）该二叉树如图 6-9 所示。
图 6-9 1棵二叉树
（2）本题二叉树的各种遍历结果如下：
前序遍历：eadcbjfghi 中序遍历：abcdjefhgi 后序遍历：bcjdahigfa
（3）c 的父结点为 d，左孩子为 j，没有右孩子。
2．有一份电文中共使用 5 个字符：a、b、c、d、e，它们的出现频率依次为 4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。
14
解：依题意，本题对应的哈夫曼树如图 6-15 所示。
各字符对应的哈夫曼编码如下： a：001 b：10 c：01 d：000 e：11
图6-15 一棵哈夫曼树
3．设给定权集 w={2，3，4，7，8，9}，试构造关于 w 的一棵哈夫曼树，并求其加权路径长度 WPL。
解：本题的哈夫曼树如图 6-16 所示。
15