二元霍夫曼编码C＋＋代码

二元霍夫曼编码是一种用于数据压缩的无损压缩算法，它通过对频率较高的字符分配较短的编码，从而实现高效的数据压缩。在C++中实现二元霍夫曼编码，你需要先构建一个霍夫曼树，然后根据这个树来生成每个字符的编码。

以下是一个简单的C++代码示例，展示了如何创建霍夫曼树和编码过程：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

// 定义霍夫曼树节点结构
struct HuffmanNode {
    char data;
    int freq;
    HuffmanNode* left = nullptr;
    HuffmanNode* right = nullptr;
};

// 创建一个空的二叉树
HuffmanNode* createEmptyTree() {
    return new HuffmanNode();
}

// 插入节点到优先队列
void insert(HuffmanNode** heap, char data, int freq) {
    HuffmanNode* newNode = createEmptyTree();
    newNode->data = data;
    newNode->freq = freq;
    
    if (*heap == nullptr) {
        *heap = newNode;
    } else {
        HuffmanNode* current = *heap;
        while (current != nullptr) {
            if (freq < current->freq) {
                if (current->left == nullptr) {
                    current->left = newNode;
                    break;
                }
                current = current->left;
            } else {
                if (current->right == nullptr) {
                    current->right = newNode;
                    break;
                }
                current = current->right;
            }
        }
    }
}

// 创建霍夫曼树
HuffmanNode* buildHuffmanTree(std::vector<HuffmanNode*>& freqNodes) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, std::greater<HuffmanNode*>> huffmanHeap(freqNodes.begin(), freqNodes.end());
    
    while (huffmanHeap.size() > 1) {
        HuffmanNode* left = huffmanHeap.top(); huffmanHeap.pop();
        HuffmanNode* right = huffmanHeap.top(); huffmanHeap.pop();
        
        HuffmanNode* newNode = createEmptyTree();
        newNode->left = left;
        newNode->right = right;
        newNode->freq = left->freq + right->freq;
        huffmanHeap.push(newNode);
    }
    
    return huffmanHeap.top();
}

// 从霍夫曼树生成编码
std::unordered_map<char, std::string> generateCodes(HuffmanNode* root) {
    std::unordered_map<char, std::string> codes;
    std::string prefix = "";
    
    traverseHuffmanTree(root, "", codes);
    return codes;
}

// 遍历霍夫曼树并生成编码
void traverseHuffmanTree(HuffmanNode* node, std::string prefix, std::unordered_map<char, std::string>& codes) {
    if (node == nullptr) return;
    
    if (node->left == nullptr && node->right == nullptr) { // 达到叶子节点，添加编码
        codes[node->data] = prefix;
    } else {
        traverseHuffmanTree(node->left, prefix + "0", codes);
        traverseHuffmanTree(node->right, prefix + "1", codes);
    }
}

// 示例使用
int main() {
    // 假设有一个字符频率统计
    std::vector<HuffmanNode*> freqNodes = {{"a", 10}, {"b", 5}, {"c", 3}};

    HuffmanNode* root = buildHuffmanTree(freqNodes);
    std::unordered_map<char, std::string> codes = generateCodes(root);

    // 输出编码结果
    for (const auto& pair : codes) {
        std::cout << "Character " << pair.first << " has encoding: " << pair.second << std::endl;
    }

    return 0;
}