a b c

d e

（2）后序遍历序列为：bdeca （5分）

3. 通信报文中出现的字符A、B、C、D、E，在报文中出现的频率分别为

0.23、0.2、0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。（共14分） 参考答案如下：

为处理方便，关键字都乘以100，为{23，20，32，12，13}

构造哈夫曼树为：（9分,每个结点1分）

0 43 0 20 B 23 A 0 12 D 13 E 1 0 25 1 100 1 57 1 32 C

所以编码为：A：01 B：00 C：11 D：100 E：101 （5分，每个编码1分）

4. 某二叉树结点的中序序列为H，B，C，D，E，F，G，后序序列为B，D，

C，H，F，G，E，请据此画出该二叉树，再给该树加上中序线索。（共15分）

对应的二叉树为：（7分,每个结点1分）

H G E

B D C F 对应中序线索树为：（8分，每条线索1分）

E G H C F B D

5.请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。（10分）

证明：令树中结点总数为N，度为1的结点个数为n1。

则树中结点数满足下列公式：n0+n1+n2=N

从度的角度来考虑，满足下列公式：2n2+n1+1=N 从而得证：n0=n2+1

6.请按照孩子-兄弟表示法，将图1所示树转化为二叉树。（共14分）

E B A C D F

G

解：

图1

E B A C D

F

（每个结点2分）

G

7.设二叉树如图2所示。分别写出它的先序遍历、中序遍历、后序遍历序列。（共15分）

B C D A E F H I J 图2

G

8.

（1）写出如图所示二叉树的中序遍历结果。（8分） （2）画出二叉树的中序后继线索。（10分）

H

D G A C F E B （1）中序遍历结果：ADBCHFEG ——共8分，每个字符1分 （2）二叉树的中序后继线索如图

——共10分，每个后继线索2分

D

A C G H F

9.

已知某二叉树的前序遍历序列为：A B C D E F G和中序遍历序列为：C B E D A F G。请画出该二叉树。

答案如下：

10.

B A F C D G E 已知通信联络中只可能出现A、B、C、D、E、F、G、H共8种字符，其出现次数分别为5，28，7，9，14，23，3，11次。

（1）请画出赫夫曼树（权值小的结点在左边）。（15分） （2）计算该树的带权路径长度。（3分）

答案：

（1）赫夫曼树构造如下。树中结点位置正确者，每个1分，共15分。