已知下列字符A、B、C、D、E、F、G的权值分别是3、12、7、4、2、8、11。绘制以该权值为叶子结点的Huffman树,并求出树的带权路径长度值WPL和压缩率,并写出以上每个字符的编码。
时间: 2023-06-16 21:03:54 浏览: 1968
首先,我们需要按照权值从小到大的顺序排列这些字符,得到:A(3)、E(2)、D(4)、G(11)、C(7)、F(8)、B(12)。
接下来,我们需要构建Huffman树:
1. 将权值最小的两个节点A和E合并,得到一个新节点AE,其权值为3+2=5。
2. 将权值最小的两个节点D和AE合并,得到一个新节点DAE,其权值为5+4=9。
3. 将权值最小的两个节点C和F合并,得到一个新节点CF,其权值为7+8=15。
4. 将权值最小的两个节点DAE和CF合并,得到一个新节点DAECF,其权值为9+15=24。
5. 将权值最小的两个节点G和B合并,得到一个新节点GB,其权值为11+12=23。
6. 将权值最小的两个节点GB和DAECF合并,得到一个新节点Huffman树的根节点,其权值为23+24=47。
Huffman树如下所示:
```
47
/ \
23 24
/ \ / \
11 12 9 15
/ \
5 4
/ \
3 2
```
接下来,我们需要计算树的带权路径长度值WPL和压缩率。
树的带权路径长度值WPL = 3×1 + 2×2 + 4×2 + 11×3 + 7×3 + 8×3 + 12×3 = 121
压缩率 = (7×3 + 4×2 + 2×3 + 3×5 + 8×3 + 12×3)/(3×8)= 2.125
最后,我们需要给每个字符分配编码。在Huffman树中,从根节点到每个叶子节点的路径上,左边的路径表示0,右边的路径表示1。因此,A的编码为000,E的编码为001,D的编码为01,G的编码为11,C的编码为10,F的编码为110,B的编码为111。
综上所述,该Huffman树的带权路径长度值WPL为121,压缩率为2.125,每个字符的编码分别为:
A:000
E:001
D:01
G:11
C:10
F:110
B:111
阅读全文