构造哈弗曼树:
1、首先a(3)、b(2)、i(1)、l(1)分别单独构成一个树(节点),节点的权重是字符出现的频率;
2、先将权重最小的两个节点结合组成一个新的节点(新节点的权重为子节点的权重之和),然后依次这样进行,最终所有的节点组成一个树;
3、对于每个节点,其左边值为0,右边值为1;所有的叶节点均为文本中出现的字符。
weight(2) weight(4)
weight(7)
0/
\1 0/ \1
0 / \ 1 -> weight(2)
b(2) -> weight(4) a(3)
0 / \1
0/ \1
l(1) i(1) l(1) i(1)
weight(2) b(2)
0 / \1
l(1) i(1)
所以,对于a/b/l/i 他们对应的霍夫曼编码
a:1;
b:01;
i :001;
L:000;
长度:1+3+3+2+1+2+1=13