Free考研资料

标题: 请问赫夫曼树是不是唯一的？ [打印本页]

作者: xjxxzx 时间: 07-9-29 11:24
标题: 请问赫夫曼树是不是唯一的？
赫夫曼树有些困惑。
我用的是清华严蔚敏的《数据结构》，书中在构建赫夫曼树时第一步并没有排序，而是直接从一组数中选择最小的两个数。做题发现有些元素构建的赫夫曼树有多种方式，不知对不对？
请问赫夫曼树是不是唯一的？

如：2，3，4，5 可构建两种
                                                                                       /14\
                                                                                    /9\    5
               /14\                                                          /5\ 4
         /5 \       /9\                                                 2    3
      2    3    4 5

两个图的 WPL都为28  ，都对吗？

作者: xjxxzx 时间: 07-9-30 08:06
为什么没人回答我啊，高手都那里去了

作者: yehmily 时间: 07-9-30 21:59
提示: 作者被禁止或删除内容自动屏蔽

作者: hzq123 时间: 07-10-1 08:20
提示: 作者被禁止或删除内容自动屏蔽

作者: n1m234 时间: 07-10-1 22:49
理论上是一样的　关键判断就是ＷＰＬ　最优化的要求满足基本就ＯＫ　

作者: djjkmoo 时间: 07-10-14 13:11
哈夫曼树是不唯一的。
如果在结合的过程中，被创建的结点与开始给出的一个结点相等，而这个结点又是在下一次创建中最小的两个结点中的一个，这样就会出现两种选择。
比如说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

作者: wzhun168 时间: 07-10-14 15:25
不是唯一的,但是只有一个 wpl是最小的

作者: ForStream 时间: 07-10-16 23:40
提示: 作者被禁止或删除内容自动屏蔽

作者: 111111 时间: 07-10-19 00:10
提示: 作者被禁止或删除内容自动屏蔽

作者: 王兔子 时间: 07-10-21 22:16
提示: 作者被禁止或删除内容自动屏蔽

作者: 九天飞鹏 时间: 07-10-29 00:30
提示: 作者被禁止或删除内容自动屏蔽

作者: cskiller0824 时间: 07-10-30 10:27
提示: 作者被禁止或删除内容自动屏蔽

作者: diego66 时间: 07-11-1 15:42
提示: 作者被禁止或删除内容自动屏蔽

作者: aleclee0826 时间: 07-11-8 16:47
提示: 作者被禁止或删除内容自动屏蔽

作者: cppsoldier2006 时间: 07-11-8 17:23
提示: 作者被禁止或删除内容自动屏蔽

作者: jzs 时间: 07-11-13 09:43
提示: 作者被禁止或删除内容自动屏蔽

作者: diego66 时间: 07-11-13 17:19
提示: 作者被禁止或删除内容自动屏蔽

作者: hyx1114qiang 时间: 07-12-25 20:39
提示: 作者被禁止或删除内容自动屏蔽

作者: zhuqi 时间: 08-3-31 09:05
值最小就好了，树不唯一

作者: ddkx111 时间: 08-6-12 07:07
提示: 作者被禁止或删除内容自动屏蔽

作者: 525626 时间: 08-6-12 19:42
不是唯一的，[s:9]

欢迎光临 Free考研资料 (http://bbs.freekaoyan.com/)