哈夫曼树
定义
特点
- 没有度为1的结点
- 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树
- 对于同一组权值，可能存在不同构的两课哈夫曼树
构造
每次把权值最小的2科二叉树合并
先把二叉树按权值从小到大排好
然后把权值最小的2给结点并在一起，得到一个新的结点，新结点的权值为2结点和
接下来从新的结点和旧的结点多次重复操作
就剩下2个结点则直接合并
伪代码如下
问题的关键在于如何选取2给最小的值，可用最小堆实现，
把结点的权值构造成一个最小堆，从里面挑2个最小的，并在一起形成一个新的节点，再插入堆
也可以用排序的方法从小到大排行，删除2个小的合在一起，然后把新的节点插入排序好的结点，用堆效率比较高
这种情况就叫做编码的二义性，避免二义性的方法：如何字符的编码都不是另一个字符编码的前缀
保证编码不会出现二义性的方法：用二叉树进行编码
例子
每个字符出现的频率是不一样的，我们可以根据频率，用哈夫曼树构造
例子
