给定叶子结点权值153678,构造哈夫曼树,并计算其带权路径长度

Question

给定叶子结点权值 1 5 3 6 7 8,构造哈夫曼树,并计算其带权路径长度

Answer 1

哈夫曼树构造方法
假设有n个权值,则构造出的哈夫曼树有n个叶子结点.n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为：
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树,并将新树加入森林；
(4)重复(2)、(3)步,直到森林中只剩一棵树为止
根据上述方法,得到的哈夫曼树,先选1 3 得到4,新的森林即 4 5 6 7 8,选择4 5 得到9,新的森林变为6 7 8 9,选择6 7 得到13,森林变为8 9 13,选择8 9得到17 变为 13 17,选择13 17得到30,只剩最后一个课树.
[30]
/ \
[17] [13]
/ \ / \
(8) [9] (6) (7)
/ \
[4] (5)
/ \
(1) (3)
图片上传不了,按照上述方式弄了一下,()表示叶节点,到时候你用圈就行,[]表示是其下面左右子树的根.
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL
WPL= 1*4 +3*4 +5*3 + 8*2 + 6*2 + 7*2 = 73