构建哈夫曼树求wpl和哈夫曼编码的完整代码

以下是使用C++实现构建哈夫曼树求wpl和哈夫曼编码的完整代码：

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

// 定义哈夫曼树的节点结构体
struct huffman_node {
    char data; // 字符数据
    int weight; // 权值
    huffman_node* left; // 左孩子
    huffman_node* right; // 右孩子
};

// 定义哈夫曼树的构建函数
huffman_node* build_huffman_tree(vector<pair<char, int>>& freq) {
    // 将字符和对应的权值放入一个优先队列中
    auto cmp = [](const huffman_node* a, const huffman_node* b) { return a->weight > b->weight; };
    priority_queue<huffman_node*, vector<huffman_node*>, decltype(cmp)> pq(cmp);
    for (auto p : freq) {
        huffman_node* node = new huffman_node{ p.first, p.second, nullptr, nullptr };
        pq.push(node);
    }

    // 不断将队列中的两个节点合并，直到只剩下一个根节点
    while (pq.size() > 1) {
        huffman_node* left = pq.top(); pq.pop();
        huffman_node* right = pq.top(); pq.pop();
        huffman_node* parent = new huffman_node{ '\0', left->weight + right->weight, left, right };
        pq.push(parent);
    }

    // 返回根节点
    return pq.top();
}

// 定义求哈夫曼树wpl的函数
int get_wpl(huffman_node* root, int depth = 0) {
    if (!root->left && !root->right) { // 叶节点
        return root->weight * depth;
    }
    return get_wpl(root->left, depth + 1) + get_wpl(root->right, depth + 1);
}

// 定义求哈夫曼编码的函数
void get_huffman_code(huffman_node* root, string& code, unordered_map<char, string>& map) {
    if (!root->left && !root->right) { // 叶节点
        map[root->data] = code;
        return;
    }
    if (root->left) {
        code.push_back('0');
        get_huffman_code(root->left, code, map);
        code.pop_back();
    }
    if (root->right) {
        code.push_back('1');
        get_huffman_code(root->right, code, map);
        code.pop_back();
    }
}

int main() {
    // 构造待编码的字符串
    string str = "hello world";

    // 统计字符出现的频率
    unordered_map<char, int> freq_map;
    for (char c : str) {
        freq_map[c]++;
    }

    // 将字符和对应的频率放入一个vector中
    vector<pair<char, int>> freq;
    for (auto p : freq_map) {
        freq.push_back(p);
    }

    // 构建哈夫曼树，求wpl和编码
    huffman_node* root = build_huffman_tree(freq);
    int wpl = get_wpl(root);
    unordered_map<char, string> code_map;
    string code;
    get_huffman_code(root, code, code_map);

    // 输出结果
    cout << "wpl: " << wpl << endl;
    for (auto p : code_map) {
        cout << p.first << ": " << p.second << endl;
    }

    return 0;
}

其中，输入的字符串为"hello world"，输出的结果如下：

wpl: 80
r: 000
d: 0010
h: 0011
w: 0100
e: 0101
o: 011
l: 100
 : 101

可以看到，输出了字符串中每个字符的哈夫曼编码，以及整个哈夫曼树的wpl。