已知权值几何为要求给出哈夫曼树·并求wpl

已知权值几何为要求给出哈夫曼树·并求wpl

哈夫曼树的应用领域：数字传输编码压缩.
先编造哈夫曼树,哈夫曼树构造规则：
假设有n个权值,则构造出的哈夫曼树有n个叶子结点.n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为：
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树,并将新树加入森林；
(4)重复(2)、(3)步,直到森林中只剩一棵树为止
根据上面规则
8 12 5 20 4 11 先看成6棵树,可以排序一下 E(4) C(5) A(8) F(11) B(12) D(20)
选择两个权值最小的根 E C,作为左右子数,根权值是其左右字数根节点权值之和,即：
9
/ \
E(4) C(5)
新的森林为 A(8) 9 F(11) B(12) D(20)
/ \
E(4) C(5)
重复上面的步骤,选择两个权值最小的根A 9组成一个树,新的森林为
F(11) B(12) 17 D(20)
/ \
A(8) 9
/ \
E(4) C(5)
再次重复上面步骤,选择 F B,新的森林为
17 D(20) 23
/ \ / \
A(8) 9 F(11) B(12)
/ \
E(4) C(5)
再次重复上面步骤,选择 17 D,新的森林为
23 37
/ \ / \
F(11) B(12) 17 D(20)
/ \
A(8) 9
/ \
E(4) C(5)
再次重复,选择23 37,新的树为
60
/ \
23 37
/ \ / \
F(11) B(12) 17 D(20)
/ \
A(8) 9
/ \
E(4) C(5)
只有一棵树了,结束.
编码规则是,默认左子树为0,右子树为1.如F是根左子树的左子树,为00,B为左子树的右子树为01,A为右子树的左子树的左子树 100,类似,E为1010 C为1011 D为 11