哈夫曼树的基本概念
哈夫曼树的定义是对一组具有确定权值的叶子节点，选出最小带权路径长度的二叉树为哈夫曼树(WPL最小)，也称最优二叉树
哈夫曼算法的实现
注意：哈夫曼树在构造时选择两个最小的权值点，默认小的在左边大的在右边，但实际上并没有硬性规定，可以互换，对长度没有影响，但本文默认小的在左边大的在右边。
1.对权值节点排序，在n个权值节点中选出两个最小的，这两个节点作为左右子树形成一棵新的二叉树，根节点的值是左右子树权值的加和
2.将原序列中最小的两个权值删除，将新的权值加入到序列中(原最小两个权值的和)，并排序
3.不断重复1和2步骤，直至只剩下一棵树**(结束的表示是序列只剩1个节点值)**，此树为所构造的哈夫曼树
下面用图说明哈夫曼树的构造过程，给定权值1 5 2 6 10 7，要求构造出哈夫曼树
初始状态为
1.将权值进行排序得到1 2 5 6 7 10，选出权值最小的两个节点分别是1和2，将1和2作为左右子树生成一棵二叉树，根节点值为3
2.将最小的两个节点(1,2删除)，将节点3加入到序列中，此时序列为3 5 6 7 10，即
3.由于序列中的所有节点（剩余5个）大于1个，继续循环上述1和2过程，此时序列为3 5 6 7 10，将权值最小的两个节点3和5作为左右子树生成新的一棵二叉树，根节点为3+5=8
4.将3和5节点删除，将节点8加入到序列中，重新排序，此时序列为6 7 8 10，如下图
5.由于并没有消耗完序列中的所有节点（剩余4个）大于1个，继续循环上述1和2过程，此时序列为6 7 8 10，将权值最小的两个节点6和7作为左右子树生成新的一棵二叉树，根节点为6+7=13
6.将6和7节点删除，将节点13加入到序列中，重新排序，此时序列为8 10 13，如下图
7.由于序列中的所有节点（剩余3个）大于1个，继续循环上述1和2过程，此时序列为8 10 13，将权值最小的两个节点8和10作为左右子树生成新的一棵二叉树，根节点为8+10=18
8.将6和7节点删除，将节点18加入到序列中，重新排序，此时序列为13 18，如下图
9.由于序列中的所有节点（剩余2个）大于1个，继续循环上述1和2过程，此时序列为13 18，将权值最小的两个节点13和18作为左右子树生成新的一棵二叉树，根节点为13+18=31
10.将13和18节点删除，将节点31加入到序列中，此时序列为31，如下图
11.此时序列只剩1个元素，循环结束，所生成的树即为哈夫曼树。
哈夫曼编码
在通信传送时，数据表现为0和1的二进制形式。为了提高传输的速度，通常会进行数据压缩。同时，要保证编码不存在二义性。哈夫曼编码符合上述要求，能达到较优的编码方式，其原理就是自底向上构建哈夫曼树。
例：假设某报文由{‘l’,‘m’,‘y’,‘z’,‘j’,‘h’}六个字符组成，每个字符出现的频率分别是{0.24,0.16,0.2,0.08,0.02,0.3},为这6个字符设计哈夫曼编码
数据预处理
首先可以将字符出现的频率转换为整数，即每个概率乘100，得到相应权值
| 字符 | 权值 |
|---|---|
| l | 24 |
| m | 16 |
| y | 20 |
| z | 8 |
| j | 2 |
| h | 30 |
构造哈夫曼树
此时l字符对应权值为24，m字符对应权值为16.等，得到6个节点的权值后，按照上文讲到的方法构造哈夫曼树(不断循环方式1和方式2直至只剩下一棵树)，具体细节不再赘述。
生成的哈夫曼树如下：
按照哈夫曼编码的规则，每个根节点的左子树编码为0 每个根节点的右子树编码为1。
根据上述规则可以生成每个字符(即出现频率的节点 如l为24的节点为01)对应的编码文章来源：https://www.toymoban.com/news/detail-510574.html
| 字符 | 编码 |
|---|---|
| l | 01 |
| m | 101 |
| y | 00 |
| z | 1001 |
| j | 1000 |
| h | 11 |
用哈夫曼编码得到的序列长度应为24 * 2+16 * 3 + 20 * 2 + 8 * 4 + 2 * 4 + 30 * 2 = 236
而利用等长编码由于字符数为6位，需要用3位二进制数表示，因此序列长度为300
可以看到哈夫曼编码的序列明显小于等长编码得到的序列，比例为236/300。文章来源地址https://www.toymoban.com/news/detail-510574.html
到了这里，关于哈夫曼树及哈夫曼编码(考试常考版)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
