前言
- 哈夫曼树的定义、特点、构造
- 哈夫曼编码
哈夫曼树定义
假设有n个权值w1—wn，构造有n个叶子的二叉树，每个叶子的权值是这n个权值之一；这样的二叉树有很多种，其中必有一个或多个的带权路径长度WPL是最小的，这种二叉树称为最优二叉树或哈夫曼树
以下二叉树的权值路径长度：WPL=7x3+6x3+4x3+1x3=36
并非最小WPL，那么怎样构造最小WPL的二叉树，别急接着往下看！
哈夫曼树的特点
特点
没有度为1的结点
n个叶子结点的哈夫曼树共有2n-1个结点
任意非叶子结点的左右子树交换之后仍然是哈夫曼树（只要不改变叶子结点的位置即可）
哈夫曼树的构造
构造哈夫曼树的步骤
将w1-wn看作带有n棵树的森林，且每棵树仅有一个结点
在森林中选出两个根结点权值最小的树合并，作为新树的左或右子树，且新树的根结点权值为左右子树根结点的权值之和
删掉合并前的两棵树，添加新合成的树
重复上述两个步骤，直到只剩一棵树为止，此树即为哈夫曼树
举例说明
- 如下图有一个含四棵树的森林：
- 先选取权值最小的两个树 1和2，并合并结点权值相加，删除合并前的两棵树，添加合并后的树
- 合并根结点权值为3和3的两个树，得到根结点权值6的树：
- 合成根结点权值为6和5的两个树，得到根结点权值11的树：
哈夫曼编码
哈夫曼编码的意义
在远程通讯中，为了使由二进制表示的字符串报文在网络中传播更快，可以采用哈夫曼编码尽可能缩短字符串编码的长度
哈夫曼编码又是前缀无关编码，可以保证在长度不等的编码中，任一字符的编码都不是另一个字符编码的前缀
比如以下的编码方式中，0000能编译出三种字符串，这是绝对不允许的！而哈夫曼编码可以避免这种情况，如何避免的？还请看哈夫曼的编码方式~
编码步骤
- 统计每个字符在文件中出现的平均概率
- 将每个字符的概率作为权值，以权值越大的叶子离根越近，路径也越短的特点，构造哈夫曼树
- 在哈夫曼树的每个分支标记：结点左分支为0，右分支为1；再将每个路径上的标记连起来，作为该叶子代表的字符编码
举例说明
- 现有A、B、C、D四种字符，其出现频率为{5，2，1，3}
- 对其进行哈夫曼编码可得：
总结
本文主要介绍了哈夫曼树的定义、特点以及构造；哈夫曼编码
文章到这结束啦，感谢阅读~
如果文章的论述或代码等出现错误，欢迎前来指正！
如果你觉得文章写的还不错，记得点赞收藏评论三连~ ❤
