已知一电报中abcdefgh八个字符,他们在电报中出现的概率为0.09,0.02,0.15,0.19,0.20,0.11,0.07,0.17,给出一种可行的哈夫曼编码。(画出相应哈夫曼树)
时间: 2024-05-14 10:18:26 浏览: 11
首先按照出现概率从小到大排序,得到以下列表:
| 字符 | a | b | c | d | e | f | g | h |
|------|-------|-------|-------|-------|-------|-------|-------|-------|
| 概率 | 0.09 | 0.02 | 0.15 | 0.19 | 0.20 | 0.11 | 0.07 | 0.17 |
接下来按照哈夫曼编码的构造方法,构造哈夫曼树:
1. 将概率最小的两个字符 a 和 b 合并,得到一个新节点 ab,其概率为 0.09+0.02=0.11。
2. 将概率最小的两个字符 ab 和 g 合并,得到新节点 abg,其概率为 0.11+0.07=0.18。
3. 将概率最小的两个字符 c 和 f 合并,得到新节点 cf,其概率为 0.15+0.11=0.26。
4. 将概率最小的两个字符 d 和 e 合并,得到新节点 de,其概率为 0.19+0.20=0.39。
5. 将概率最小的两个节点 abg 和 cf 合并,得到新节点 abgcf,其概率为 0.18+0.26=0.44。
6. 将概率最小的两个节点 de 和 h 合并,得到新节点 deh,其概率为 0.39+0.17=0.56。
7. 将概率最小的两个节点 abgcf 和 deh 合并,得到新的根节点,其概率为 0.44+0.56=1。
构建好的哈夫曼树如下所示:
```
1
/ \
0.44 0.56
/ \
abgcf deh
/ \
0.18 0.26
/ \
abg cf
/ \
0.09 0.02
|
root
```
最后给出每个字符的哈夫曼编码:
| 字符 | a | b | c | d | e | f | g | h |
|------|-------|-------|-------|-------|-------|-------|-------|-------|
| 编码 | 111 | 1101 | 10 | 01 | 00 | 100 | 1011 | 1010 |
其中,左子树表示编码为 0,右子树表示编码为 1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)