内容发布更新时间 : 2024/12/24 0:20:06星期一 下面是文章的全部内容请认真阅读。

(2) 后序序列和中序序列相同：空树或缺右子树的单支树； (3) 先序序列和后序序列相同：空树或只有根结点的二叉树。

12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树。 答：这棵二叉树为:

13. 分别写出图2中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。

答：先序遍历序列:ABDGCEHF 中序遍历序列:DGBAEHCF 后序遍历序列:GDBHEFCA

14. 给定权值(7,18,3,32,5,26,12,8)，构造的哈夫曼树。 答：哈夫曼树为:

15. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10，试为这8个设计哈夫曼编码。 答：哈夫曼树为:

在上述哈夫曼树的每个左分支上标以0，右分支上标以1，并设这8个字母分别为A、B、C、D、E、F、G和H，则它们的哈夫曼树为分别为:

A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：0001

16. 画出无向图G1的邻接矩阵和邻接表示意图，并写出每个顶点的度。

答：（1）邻接矩阵:

（2）邻接链表：

（3）每个顶点的度：

顶点 度

V1 3 V2 3 V3 2

V4 3 V5 3

17. 画出有向图G2的邻接矩阵、邻接表和逆邻接表示意图，并写出每个顶点的入度和出度。

答：（1）邻接链表：

（2）逆邻接链表：

（3） 顶点 入度 出度 V1 3 0

V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 3

18. 对应图G3，写出从v1出必的深度优先遍历序列和广度优先遍历序列各三个。

答：深度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2

广度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V5

19. 何谓二叉排序树?

答：一棵二叉排序树(又称二叉查找树)或者是一棵空树，或者是一棵同时满足下列条件的二叉树：

(1)若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。

(2)若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。

(3)它的左、右子树也分别为二叉排序树。