C++用哈夫曼树实现对已有文件的编码

哈夫曼树可以用于文件的压缩和编码。以下是一个简单的 C++ 程序，用于实现对已有文件的编码：

#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>
#include <bitset>

using namespace std;

// 哈夫曼树节点类
class HuffmanNode {
public:
    char data;          // 节点存储的字符
    int freq;           // 字符出现的频率
    HuffmanNode* left;  // 左子树指针
    HuffmanNode* right; // 右子树指针

    HuffmanNode(char data, int freq) {
        this->data = data;
        this->freq = freq;
        this->left = nullptr;
        this->right = nullptr;
    }
};

// 哈夫曼树构建函数
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
    // 构建小根堆
    auto compare = [] (HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    };
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, decltype(compare)> minHeap(compare);
    for (auto& entry : freqMap) {
        minHeap.push(new HuffmanNode(entry.first, entry.second));
    }

    // 构建哈夫曼树
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        minHeap.push(parent);
    }

    return minHeap.top();
}

// 哈夫曼编码表生成函数
void generateHuffmanCodes(HuffmanNode* root, string code, unordered_map<char, string>& codesMap) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        codesMap[root->data] = code;
    }
    generateHuffmanCodes(root->left, code + "0", codesMap);
    generateHuffmanCodes(root->right, code + "1", codesMap);
}

// 压缩函数
void compressFile(string inputFile, string outputFile) {
    // 统计字符出现的频率
    unordered_map<char, int> freqMap;
    ifstream in(inputFile, ios::in | ios::binary);
    char ch;
    while (in.get(ch)) {
        freqMap[ch]++;
    }
    in.close();

    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);

    // 生成哈夫曼编码表
    unordered_map<char, string> codesMap;
    generateHuffmanCodes(root, "", codesMap);

    // 压缩文件
    in.open(inputFile, ios::in | ios::binary);
    ofstream out(outputFile, ios::out | ios::binary);
    string code, buffer;
    while (in.get(ch)) {
        code += codesMap[ch];
        while (code.length() >= 8) {
            buffer += static_cast<char>(bitset<8>(code.substr(0, 8)).to_ulong());
            code.erase(0, 8);
        }
    }
    if (!code.empty()) {
        code += string(8 - code.length(), '0');
        buffer += static_cast<char>(bitset<8>(code).to_ulong());
    }
    out << buffer;
    in.close();
    out.close();
}

int main() {
    string inputFile = "input.txt";
    string outputFile = "output.bin";
    compressFile(inputFile, outputFile);
    return 0;
}

该程序使用 unordered_map 统计输入文件中每个字符出现的频率，并使用哈夫曼树构建函数 `buildHuffmanTree` 构建哈夫曼树。然后，使用哈夫曼编码表生成函数 `generateHuffmanCodes` 生成每个字符的哈夫曼编码。最后，使用压缩函数 `compressFile` 将输入文件压缩为二进制格式的输出文件。