.

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 二叉树对应的森林

Word 资料

.

综合题

1．二叉树结点数值采用顺序存储结构，如表6-2所示。

表6-2 二叉树的顺序存储结构

1 e 2 a 3 f 4 5

6

7

8

9 10

d g c （1）画出二叉树表示；

（2）写出前序遍历，中序遍历和后序遍历的结果； （3）写出结点值 c 的父结点，其左、右孩子。 解：

（1）该二叉树如图 6-9 所示。

11 j 12 13 14 h 15 i 16 17 18 19 20 b

图 6-9 1棵二叉树

（2）本题二叉树的各种遍历结果如下：

前序遍历：eadcbjfghi 中序遍历：abcdjefhgi 后序遍历：bcjdahigfa

（3）c 的父结点为 d，左孩子为 j，没有右孩子。

2．有一份电文中共使用 5 个字符：a、b、c、d、e，它们的出现频率依次为 4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），

Word 资料

.

并求出每个字符的哈夫曼编码。

解：依题意，本题对应的哈夫曼树如图 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 所示。

Word 资料

.

图6-16 一棵哈夫曼树

其加权路径长度 WPL=7×2+8×2+4×3+2×4+3×4+9×2=80

4. 已知一棵二叉树的中序序列为 cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。

解：由后序序列的最后一个结点 a 可推出该二叉树的树根为 a，由中序序列可推出 a的左子树由 cbed 组成，右子树由 hgijf 组成，又由 cbed 在后序序列中的顺序可推出该子树的根结点为 b，其左子树只有一个结点 c，右子树由 ed 组成，显然这里的 e 是根结点，其右子树为结点 d，这样可得到根结点 a 的左子树的先序序列为：bcde；再依次推出右子树的先序序列为：fghij。因此该二叉树如图 6-17所示。

Word 资料