用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度

Question

用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度
用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度

Answer 1

先构造哈夫曼树,其构造规则如下：
假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为：
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树,并将新树加入森林；
(4)重复(2)、(3)步,直到森林中只剩一棵树为止根
根据上述规则先选择两个权值最小的点构造为一个树,1 和 2 组成根为3的树,新的序列就是
3 3 4 5
/ \
1 2
在这个新的序列选两个权值最小的点 3 和 3组成一课新树,新的序列
4 5 6
/ \
3 3
/ \
1 2
再选取两个权值最小的点 4 5组成一新树
6 9
/ \ / \
3 3 4 5
/ \
1 2
再选取两个权值最小的点 6 9组成一新树
15
/ \
6 9
/ \ / \
3 3 4 5
/ \
1 2
只有一个根了,结束.
树带权路径长度WPL=3 *2 + 1 * 3 + 2*3 + 4*2 + 5*2 = 33 （就是所有叶子结点的权值 * 深度之和）