广州大学松田学院7数据结构复习题-树-参考答案

答：恢复的二叉树为：

B A C E F D G H I 其层次遍历序列为：E B F A D H C G I

8． 已知一棵二叉树结点的先序遍历序列为：EBADCFHGJ，中序遍历序列为：DEBAFCHG，试恢复该二叉树，并写出它的后序遍历的序列。 解：恢复的二叉树

E

B F

H A D

G C I

后序遍历序列：A C D B G I H F E

9． 已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的前序遍历的序列。 解：

A

21

B DG E H C F I J 前序遍历的序列：A B D E G H J C F I

10． 对于算术表达式（A+B*C/D）*E+F*G，画出标识符树，并求它们的后缀表达式。 解： +

* *

+ E FG

A *

B /

C D

后缀表达式：A B C D / * + E * F G * +

11． 给定一个权集W={4，5，7，8，20，12，2}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。 解：

58

2335

20 12 15 11

68 5 7

2 4

WPL=(12+20)*2+(5+7+8)*3+(2+4)*4=148

12． 给定一个权集W={7，19，2，6，32，3，21，10}，试画出相应的哈夫曼树，并计算其带权路径长度WPL。

100解：

（1）

4060

21 19 28 32 11 17 5 6 7 10 2 3

（2） WPL＝ (19+21+32)* 2+ (6+7+10) 4+ (2+3) *5=144+92+25=261

22