已知字符a,b,c,d,e,f,g出现的次数分别为3,20,10,9,35,18,40,试设计哈夫曼编码。(权值小的放左边)
时间: 2023-09-28 16:12:12 浏览: 51
首先根据权值构建哈夫曼树:
1. 将权值从小到大排序,得到:a(3),d(9),b(20),c(10),f(18),e(35),g(40)
2. 取出权值最小的两个节点a和d,构建一棵树,其根节点的权值为13(a和d的权值之和)
3. 将根节点的权值插入到排序好的权值序列中,得到:13, b(20), c(10), f(18), e(35), g(40)
4. 再次取出权值最小的两个节点13和c,构建一棵树,其根节点的权值为23
5. 将根节点的权值插入到排序好的权值序列中,得到:23, b(20), f(18), e(35), g(40)
6. 再次取出权值最小的两个节点b和f,构建一棵树,其根节点的权值为38
7. 将根节点的权值插入到排序好的权值序列中,得到:38, e(35), g(40)
8. 再次取出权值最小的两个节点38和e,构建一棵树,其根节点的权值为73
9. 将根节点的权值插入到排序好的权值序列中,得到:73, g(40)
10. 最后取出权值最小的两个节点73和g,构建一棵树,其根节点的权值为113,得到完整的哈夫曼树。
![哈夫曼树](https://img-blog.csdnimg.cn/20211014190245625.png)
根据哈夫曼树得到字符的编码:
- a: 1001
- d: 1000
- b: 0
- c: 101
- f: 110
- e: 111
- g: 10
因此,字符a的编码为1001,字符d的编码为1000,字符b的编码为0,字符c的编码为101,字符f的编码为110,字符e的编码为111,字符g的编码为10。
相关问题
已知下列字符a、b、c、d、e、f、g的权值分别为4,13,8,5,3,9请构造哈夫曼树
首先将字符按照权值从小到大排序:e(3),g(9),a(4),d(5),c(8),f(9),b(13)。
然后选取权值最小的两个节点e和g,构造出一个新的节点,其权值为两个节点的权值之和12,把e和g作为新节点的左右子节点。此时剩余的节点为a、d、c、f、b。再次选取权值最小的节点a和d,构造出一个新的节点,其权值为两个节点的权值之和9,把a和d作为新节点的左右子节点。此时剩余的节点为c、f、b和新的节点(a+d)。
重复以上步骤,直到所有节点都被处理完,最终得到的哈夫曼树如下所示:
```
52
/ \
21 31
/ \ / \
9 12 13 18
/ \ / \ / \ / \
4 5 3 9 8 5 9 9
a d e g c f b 新节点
```
其中,根节点的权值为所有字符的权值之和,即4+13+8+5+3+9=42。
已知下列字符a、b、c、d、e、f、g的权值分别为4,13,8,5,3,9请构造哈夫曼树,计算其wp值
首先将字符按照权值从小到大排序,得到顺序为 e、g、a、d、c、f、b。然后将权值最小的两个字符 e 和 g 合并,得到一个新节点 eg,其权值为 e 和 g 的权值之和 3+9=12。合并后的序列为 eg、a、d、c、f、b、再将权值最小的两个节点 eg 和 a 合并,得到新节点 ega,其权值为 eg 和 a 的权值之和 12+4=16。合并后的序列为 ega、d、c、f、b。以此类推,直到所有节点都合并成一个根节点,得到哈夫曼树如下:
```
[48]
/ \
[21] [27]
/ \ / \
[9] [12] [13] [14]
/ \ / \ / \
e g a d c f
```
其中每个节点的值表示该节点下面所有字符权值之和。根据哈夫曼树可以计算每个字符的编码:
```
e: 00
g: 01
a: 101
d: 100
c: 1101
f: 1100
b: 111
```
每个字符的编码长度分别为 2、2、3、3、4、4、3,所以平均编码长度为:
```
wp = (4*2 + 13*2 + 8*3 + 5*3 + 3*4 + 9*4 + 3) / (4+13+8+5+3+9)
= 2.86
```
因此,该哈夫曼树的 wp 值为 2.86。