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分。