哈夫曼编码
某电文由8个字母组成，字母出现的频率如下表所示，请写出字母的哈夫曼编码。
| 字母 | 频率 | 哈夫曼编码 |
| A | 22 | |
| B | 15 | |
| C | 4 | |
| D | 3 | |
| E | 37 | |
| F | 10 | |
| G | 7 | |
| H | 2 |
因为有着八个元素，所以要预留2*n-1（n=8）即15个空位置
如下图所示求哈夫曼编码即使要把给填满
| name | weight | parent | lchild | rchild |
| A | 22 | 0 | ||
| B | 15 | 0 | ||
| C | 0 | |||
| D | 0 | |||
| E | 37 | 0 | ||
| F | 0 | |||
| G | 0 | |||
| H | 0 | |||
| I | ||||
| J | ||||
| K | ||||
| L | ||||
| M | ||||
| N | ||||
| O |
怎么求I?
首先在I的上方选取两个weight(权重)最小的点，I的值即为他们的和
由上图分析可知
I(weight)=H(weight)+D(weight)
画成图就是：
由此图可知
I的权重为5，父母为0（无父母），左子树为H,右子树为D
| I | 5 | 0 | H | D |
H，D的父母也要修改为（I）
| H | 2 | I |
| D | 3 | I |
然后再从J的上方挑选两个子树合成新的树
选出 C和H分别作为J的左右子树，（C<H即是4<5）
即需要修改：
| C | 4 | J | 0 | 0 |
| I | 5 | J | H | D |
| J | 9 | 0 | C | I |
依次类推将所有的元素补全构建成完整的树：
即是：
求编码只求编码区 （ABCDEFGH）
E从根开始向下查找 0
A从根开始向下查找 1 0
B从根开始向下查找 1 1 0
由图可知各个字符的哈夫曼编码
电文总长度（WPL）为
所有红节点的和
即5+9+16+26+41+63+100=260
2 分文章来源：https://www.toymoban.com/news/detail-475470.html
位。文章来源地址https://www.toymoban.com/news/detail-475470.html
到了这里，关于填空 哈夫曼编码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
