http://bbs.freekaoyan.com/viewthread.php?tid=196010
赫夫曼树有些困惑。
我用的是清华严蔚敏的《数据结构》，书中在构建赫夫曼树时第一步并没有排序，而是直接从一组数中选择最小的两个数。做题发现有些元素构建的赫夫曼树有多种方式，不知对不对？
请问赫夫曼树是不是唯一的？
如：2，3，4，5 可构建两种
/14\
/9\ 5
/14\ /5\ 4
/5 \ /9\ 2 3
2 3 4 5
两个图的 WPL都为28 ，都对吗？
---------------------------------
为什么没人回答我啊，高手都那里去了
---------------------------------
这个问题我也研究过，我绝的应该是一样的，但是什么时候用双什么时候用单，我就凭感觉了。子树少时一般用单，多时一般用双。有没有其他的方法我就不知道了，请高手们帮帮忙，让小弟我把这个困惑解决了！
---------------------------------
我是湖北一名大三的学生!我个人认为,赫夫曼树是唯一的.至于你在上面提到的,我想,第一种方法才是对的.你应该漏看了一点.
构造赫夫曼树时,首先将所有的数字按照原顺序编号(仅仅是为了方便,以免弄混了),然后选取两个值最小的相加,将得到的结果重新编号.拿你在上面说的,2，3，4，5的编号应分别为①②③④,然后是①和②相加,结果为5,那么这个5的编号应该是⑤,此时4,5,5的标号分别为③④⑤,再选两个数值最小的相加,应该是③ ④,而不是③ ⑤,因为每次选择时应该先选取序号小的那个.
以上仅为我个人的一点拙见,希望对你有所帮助!
---------------------------------
理论上是一样的 关键判断就是ＷＰＬ 最优化的要求满足基本就ＯＫ
---------------------------------
哈夫曼树是不唯一的。
如果在结合的过程中，被创建的结点与开始给出的一个结点相等，而这个结点又是在下一次创建中最小的两个结点中的一个，这样就会出现两种选择。
比如说2，3，5，4，6
第一次选取2和3，生成结点为5。第二次在剩下的5，4，6和生成的5这四个结点中选取最小的两个4和5，这时因为5，5，4，6中有两个5，所以有两种结合（即2和3结合的那个5可以和4结合，而原来的那个5也可以和4结合）
20 20
9 11 9 11
4 5 5 6 4 5 5 6
2 3 2 3
---------------------------------
不是唯一的,但是只有一个 wpl是最小的
---------------------------------
根据构造哈夫曼树的算法应该是唯一的 搂主最好仔细阅读一下如何构造哈夫曼树
---------------------------------
选WPL最小的,不唯一
---------------------------------
不是唯一的,而且只要按照正确的方法构造出的霍夫曼树wpl是一样的,比如你给的2,4,5,6
就可以是14
/ \
5 9
/ \
4 5
/ \
2 3,也可以是14
/ \
5 9
/ \ / \
2 3 4 5,或者是在同一层的左右兄弟可以交换顺序
