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

selantor

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

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

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

如果可以的话了解的大神顺便清晰地讲一下它如何构造可以吗，我们12号就得考插本的专业课了，我是跨专业的，不知道自己有些理解有没有错误，还希望大家指点一二。。

最佳答案

月排行榜 / 总排行榜

lumber2388779

2017-3-8 14:12: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这个图文并茂

跳转到最佳答案楼层

lumber2388779

以你的图为例子吧
你的图组成树之前的数字是：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这个图文并茂