定义
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称之为最优二叉树，也就是哈夫曼树。
特点
- 变长编码，压缩数据，减少数据量大小
- 数据都存储在叶子节点，解码时不会出现重复编码的冲突
- 根据数据的权重(出现频率)来决定编码，进一步压缩数据
使用场景
主要用于文件的不等长编码的无损压缩，如视频、文件等
构建Haffuman树
假如，有一个文件中有一串文本：hello,huffman，接着需要对该文件进行压缩。
在压缩前，文本使用ASCII进行编码，每一个字符都占用1个字节，8bit，那么写入文件后会占用13个字节，共占用104bit。
如果使用Huffuman编码进行压缩的话，会需要这几个步骤：
- 统计字符出现的次数，统计权重
| 字符 | h | f | l | e | o | , | u | m | a | n |
|---|---|---|---|---|---|---|---|---|---|---|
| 次数 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
- 根据权重构建Huffman树
-
从权重最小的开始构建树的叶子节点，即
a与n
构建A与N -
同样再构建权重排序后的最小的叶子节点，即
u与m
构建U与M -
同理，构建
O与,的叶子节点
构建O与, -
接着开始找到权重最小的两个节点，也就是
O与,组成的子树以及E，来构建一个新的子树，然后再根据权重重新排序
构建O与,与E的子树 -
接着按照权重再构建子树，也就是通过后两个子树构建新的子树
构建新子树 -
同理构建
F与L的子树
构建F与L的子树 -
最后，通过一层层子树的堆叠，就变成了以下的样子，而这就是最终的Huffman树
最优二叉树 最终在树的左右子树中，加入
0与1的编码，而对应的编码也就是Huffman编码。
部分编码如下：
| 字符 | A | H | L | M |
|---|---|---|---|---|
| 编码 | 0000 | 11 | 011 | 0011 |
由于所有的字符都在Huffman树的叶子节点上，所以编码与解码不会有冲突。
通过这棵编码树，就可以对文件进行编解码，来压缩与解压文件了。
