哈夫曼树这样构造对吗,

2025-04-13 18:26:25
推荐回答(1个)
回答1:

个人认为,这样构造的哈夫曼树欠妥,"结点8和结点11"放在"结点6和7"的右边比较合适.

分析过程如下:

五个权值是 11 8 6 2 5

(1) 从小到大排序 2 5 6 8 11 (这是有序序列)
(2) 每次提取最小的两个结点,取结点2和结点5,组成新结点N7,其权值=2+5=7,
    取数值较小的结点作为左分支,结点2作为左分支,而结点5就作为右分支.
(3) 将新结点N7放入有序序列,保持从小到大排序:
    6 N7 8 11 
(4) 重复步骤(2),提取最小的两个结点,结点6与N7组成新结点N13,其权值=6+7=13,
    结点6数值较小,作为左分支,而N7就作为右分支.
(5) 将新结点N13放入有序序列,保持从小到大排序:
    8 11 N13
(6) 重复步骤(2),提取最小的两个结点,结点8与结点11组成新结点N19,其权值=8+11=19,
    结点8的数值较小,作为左分支,结点11就作为右分支.
(7) 将新结点N19放入有序序列,保持从小到大排序:
    N13 N19
(8) 重复步骤(2),提取剩下的两个结点,N13与N19组成新结点N32,其权值=13+19=32,
    数值较小的N13作为左分支,N19就作为右分支.
    最后得到"哈夫曼树":

          N32
       /       \
      N13     N19 
     /  \     /  \
    6   N7   8   11
       / \
      2   5


哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
得出所有结点的"哈夫曼编码":
权值11: 11
权值8 : 10
权值6 : 00
权值5 : 011
权值2:  010


哈夫曼树的带权路径长度是:
11*2 + 8*2 + 6*2 + 5*3 + 2*3 = 71