二叉树的wpl计算bjfu

二叉树的带权路径长度（Weighted Path Length，WPL）是二叉树中所有叶子节点的带权路径长度之和，其中带权路径长度是指从根节点到叶子节点的路径长度与该叶子节点的权值之积。

计算二叉树的WPL可以通过构建哈夫曼树来实现。哈夫曼树是一种特殊的二叉树，它的叶子节点表示待编码的字符，每个字符都有一个权值，哈夫曼树的带权路径长度是最小的。

步骤如下：

1. 给定一个二叉树，计算它的每个叶子节点的权值和路径长度。

2. 将所有的叶子节点按照权值从小到大排序。

3. 从权值最小的两个叶子节点中选取一个父节点，它的权值为两个叶子节点的权值之和，路径长度为两个叶子节点的路径长度之和。将这个父节点插入到原来的节点集合中。

4. 重复步骤 3 直到节点集合中只剩下一个节点，这个节点就是哈夫曼树的根节点。

5. 计算哈夫曼树的带权路径长度，即所有叶子节点的权值与路径长度之积的和。

下面是一个用C++实现的计算二叉树WPL的函数：

int getWPL(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return root->val;
    }
    int left_wpl = getWPL(root->left);
    int right_wpl = getWPL(root->right);
    return left_wpl + right_wpl + root->val;
}

其中 TreeNode 表示二叉树节点的结构体，val 表示节点的权值，left 和 right 分别表示左右子节点的指针。函数的返回值是二叉树的WPL。