✊✊✊🌈大家好！本篇文章将较详细介绍哈夫曼树的相关内容，并对进行代码实现，展示代码语言为：C++代码 😇。
🎡导航小助手🎡
✨一文搞懂哈夫曼树、代码实现及优化（C++版）✨
首先，哈夫曼树是最优二叉树，其定义为：给定n个权值作为n个叶子节点，构造一颗二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。
下图就是一颗哈夫曼树：
1) 路径和路径长度
定义: 在一棵树中，从一个结点往下可以达到的孩子或者孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
例子: 图1中，170和130的路径长度是1，70和60的路径长度是2，40和20的路径长度是3。
2)结点的权及带权路径长度
定义:若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
例子: 节点40的路径长度是3，它的带权路径长度= 路径度*权 = 3* 40 = 120.
3)树的带权路径长度
定义: 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
例子: 示例中，树的WPL= 1* 170 + 2*70 + 3*40 + 3*20 = 170 + 140 + 120 + 60 = 490。
：
- 权值越大的叶子结点越靠近根节点。
- 权值越小的叶子节点越远离根节点。
- 哈夫曼树并不唯一。
- 哈夫曼的子树也是哈夫曼树。
- 哈夫曼树无度为1的结点。
- 有n个叶子结点的哈夫曼树，总结点数为2n-1。
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 W1、W2、 ...wn，哈夫曼树的构造规则为:
1.将w1、w2、...，wn看成是有n 棵树的森林;
2.在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和;
3.从森林中删除选取的两棵树，并将新树加入森林;
4.重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树
1️⃣ 首先封装好列表类treeNode或者说定义结构体treeNode，包含了权值和左右两个孩子的指针。
2️⃣ 哈夫曼树的构造
3️⃣ 计算WPL-叶子结点的带权路径长度之和
🌻效果展示：
💻：
哈夫曼树在构建过程中，需先进行两轮排序，选取最小的两棵树作为左、右子树。前文利用sort函数直接进行两轮排序，时间复杂度为O(n^2)，我们可以采用优先队列来进行优化。
优先级队列的自定义排序的代码实现如下所示：
🍓
🍓将函数修改如下：
优先队列的底层是堆，其时间复杂度为O(2logn)，采用优先队列堆哈夫曼树构造进行优化，能大大减小所需时间。
本篇文章将较详细介绍哈夫曼树的相关内容，并对进行代码实现。
在《数据结构》专栏，会继续更新其他数据结构的学习内容，感兴趣的小伙伴们可以关注数据结构专栏！ 博主水平有限，欢迎大家在评论区或者私信留言交流、批评指正！
🚀🚀更新不易，觉得文章写得不错的小伙伴们，点赞评论关注走一波💕💕~~~谢谢啦🙏 🙏🙌 ！
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/15571.html