Question

对于给定的一组权值W=｛7，2，8，4，16，3，9｝构造出哈夫曼树。并计算带权路径！

Answer 1

7个权值是 7  2  8  4  16  3  9

(1) 从小到大排序 2 3 4 7 8 9 16 (这是有序序列)
(2) 每次提取最小的两个结点,取结点2和结点3,组成新结点N5,其权值=2+3=5,
    取数值较小的结点作为左分支,结点2作为左分支,而结点3就作为右分支.
(3) 将新结点N5放入有序序列,保持从小到大排序:
    4 N5 7 8 9 16
(4) 重复步骤(2),提取最小的两个结点,结点4与N5组成新结点N9,其权值=4+5=9,
    结点4的数值较小,作为左分支,N5就作为右分支.
(5) 将新结点N9放入有序序列,保持从小到大排序:
    7 8 9 N9 16  [注意:新结点N9排在原有结点9的后面]
(6) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,
    结点7的数值较小,作为左分支,结点8就作为右分支.
(7) 将新结点N15放入有序序列,保持从小到大排序:
    9 N9 N15 16
(8) 重复步骤(2),提取最小的两个结点,结点9与N9组成新结点N18,其权值=9+9=18,
    结点9作为左分支,N9就作为右分支.
(9) 将新结点N18放入有序序列,保持从小到大排序:
    N15 16 N18
(10)重复步骤(2),提取最小的两个结点,N15与结点16组成新结点N31,其权值=15+16=31,
    N15的数值较小,作为左分支,结点16就作为右分支.
(11)将新结点N31放入有序序列,保持从小到大排序:
    N18 N31
(12)重复步骤(2),提取剩下的两个结点,N18与N31组成新结点N49,其权值=18+31=49,
    数值较小的N18作为左分支,N31就作为右分支.
    最后得到"哈夫曼树":

            N49
       /           \
      N18          N31
     /  \         /  \
    9   N9      N15  16
       /  \     /  \
      4   N5   7    8
         /  \   
        2    3

带权路径长度(WPL):
根结点N49到结点16的路径长度是2,结点16的带权路径长度是16*2
根结点N49到结点9的路径长度是2,结点9的带权路径长度是9*2
根结点N49到结点8的路径长度是3,结点8的带权路径长度是8*3
根结点N49到结点7的路径长度是3,结点7的带权路径长度是7*3
根结点N49到结点4的路径长度是3,结点4的带权路径长度是4*3
根结点N49到结点3的路径长度是4,结点3的带权路径长度是3*4
根结点N49到结点2的路径长度是4,结点2的带权路径长度是2*4
所以,哈夫曼树的带权路径长度(WPL)等于
16*2 + 9*2 + 8*3 + 7*3 + 4*3 + 3*4 + 2*4 = 127


附:

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N49到结点16,连续经历两次右分支,编码就是11
从根结点N49到结点9,连续经历两次左分支,编码就是00
从根结点N49到结点8,先经历右分支,再左分支,最后右分支,编码就是101
如此类推,可以得出所有的结点的 哈夫曼编码:
权值16: 11
权值 9: 00
权值 8: 101
权值 7: 100
权值 4: 010
权值 3: 0111
权值 2: 0110