带权路径长度是个什么概念？

Question

如题所述

Answer 1

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

带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度若根结点为0层，叶结点到根结点的路径长度为叶结点的层数。

带权路径长度表示方法

树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

WPL是衡量一个带权二叉树优劣的关键。无论如何，对于n个带权节点，总可以用他们作为叶节点构造出一颗最小WPL值的树。