构建哈夫曼树及编码c++

哈夫曼树是一种带权路径长度最短的树，可以用于数据压缩等领域。构建哈夫曼树的过程可以通过递归实现，具体步骤如下：
1. 将所有权值存储在一个数组中，并按照从小到大的顺序排序。
2. 取出权值最小的两个节点，将它们合并成一个新节点，新节点的权值为两个节点的权值之和。
3. 将新节点插入到数组中，并按照权值从小到大的顺序排序。
4. 重复步骤2和3，直到数组中只剩下一个节点，即为哈夫曼树的根节点。

下面是C++实现哈夫曼树的代码示例：

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

// 定义哈夫曼树节点结构体
struct HuffmanNode {
    int weight; // 权值
    HuffmanNode* left; // 左子节点
    HuffmanNode* right; // 右子节点
    HuffmanNode(int w) : weight(w), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于优先队列中节点的排序
struct cmp {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(vector<int>& weights) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (int w : weights) {
        pq.push(new HuffmanNode(w));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight);
        parent->left = left;        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 生成哈夫曼编码
void generateHuffmanCode(HuffmanNode* root, string code, vector<string>& codes) {
    if (!root) {
        return;    }
    if (!root->left && !root->right) {
        codes.push_back(code);
        return;
    }
    generateHuffmanCode(root->left, code + "0", codes);
    generateHuffmanCode(root->right, code + "1", codes);
}

int main() {
    vector<int> weights = {5, 9, 12, 13, 16, 45};
    HuffmanNode* root = buildHuffmanTree(weights);
    vector<string> codes;
    generateHuffmanCode(root, "", codes);
    for (int i = 0; i < weights.size(); i++) {
        cout << "Weight: " << weights[i] << ", Code: " << codes[i] << endl;
    }
    return 0;
}