① ②
1 A 2 B 3 4 5 E F G H I C D 6 7 J
8 解： ① ②
1
2 3 4 5 6
8 7 （5）把下列森林转换为二叉树
① ② A F
B C D G E 解： A B F C G H
E DI
K J （6）把下列二叉树还原为森林
46
A B E C F H DJ G I ③ H I J K
解：还原后的二叉树为：
① ② ③ A E
（7）某二叉树的结点数据采用顺序存储，其结构如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B B C DF H I I A B F E G C D H G ① 画出该二叉树（3分）
② 写出按层次遍历的结点序列（2分）
解：
B 层次遍历的结点序列：E A F D H C G I B （8）某二叉树的存储如下： lchild data rchild 1 0 J 0 2 0 H 0 3 2 F 0 4 3 D 9 5 7 B 4 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 A D C G E F H I 其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为
47
数据域。
① 画出该二叉树（3分）
② 写出该树的前序遍历的结点序列（2分） 解：
J 前序遍历的结点序列：A B C E D F H G I J
（9）给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
254060082833E H C F I B D G A 55
解：
中序遍历序列：55 40 25 60 28 08 33 54 中序线索二叉树：
554028256008330543054
（10）画出表达式：-A+B-C+D 的标识符树，并求它们的后缀表达式。 解：
48
ˉ 0 A ˉ + B+ D C 后缀表达式：0 A – B + C – D +
（11）画出表达式：（A+B/C-D）*（E*（F+G））的标识符树，并求它们的后缀表达式。 解：
A B ˉ + / C DE F * * + G 后缀表达式：A B C / + D – E F G + * *
（12）对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。 解：
后缀表达式：A B C D / * + E * F G * +
（13）给定一个权集W={4,5,7,8,6,12,18}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。
49
+ * + A B C * / D E F* G 解：4 5 6 7 8 12 18
9 13
17 25
35
2512 6 13 7 84 60 35 17 9 5 18 60
WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159
（14）给定一个权集W={3,15,17,14,6,16,9,2}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。
解：
2 3 6 9 14 15 16 17
5 29 33
11
20
49
82
WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229
（15）假设用于通信的电文仅由A、B、C、D、E、F、G 8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。 解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：（左子为0，右子为1。） 100
0 0 0 0 1 82 3316 17 9 5 2 320 49 29 15 11 146 字母编号 401 0 0 对应编码 1010 00 10000 1001 11 10001 01 1011 出现频率 7 19 2 6 32 3 21 10 601 A B C D E D E F 19 21 11 5 1 2 328 1 17 32 1 0 1 7 10
六．算法设计题
6 50