当前位置:网站首页 > 技术博客 > 正文

哈夫曼树算法实现



✊✊✊🌈大家好!本篇文章将较详细介绍哈夫曼树的相关内容,并对进行代码实现,展示代码语言为: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. 权值越大的叶子结点越靠近根节点。
  1. 权值越小的叶子节点越远离根节点。
  1. 哈夫曼树并不唯一。
  1. 哈夫曼的子树也是哈夫曼树。
  1. 哈夫曼树无度为1的结点。
  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),采用优先队列堆哈夫曼树构造进行优化,能大大减小所需时间。

  本篇文章将较详细介绍哈夫曼树的相关内容,并对进行代码实现。

  在《数据结构》专栏,会继续更新其他数据结构的学习内容,感兴趣的小伙伴们可以关注数据结构专栏!        博主水平有限,欢迎大家在评论区或者私信留言交流、批评指正!

🚀🚀更新不易,觉得文章写得不错的小伙伴们,点赞评论关注走一波💕💕~~~谢谢啦🙏 🙏🙌 !

版权声明


相关文章:

  • 远程桌面链接服务器2024-11-20 21:01:07
  • 网易游戏测试工资待遇怎么样2024-11-20 21:01:07
  • redis缓存的使用2024-11-20 21:01:07
  • ts vue3.02024-11-20 21:01:07
  • c++中getline函数2024-11-20 21:01:07
  • 病毒分析入门2024-11-20 21:01:07
  • usb协议有哪些2024-11-20 21:01:07
  • 计数排序公式2024-11-20 21:01:07
  • c 数组 指针2024-11-20 21:01:07
  • 全面解析JAVA的注解2024-11-20 21:01:07