Question

权值w={5,29,7,8,14,23,3,11},画出哈夫曼树。

权值w={5,29,7,8,14,23,3,11},画出哈夫曼树。为什么答案是图一？图二哪里错了？





Answer 1

权值w={5,29,7,8,14,23,3,11},画出哈夫曼树.

个人认为, 图2的画法有不妥的地方.

问题点就是:
结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?

个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.

分析过程如下:

八个权值从小到大排序是: 3 5 7 8 11 14 23 29

图1 : 哈夫曼树

         N100
      /        \
    N42        N58
   /  \       /  \
  23  N19    29  N29
     /  \       /  \
   11   N8     14  N15
       /  \       /  \
      3    5     7    8

根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
如此类推,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
权值29: 10
权值23: 00
权值14: 110
权值11: 010
权值8 : 1111
权值7 : 1110
权值5 : 0111
权值3 : 0110


图2 : 哈夫曼树

             N100
         /          \
        N58        N42
       /   \      /   \
      N29  29    N19  23
     /  \       /  \
   14   N15    8   11
       /  \
      7   N8
         /  \
        3    5

根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点3的路径长度是5,结点3的带权路径长度是3*5
如此类推,哈夫曼树的带权路径长度(WPL)等于
29*2 +23*2 +14*3 +11*3 +8*3 +7*4 +5*5 +3*5  = 271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
权值29: 01
权值23: 11
权值14: 000
权值11: 101
权值8 : 100
权值7 : 0010
权值5 : 00111
权值3 : 00110


从 WPL 的角度看,图1和图2的WPL都是等于271.

从 哈夫曼编码 的角度看:
图1, 权值29的编码是10, 权值3的编码是0110 
图2, 权值29的编码是01, 权值3的编码是00110

图2的权值29和权值3的编码长度相差大了一点.

相比下,图1的方案更加合适,所以优先选择图1的哈夫曼树.

图1和图2出现编码差异大的主要原因是:
结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?
图1的做法是将新结点N8排在原有结点8的后面,所以结点7与原有结点8先合并.
而图2的做法是新结点将N8排在原有结点8的前面,所以结点7和新结点N8先合并了.

个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.

另外,个人认为,图1的结点11和N8的左右位置互换一下,结点23和N19左右位置互换一下,
这样会更加合适,保证从左到右,结点是从小到大,让最后编码的时候,更加统一.


以下是详细的构建过程:

(1) 从小到大排序 3 5 7 8 11 14 23 29 (这是有序序列)
(2) 每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8,
    取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.
(3) 将新结点N8放入有序序列,保持从小到大排序:
    7 8 N8 11 14 23 29  [注意,新结点N8排在原结点8的后面]
(4) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,
    结点7的数值较小,将结点7作为左分支,结点8就作为右分支.
(5) 将新结点N15放入有序序列,保持从小到大排序:
    N8 11 14 N15 23 29
(6) 重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19,
    N8的数值较小,作为左分支,结点11就作为右分支.
(7) 将新结点N19放入有序序列,保持从小到大排序:
    14 N15 N19 23 29
(8) 重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29,
    结点14的数值较小,作为左分支,N15就作为右分支.
(9) 将新结点N29放入有序序列,保持从小到大排序:
    N19 23 29 N29  [注意,新结点N29排在原结点29的后面]
(10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42,
    N19的数值较小,作为左分支,结点23就作为右分支.
(11)将新结点N42放入有序序列,保持从小到大排序:
    29 N29 N42
(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58,
    结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.
(13)将新结点N58放入有序序列,保持从小到大排序:
    N42 N58
(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100,
    数值较小的N42作为左分支,N58就作为右分支.
    最后得到"哈夫曼树":

              N100
           /       \
          N42      N58
         /   \     /  \
        N19  23   29  N29
       /  \          /  \
      N8  11       14   N15
     /  \              /  \
    3    5            7    8

带权路径长度(WPL):
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2
根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3
根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3
根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4
根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4
根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
所以,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10
从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01
从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110
如此类推,得出所有结点的"哈夫曼编码":
权值29: 10
权值23: 01
权值14: 110
权值11: 001
权值8 : 1111
权值7 : 1110
权值5 : 0001
权值3 : 0000

Answer 2

我觉得你的是对的，哈夫曼树是不唯一的，只要得到的带权路径长度是最小的就没问题，答案是100，你的也是100，我个人认为是正确的。如果我说的不对还请帮忙纠正，一起进步

Answer 3

位肩挑咆难磕睡刀