内容发布更新时间 : 2024/12/24 3:52:28星期一 下面是文章的全部内容请认真阅读。
(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)它的左、右子树也分别为二叉排序树。