.
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 资料
相关推荐：
loading