有一电文共使用 7 种字符 A， B， C， D， E， F， G， 其出现频率依次为 0.05 , 0.30 , 0.09 , 0.15 , 0.10 , 0.11 , 0.20。 ( 1 ) 试画出对应的编码哈夫曼树[1] ( 要求左子树根结点[2]的权小于等于右子树根结点的权 ) ( 2 ) 求出每个字符的哈夫曼编码[3]
有一电文共使用 7 种字符 A， B， C， D， E， F， G， 其出现频率依次为 0.05 , 0.30 , 0.09 , 0.15 , 0.10 , 0.11 , 0.20。
( 1 ) 试画出对应的编码哈夫曼树[1] ( 要求左子树根结点[2]的权小于等于右子树根结点的权 )
( 2 ) 求出每个字符的哈夫曼编码[3]
题目解答
答案
（1）根据哈夫曼树建树的规则，从小到大将权值进行排序，然后两两合并，最后得到如下的哈夫曼树：
+--------+
| 1.00 |
| |
+--------+
/ \
/ \
+--------+ +--------+
| 0.39 | | 0.61 |
| | | |
+--------+ +--------+
/ \ / \
/ \ / \
+--------+ +--------+ +--------+
| 0.20 | | 0.21 | | 0.40 |
| (G) | | (C) | | +--------+
+--------+ +--------+ | | 0.19 |
| | (A) |
| +--------+
|
| +--------+
| | 0.21 |
| | (F) |
| +--------+
|
| +--------+
| | 0.25 |
| | (D) |
| +--------+
|
| +--------+
| | 0.30 |
| | (B) |
| +--------+
（2）根据哈夫曼树的编码规则，从根节点开始，向左子树走为0，向右子树走为1，经过树上的路径即为该字符的编码。因此，得到每个字符的编码如下：
A: 111111
B: 0
C: 111101
D: 1110
E: 111100
F: 11111
G: 10
解析
首先，根据字符的出现频率，构建哈夫曼树。哈夫曼树的构建规则是：每次从当前未合并的节点中选择两个权值最小的节点，合并成一个新的节点，新节点的权值为两个子节点权值之和。重复此过程，直到所有节点合并成一个根节点。
步骤 2：确定哈夫曼树的结构
根据哈夫曼树的构建规则，我们得到如下哈夫曼树结构：
+--------+
| 1.00 |
| |
+--------+
/ \
/ \
+--------+ +--------+
| 0.39 | | 0.61 |
| | | |
+--------+ +--------+
/ \ / \
/ \ / \
+--------+ +--------+ +--------+
| 0.20 | | 0.21 | | 0.40 |
| (G) | | (C) | | +--------+
+--------+ +--------+ | | 0.19 |
| | (A) |
| +--------+
|
| +--------+
| | 0.21 |
| | (F) |
| +--------+
|
| +--------+
| | 0.25 |
| | (D) |
| +--------+
|
| +--------+
| | 0.30 |
| | (B) |
| +--------+
步骤 3：确定哈夫曼编码
根据哈夫曼树的结构，从根节点开始，向左子树走为0，向右子树走为1，经过树上的路径即为该字符的编码。因此，得到每个字符的编码如下：
A: 111111
B: 0
C: 111101
D: 1110
E: 111100
F: 11111
G: 10