树的带权路径长度怎么算

树的路径长度为从树根至树中各个结点的路径长度的总和。在结点数量相同的二叉树中，完全二叉树的路径长度是最短的。

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

其中：

n 代表叶子结点的数量

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

树的带权路径长度也被称作树的代价。

一棵深度为 k，且拥有 2^k - 1 个节点的二叉树，被叫做满二叉树。该树的特点是每一层上的节点数均为最大节点数。而在一棵二叉树中，除了最后一层外，倘若其余层都是满的，并且最后一层要么是满的，要么是在右边缺少连续的若干节点，那么此二叉树就是完全二叉树。

具有 n 个节点的完全二叉树的深度为 floor(log2n) + 1。深度为 k 的完全二叉树，最少有 2^(k - 1) 个叶子节点，最多有 2^k - 1 个节点。