Question

数据结构 判断题求解答

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