Question

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

Answer 1

哈夫曼树带权路径长度是：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中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

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

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

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

c（权值6）元素距父节点的距离为3。

d，e（权值3,5）元素距父节点的距离为4。

结点的权：

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

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

树的带权路径长度（Weighted Path Length of Tree）：定义为树中所有叶结点的带权路径长度之和，通常记为：

其中：

n表示叶子结点的数目

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

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