Question

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

用于通信的电文由字符集{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个字母设计哈夫曼编码

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏10（财富值+成长值）

Answer 1

哈夫曼编码首先要构造哈夫曼树，其构造规则是从概率这个序列中选择两个最小结点的值构造一颗树，新的树根的权值为两个子树的概率权值和。
如题中，首先选择0.02 和 0.03构造一颗树，将权值之和放回序列中，为：
0.07 0.19 0.10 0.32 0.21 0.06 0.05
继续上述过程只剩下一颗树为止。
最终哈夫曼树为：
1
/ \
0.40 0.60
/ \ / \
b0.19 g0.21 0.28 e0.32
/ \
0.11 0.17
/ \ / \
0.05 h0.06 a0.07 d0.10
/ \
f(0.02) c(0.03)
哈夫曼编码是从根结点开始，找叶子结点，也就是相关字符，默认往左为0，往右为1
所以b的编码是00，g:01 e:11 h:1001 a:1010 d:1011 f:10000c:10001