20162318 2017-2018-1 《程序设计与数据结构》第9周学习总结

教材学习内容总结

哈夫曼树

1 . 何为Huffman Tree？

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面的图说明：

2 . 如何构建Huffman Tree？

1.遍历森林，从中选出两个最小的节点。2.两个节点相加，将新节点作为它们的根节点3.在森林中删除那两个节点，并将它们的根节点加入森林4.重复上面的步骤用图说明：

3 . 哈夫曼编码（重点）

指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码，如图：

5 .

堆

1 .堆的概念

heep是一颗完全二叉树，其中每一个元素都要大于或小于它的所有孩子

2 . 向堆中添加元素（最大堆）

先将该元素作为叶节点，然后将其向上移动到合适的位置

3 . 从堆中删除最大元素（最大堆）

把最后的叶节点来取代根，然后向下移动到适合它的位置

4 . 堆排序（重点）

由于堆拥有有序特性，so每一次都是删除根节点（最大堆），得到的排序将会是降序

优先队列

优先队列不是FIFO队列。它根据优先级排列元素，而不是根据它们进入队列的次序来排列。

教材学习中的问题和解决过程

• 问题1：堆和二叉查找树的区别
• 问题1解决方案：

二叉查找树：对于每个节点n，n的左子树中包含的元素都小于n中的元素，n的右子树中包含的元素都大于等于n中的元素。堆：其中的每个元素都要大于或小于它的所有孩子

上周考试错题总结

解析：虽然所有节点在完全相同的层次上的树是平衡的，但并不是所有的平衡树都具有这个属性。

结对及互评

本周结对学习情况

堆和哈夫曼树

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）
目标	5000行	30篇	400小时
第一周	0/0	1/1	10/10
第二周	200/200	0/1	18/38
第三周	300/500	2/3	22/60
第五周	632/1132	5/8	30/90
第六周	247/1379	2/10	15/105
第七周	840/2219	2/12	12/117
第九周	578/2787	2/14	13/130

• 计划学习时间:16小时

• 实际学习时间:13小时