哈夫曼树的带权路径长度是_哈夫曼树带权路径长度c_结点的路径长度

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

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

先构造哈夫曼树,其构造规则如下：

假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为：

(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树,并将新树加入森林；

(4)重复(2)、(3)步,直到森林中只剩一棵树为止根

根据上述规则先选择两个权值最小的点构造为一个树,1 和 2 组成根为3的树,新的序列就是

3 345

/ \

12

在这个新的序列选两个权值最小的点 3 和 3组成一课新树,新的序列

4 5 6

/ \

3 3

/ \

12

再选取两个权值最小的点 4 5组成一新树

69

/ \/ \

3 34 5

/ \

12

再选取两个权值最小的点 6 9组成一新树

15

/\

69

/ \/ \

3 34 5

/ \

12

只有一个根了,结束.

树带权路径长度WPL=3 *2 + 1 * 3 + 2*3 + 4*2 + 5*2 = 33 （就是所有叶子结点的权值 * 深度之和）

设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度之和为多少?2014-10-21

【数据结构】用五个权值｛3.2.4.5.1｝构造的哈夫曼树带权路径长度是多少?2014-11-03

由分别带权为9,2,5,7的4个叶节点构造一棵哈夫曼树,该树的带权路径长度为（）?2014-10-09

用整数 1,2,3,4,5作为5个树叶的权值,构造出的哈夫曼树的带权路径长度WPL2014-10-09

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-22202-1.html