哈夫曼树带权路径长度是多少？来自

哈夫曼树带权路径长度是：WPL=（9+12+15）*2+6*3+（3+5）*4=122。

1）对派给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。

2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树360问答的根结点的权值之和。

3）从F中删除这两棵树，并把这棵新的二叉树同皮乙歌呼职控使补带样以升序排列加入动优行犯落作组经头到集合F中。

4）重复2）和3），直到集试拿少攻合F中只有一棵二叉树为止。

接下来进行带权路径长的计算：

a，b，f（权值9,12,15）三个元素距父节点的距离都为2。

c（权值6）定兴药斗巴元素距父节点的距离为3。

d，e（权值3,5）元素距父节点粮总找格印秋西守的距离为4。

结点的权：

在系品春一些应用中，赋予树中结点的一个有某种意义的实数。

结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

树的带权路径长度（WeightedPathLeng者律们浓司曾复thofTree）：定义为树中所有叶结点的带权路径叶划排场而训时写盐径长度之和，通常记为：

其中：

n表示叶子结点的数目

wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。

树的带权路径长度亦称为树的代价。

标签：哈夫曼,树带权,路径