一道关于求哈夫曼编码的数据结构题，求解答用于通信的电文由字符-查字典问答网

来自金志华的问题

　　一道关于求哈夫曼编码的数据结构题，求解答用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字符构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.10,0.32,0.03,0.21,0.06}，为这8个字

　　一道关于求哈夫曼编码的数据结构题，求解答

　　用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字符构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.10,0.32,0.03,0.21,0.06}，为这8个字母设计哈夫曼编码

1回答

2020-02-02 06:45

我要回答

请先登录

程立新

　　哈夫曼编码首先要构造哈夫曼树，其构造规则是从概率这个序列中选择两个最小结点的值构造一颗树，新的树根的权值为两个子树的概率权值和。

　　如题中，首先选择0.02和0.03构造一颗树，将权值之和放回序列中，为：

　　0.070.190.100.320.210.060.05

　　继续上述过程只剩下一颗树为止。

　　最终哈夫曼树为：

　　0.400.60

　　b0.19g0.210.28e0.32

　　0.110.17

　　0.05h0.06a0.07d0.10

　　f(0.02)c(0.03)

　　哈夫曼编码是从根结点开始，找叶子结点，也就是相关字符，默认往左为0，往右为1

　　所以b的编码是00，g:01e:11h:1001a:1010d:1011f:10000c:10001

2020-02-02 06:48:48