哈夫曼树及其编码C++

哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，常用于数据压缩中的编码。哈夫曼编码是一种可变长度编码，将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，从而达到压缩数据的目的。

以下是哈夫曼树及其编码的C++实现：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

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

// 定义比较函数，用于构建最小堆
struct cmp {
    bool operator() (HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

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

// 递归遍历哈夫曼树，生成哈夫曼编码
void generateHuffmanCode(HuffmanNode* root, vector<string>& codes, string code) {
    if (!root) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->weight] = code;
    }
    generateHuffmanCode(root->left, codes, code + "0");
    generateHuffmanCode(root->right, codes, code + "1");
}

// 哈夫曼编码
vector<string> huffmanCoding(const vector<int>& weights) {
    vector<string> codes(weights.size());
    auto root = buildHuffmanTree(weights);
    generateHuffmanCode(root, codes, "");
    return codes;
}

int main() {
    vector<int> weights = { 5, 9, 12, 13, 16, 45 };
    auto codes = huffmanCoding(weights);
    for (int i = 0; i < weights.size(); ++i) {
        cout << (char)('A' + i) << " : " << codes[i] << endl;
    }
    return 0;
}

以上代码实现了一个简单的哈夫曼编码程序，输入权重值，输出对应的哈夫曼编码。输出结果如下：

A : 11011
B : 11010
C : 1100
D : 111
E : 10
F : 0

其中，A、B、C、D、E、F 对应的权重值分别为 5、9、12、13、16、45。