哈夫曼树+带权路径长度计算
哈夫曼树（最优⼆叉树）
其⽬的：
出存放⼀串字符需要的最少的⼆进制编码哈夫曼编码树的带权路径长度
构造⽅法：
1.得到每种字符出现的频率或者概率，即权值，构成频率表
2.出频率最⼩的两个，⼩的在左边，⼤的在右边，组成⼆叉树。⽗节点为两者的和（不计⼊WPL计算），频率表更新（删除这两个数，同时加⼊两数的和）
3.重复2.
4.最后标记01,0左1右，每个字符的⼆进制表⽰从上到下读出。
详细例⼦：
总结：频率⾼的字符编码越短。
带权路径长度计算：
权值*深度求和。
⽐如下⾯这个树：
频率表：3 5 7 8 11 14 23 29
wpl=（3+5）*5+7*4+（8+11+14）*3+（23+29）*2=271

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。