05-5.5.1 哈夫曼树

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> [e-mail]

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

带权路径长度

结点的 权 ：有某种现实含义的数值（如：表示结点的重要性等）
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
树的带权路径长度：树中所有 叶结点 的带权路径长度之和（WPL：Weighted Path Length）

定义

在含有 n 个带权叶结点的二叉树中，其中 带权路径长度（WPL）最小的二叉树 称为 哈夫曼树 ，也称 最优二叉树

哈夫曼树的构造

给定 n 个权值分别为 $w_1,w_2,...,w_n$ 的结点，构造哈夫曼树的算法描述如下：

1. 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F
2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和
3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中
4. 重复步骤 2 和 步骤 3 ，直至 F 中只剩下一棵树为止

结论：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
2. 哈夫曼树的结点总数为 $2n-1$
3. 哈夫曼树中不存在度为 1 的结点

哈夫曼编码

固定长度编码：每个字符用相等长度的二进制位表示
可变长度编码：允许对不同字符用不等长的二进制位表示
若没有一个编码是令一个编码的前缀，则称这样的编码是 前缀编码
由哈夫曼树得到 哈夫曼编码 ——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树