个人认为,这样构造的哈夫曼树欠妥,"结点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