在大学中学习计算机专业的 学生都会接触到 一种算法叫做哈夫曼树,在一些计算机等级认证中也会用到,很多人不会构造哈夫曼树,今天月下教给大家怎么构建(感谢网友的提醒 错误已经更正)
工具/原料
纸和笔
方法/步骤
1
哈夫曼树,类似于算法中的二叉树,说白了哈夫曼树就是一种二叉树,只是是一种最优二叉树。我们准备一组数以 1,7,3,4,9,8为例子吧,请忽略12
2
第一步,我们对这一组数字进行排序。规则是从小到大排列。排列之后的顺序是 1,3,4,7,8,9,请忽略12
3
第二步就是 在这些数中 选择两个最小的数字(哈夫曼树是从下往上排列的)写在纸上。如下图所示
4
用一个类似于树杈的“树枝”连接上两个最小的数。在顶点处计算出这两个数字的和 并写在上面。然后再比较剩下的数字和这个和的大小,再取出两个最小的数字进行排列
5
如果两个数的和正好是下一步的两个最小数的其中的一个那么这个树直接往上生长就可以了。如果这两个数的和比较大不是下一步的两个最小数的其中一个那么,就并列生长,如下图所示
6
类似于步骤四。我们继续用倒V型的树杈,向上延伸。
7
算出来最后一个结果 就证明我们的哈夫曼树构建成功了。一个节点只能生出两个“枝桠”和数据结构中的“树”不同
END注意事项
如有错误请及时联系(评论或私信)我改正
更多计算机专业的经验请关注我
希望可以帮到你
温馨提示:经验内容仅供参考,如果您需解决具体问题(尤其法律、医学等领域),建议您详细咨询相关领域专业人士。免责声明:本文转载来之互联网,不代表本网站的观点和立场。如果你觉得好欢迎分享此网址给你的朋友。转载请注明出处:https://www.baikejingyan.net/af56dVwdsBA5YA14B.html