1、哈夫曼树
这里主要讲二叉哈夫曼树，WPL：带权路径长度
计算公式
哈夫曼树就是WPL最小的二叉树，也被称为最优二叉树。
image.png
2、构建哈夫曼树
有N个结点以及对应权值。
2.1 在N个结点中选取两个权值最小的结点作为左右结点。
2.2 以这两个结点的权值之和构建一个新的结点，作为这两个结点的父结点。
2.3 在结点集中删除左右子节点，添加新的父结点。
2.4 重复以上步骤，直至结点集为空，所有结点构成一颗树的叶子结点，哈夫曼树就构建完成了。
步骤1
步骤2
特点
-所有结点都是哈夫曼树的叶子结点。
-权值越小的结点，从根节点到该结点的路径越长。
-N个结点构成哈夫曼树最终有2N-1个结点。
3、哈夫曼编码
为了解决远距离电报通信的数据传输最优化问题。
字符出现频率作为结点权值，出现频率越小，那么编码长度也就越长，可变长度编码。
步骤
3.1 字符出现频率作为权值构建哈夫曼树。
3.2 左子树记0，右子树记1，得到每一个根结点到叶子结点的编码，就是对应字符的编码。
步骤
减少编码长度
优势
4、哈夫曼解码
前缀编码：每一个编码都不是其他编码的前缀。
哈夫曼编码就是前缀编码，不会产生歧义。
对照编码表一一查看即可解码。
