✊✊✊🌈大家好!本篇文章将较详细介绍哈夫曼树的相关内容,并对进行代码实现,展示代码语言为: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