一份电文中有6种字符:A,B,C,D,E,F,它们的出现频率依次为16,5,9,3,30,1计算其带权路径长度WPL
时间: 2024-05-28 20:09:21 浏览: 231
字符串中不同字符出现的频度
5星 · 资源好评率100%
根据哈夫曼树算法,将出现频率作为权值构造哈夫曼树,为了使WPL最小,将出现频率较少的字符放在较深的分支上,出现频率较多的字符放在较浅的分支上。于是按照以下步骤计算WPL:
1. 将字符权值从小到大排序:A(16),B(5),C(9),D(3),E(30),F(1);
2. 取出频率最小的两个节点(F和D),组成一颗新树,根节点权值为两节点权值之和(4);
3. 将新树插入原有节点中合适的位置,得到如下情况:
A(16) E(30) 新树(4) C(9)
\ / / / \
B(5) C(9) E(30) A(16) D(3) B(5) E(30)
/ \ / /
A(16) B(5) F(1) F(1)
4. 重复步骤2和3,直到哈夫曼树构造完成,最后得到如下的哈夫曼树:
75
/ \
35 E(30)
/ \
16 新树(19)
/ \
C(9) 新树(10)
/ \
A(16) B(5)
新树(19) D(3) F(1)
/ \
A(16) B(5)
5. 计算WPL,遍历哈夫曼树每个叶子节点,将其深度乘以其权值,累加到WPL中。如下:
WPL = A深度 x A权值 + B深度 x B权值 + C深度 x C权值 + D深度 x D权值 + E深度 x E权值 + F深度 x F权值
= 3 x 16 + 4 x 5 + 3 x 9 + 4 x 3 + 2 x 30 + 5 x 1
= 221
因此,这份电文的带权路径长度WPL为221。
阅读全文