👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑💻
感兴趣的小伙伴可以点一下订阅、收藏、关注!🚀
谢谢大家!🙏
带权路径长度
结点的 权 :有某种现实含义的数值(如:表示结点的重要性等)
结点的带权路径长度:从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积
树的带权路径长度:树中所有 叶结点 的带权路径长度之和(WPL:Weighted Path Length)
定义
在含有 n 个带权叶结点的二叉树中,其中 带权路径长度(WPL)最小的二叉树 称为 哈夫曼树 ,也称 最优二叉树
哈夫曼树的构造
给定 n 个权值分别为 w 1 , w 2 , . . . , w n w_1,w_2,...,w_n w1,w2,...,wn 的结点,构造哈夫曼树的算法描述如下:
- 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树,构成森林 F
- 构造一个新结点,从F中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和
- 从 F 中删除刚才选出的两棵树,同时将新得到的树加入 F 中
- 重复步骤 2 和 步骤 3 ,直至 F 中只剩下一棵树为止
结论:
- 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大
- 哈夫曼树的结点总数为 2 n − 1 2n-1 2n−1
- 哈夫曼树中不存在度为 1 的结点
哈夫曼编码
固定长度编码:每个字符用相等长度的二进制位表示
可变长度编码:允许对不同字符用不等长的二进制位表示
若没有一个编码是令一个编码的前缀,则称这样的编码是 前缀编码
由哈夫曼树得到 哈夫曼编码 ——字符集中的每个字符作为一个叶子结点,各个字符出现的频度作为结点的权值,根据之前介绍的方法构造哈夫曼树