带权路径长度是多少?

发布网友发布时间：2022-04-24 19:58

共1个回答

热心网友时间：2023-10-09 06:31

带权路径长度也就是树的带权路径长度，树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。

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

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

注意事项：

1、叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。

2、最优二叉树中，权越大的叶子离根越近。

3、最优二叉树的形态不唯一，WPL最小。

在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或哈夫曼树。