鱼C论坛

 找回密码
 立即注册
查看: 2853|回复: 1

[已解决]我想请问一下哈夫曼树的构造有没有什么硬性要求?

[复制链接]
发表于 2017-3-8 00:48:21 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
今晚同学复习的时候跟我说他看的例题都是像这样一样小的在左边,大的在右边

但是之前我看到有的并没有按照这种方向去写。

想请问哈夫曼树的构造有什么硬性要求吗?

如果可以的话了解的大神顺便清晰地讲一下它如何构造可以吗,我们12号就得考插本的专业课了,我是跨专业的,不知道自己有些理解有没有错误,还希望大家指点一二。。
最佳答案
2017-3-8 14:12:18
本帖最后由 lumber2388779 于 2017-3-8 14:18 编辑

以你的图为例子吧
你的图组成树之前的数字是:2 3 5 7 8 9 11(已排序)
先挑出最小两个 2 3 组合,他们的和是5组成 5->2,3那个
再取出最小的两个 5和7 都不小于5 那与5->2,3就是同一层, 然后同一层3个数取最小两个组合就是10->5,(5->2,3)
然后再从剩余的数取出最小的7,8比10小,那只能比10低一层,组合成15->7,8
再取出最小的两个9,11, 11比10大,比15小,就与15组成26->11,15 而9与10组合成19->10,9
最后将组合的数就是26与19组合成新数45->26,19
权值就是(最初的叶子值)2*4(第4层)+3*4+5*3+7*3+8*3+9*2+11*2=120

参考下http://jingyan.baidu.com/article/380abd0a717c061d90192ca2.html这个图文并茂
QQ图片20170308004528.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-3-8 14:12:18 | 显示全部楼层    本楼为最佳答案   
本帖最后由 lumber2388779 于 2017-3-8 14:18 编辑

以你的图为例子吧
你的图组成树之前的数字是:2 3 5 7 8 9 11(已排序)
先挑出最小两个 2 3 组合,他们的和是5组成 5->2,3那个
再取出最小的两个 5和7 都不小于5 那与5->2,3就是同一层, 然后同一层3个数取最小两个组合就是10->5,(5->2,3)
然后再从剩余的数取出最小的7,8比10小,那只能比10低一层,组合成15->7,8
再取出最小的两个9,11, 11比10大,比15小,就与15组成26->11,15 而9与10组合成19->10,9
最后将组合的数就是26与19组合成新数45->26,19
权值就是(最初的叶子值)2*4(第4层)+3*4+5*3+7*3+8*3+9*2+11*2=120

参考下http://jingyan.baidu.com/article/380abd0a717c061d90192ca2.html这个图文并茂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 23:47

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表