在一段报文中只包含a、b、C、d、 e、f六种字符,在报文中出现的次数依次为4、 10、3、7、4、2,构造哈夫曼树,并写出每个 字符的哈夫曼编码。
时间: 2023-10-20 22:08:56 浏览: 367
cdt报文分析,使对CDT代码的编写更具有直观性3
首先,按照出现次数从小到大排序,得到字符序列为a、f、C、e、d、b,对应出现次数为4、2、3、4、7、10。
接下来,按照哈夫曼树构建的规则,将出现次数最小的两个字符a和f合并成一个节点,其权值为4+2=6。此时字符序列变为C、e、d、b、(af),对应出现次数为3、4、7、10、6。
再次将出现次数最小的两个字符C和e合并成一个节点,其权值为3+4=7。此时字符序列变为d、b、(C,e,af),对应出现次数为7、10、13。
继续将出现次数最小的两个字符d和b合并成一个节点,其权值为7+10=17。此时字符序列变为(C,e,af)、(d,b),对应出现次数为13、17。
最后将剩余的两个节点合并,其权值为13+17=30,得到哈夫曼树如下:
```
30
/ \
13 17
/ \ / \
(C,e,af) (d,b)
```
根据哈夫曼树,可以得到字符a的编码为0,字符f的编码为101,字符C的编码为100,字符e的编码为110,字符d的编码为111,字符b的编码为01。因此,原始报文中的字符a、f、C、e、d、b分别对应的哈夫曼编码为0、101、100、110、111、01。
阅读全文