画出Huffman树,写出各字符的Huffman编码,并计算WPL值。 字符集{A,B,C,D,E,E,G,H} 权值集{23,5,17,4,9,31,29,18}
时间: 2023-10-02 15:08:48 浏览: 122
首先,我们需要按照权值从小到大对字符进行排序:
```
D 4
B 5
E 9
C 17
H 18
A 23
G 29
E 31
```
然后,我们需要构建 Huffman 树,步骤如下:
1. 将权值最小的两个字符合并为一个新节点,权值为它们的和。
```
D 4
B 5
E 9
C 17
H 18
A 23
G 29
E 31
9
/ \
D B
```
2. 将权值次小的两个字符合并为一个新节点,权值为它们的和。
```
D 4
B 5
E 9
C 17
H 18
A 23
G 29
E 31
18
/ \
D B
/ \ / \
E C H A
```
3. 将权值第三小的两个字符合并为一个新节点,权值为它们的和。
```
D 4
B 5
E 9
C 17
H 18
A 23
G 29
E 31
18
/ \
D B
/ \ / \
E C H A
/ \
G E
```
4. 将权值第四小的两个字符合并为一个新节点,权值为它们的和。
```
D 4
B 5
E 9
C 17
H 18
A 23
G 29
E 31
18
/ \
D B
/ \ / \
E C H A
/ / \
G E E
```
5. 将权值第五小的两个字符合并为一个新节点,权值为它们的和。
```
D 4
B 5
E 9
C 17
H 18
A 23
G 29
E 31
18
/ \
D B
/ \ / \
E C H A
/ / \
G E E
```
6. 将权值第六小的两个字符合并为一个新节点,权值为它们的和。
```
D 4
B 5
E 9
C 17
H 18
A 23
G 29
E 31
18
/ \
D B
/ \ / \
E C H A
/ \ / \ / \
G E E E G E
```
现在我们已经构建了 Huffman 树。接下来,我们需要为每个字符确定 Huffman 编码。从根节点出发,左边的路径标记为0,右边的路径标记为1。当我们到达叶子节点时,我们记录下路径上的数字,这就是该字符的 Huffman 编码。例如,字符 D 的 Huffman 编码为 00,字符 A 的 Huffman 编码为 1111。
```
D 4 00
B 5 01
E 9 10
C 17 110
H 18 1110
A 23 1111
G 29 1100
E 31 11
```
最后,我们计算 WPL 值。WPL 的全称是 Weighted Path Length,即所有叶子节点的权值乘以它们的深度之和。对于这个例子,WPL 值为:
```
4*2 + 5*2 + 9*2 + 17*3 + 18*4 + 23*4 + 29*3 + 31*2 = 356
```
因此,这个字符集的 Huffman 编码是:
```
D 4 00
B 5 01
E 9 10
C 17 110
H 18 1110
A 23 1111
G 29 1100
E 31 11
WPL = 356
```