7-1 哈夫曼树WPL值

哈夫曼树的WPL（带权路径长度）是指树中所有叶子结点的权值乘以其到根节点的路径长度之和。具体计算方法如下：

1. 构建哈夫曼树，将权值较小的节点放在树的底部，权值较大的节点放在树的顶部。构建过程中需要用到贪心算法。

2. 计算WPL。从根节点开始，对于每个叶子节点，将其权值乘以其到根节点的路径长度，再将所有叶子节点的计算结果相加，即为哈夫曼树的WPL值。

例如，对于一棵包含4个叶子节点的哈夫曼树，其各叶子节点的权值分别为2、3、4、5，则WPL的计算过程如下：

1. 构建哈夫曼树：首先将权值最小的2和3合并成一棵子树，其权值为5；然后将权值次小的4和5合并成一棵子树，其权值为9；最后将5和9合并成一棵树，其权值为14，即为哈夫曼树的根节点。

2. 计算WPL：对于每个叶子节点，将其权值乘以其到根节点的路径长度，得到的结果分别为10、9、6、5，将它们相加得到30，即为该哈夫曼树的WPL值。

相关问题

用C++代码求哈夫曼树WPL值

下面是一个使用C++语言实现求哈夫曼树WPL值的示例代码：

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

struct cmp {
    bool operator()(TreeNode* a, TreeNode* b) {
        return a->val > b->val;
    }
};

int getWPL(TreeNode* root, int depth) {
    if (root->left == NULL && root->right == NULL) {
        return root->val * depth;
    }
    int wpl = 0;
    if (root->left != NULL) {
        wpl += getWPL(root->left, depth + 1);
    }
    if (root->right != NULL) {
        wpl += getWPL(root->right, depth + 1);
    }
    return wpl;
}

int main() {
    int n;
    cin >> n;
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> q;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        TreeNode* node = new TreeNode(val);
        q.push(node);
    }
    while (q.size() > 1) {
        TreeNode* node1 = q.top();
        q.pop();
        TreeNode* node2 = q.top();
        q.pop();
        TreeNode* newNode = new TreeNode(node1->val + node2->val);
        newNode->left = node1;
        newNode->right = node2;
        q.push(newNode);
    }
    TreeNode* root = q.top();
    int wpl = getWPL(root, 0);
    cout << wpl << endl;
    return 0;
}

该代码首先读入叶子节点的数量和权值，然后使用优先队列来构建哈夫曼树。接着，定义一个递归函数`getWPL`来计算WPL值，函数参数中的`depth`表示当前节点到根节点的路径长度。最后，输出计算得到的WPL值即可。

用C++代码求哈夫曼树WPL值，要用类的方法

下面是一个使用C++语言，用类的方法实现求哈夫曼树WPL值的示例代码：

#include <iostream>
#include <queue>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class HuffmanTree {
private:
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> q;
    int n;
    struct cmp {
        bool operator()(TreeNode* a, TreeNode* b) {
            return a->val > b->val;
        }
    };
    int getWPL(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            return root->val * depth;
        }
        int wpl = 0;
        if (root->left != NULL) {
            wpl += getWPL(root->left, depth + 1);
        }
        if (root->right != NULL) {
            wpl += getWPL(root->right, depth + 1);
        }
        return wpl;
    }
public:
    HuffmanTree() {
        cin >> n;
        for (int i = 0; i < n; i++) {
            int val;
            cin >> val;
            TreeNode* node = new TreeNode(val);
            q.push(node);
        }
        while (q.size() > 1) {
            TreeNode* node1 = q.top();
            q.pop();
            TreeNode* node2 = q.top();
            q.pop();
            TreeNode* newNode = new TreeNode(node1->val + node2->val);
            newNode->left = node1;
            newNode->right = node2;
            q.push(newNode);
        }
    }
    int getWPL() {
        TreeNode* root = q.top();
        return getWPL(root, 0);
    }
};

int main() {
    HuffmanTree tree;
    int wpl = tree.getWPL();
    cout << wpl << endl;
    return 0;
}

该代码使用了类`HuffmanTree`来实现哈夫曼树的构建和WPL值的计算。在类中，定义了一个私有成员变量`q`，用于存储优先队列；定义了一个私有成员函数`getWPL`，用于递归计算WPL值；定义了一个公有成员函数`getWPL`，用于调用`getWPL`计算WPL值，并返回计算结果。

在`main`函数中，首先创建一个`HuffmanTree`对象，然后调用其`getWPL`函数计算WPL值，并输出结果即可。