哈夫曼树编码与实现c++

哈夫曼树编码是一种常用的无损压缩算法。该算法的核心思想是将出现频率较高的字符用较短的编码表示，出现频率较低的字符用较长的编码表示，从而实现对文本的压缩。哈夫曼树编码的实现包括以下几个步骤：

1. 统计文本中每个字符的出现频率，并将其存储在一个数组或者哈希表中。

2. 创建一个最小堆，并将每个字符的出现频率作为节点的权值。

3. 从最小堆中选择两个权值最小的节点，将它们合并成一个新节点，新节点的权值为两个节点权值之和。将新节点插入到最小堆中。

4. 重复步骤3，直到最小堆中只剩下一个节点为止。该节点即为哈夫曼树的根节点。

5. 遍历哈夫曼树，将每个字符对应的编码存储在一个数组或者哈希表中。

6. 对原始文本进行编码，将编码后的二进制数据存储在文件中。

7. 对编码后的文件进行解码，根据哈夫曼树和编码表还原原始文本。

下面是一个使用C++实现哈夫曼树编码的示例代码：

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

struct TreeNode {
    char data; // 字符
    int freq; // 出现频率
    TreeNode *left, *right;
    TreeNode(char c, int f) : data(c), freq(f), left(nullptr), right(nullptr) {}
    ~TreeNode() {
        delete left;
        delete right;
    }
};

struct cmp {
    bool operator()(const TreeNode* a, const TreeNode* b) const {
        return a->freq > b->freq;
    }
};

void buildHuffmanTree(unordered_map<char, int>& freqMap, TreeNode*& root) {
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> minHeap;

    for (auto& p : freqMap) {
        minHeap.push(new TreeNode(p.first, p.second));
    }

    while (minHeap.size() > 1) {
        auto left = minHeap.top();
        minHeap.pop();
        auto right = minHeap.top();
        minHeap.pop();

        auto node = new TreeNode('$', left->freq + right->freq);
        node->left = left;
        node->right = right;
        minHeap.push(node);
    }

    root = minHeap.top();
}

void buildCodeTable(TreeNode* root, unordered_map<char, string>& codeTable, string code) {
    if (!root) return;
    if (root->data != '$') {
        codeTable[root->data] = code;
    }
    buildCodeTable(root->left, codeTable, code + "0");
    buildCodeTable(root->right, codeTable, code + "1");
}

string encode(unordered_map<char, string>& codeTable, string text) {
    string res;
    for (char c : text) {
        res += codeTable[c];
    }
    return res;
}

string decode(TreeNode* root, string encodedText) {
    string res;
    auto curr = root;
    for (char c : encodedText) {
        if (c == '0') curr = curr->left;
        else curr = curr->right;

        if (!curr->left && !curr->right) {
            res += curr->data;
            curr = root;
        }
    }
    return res;
}

int main() {
    string text = "hello world";
    unordered_map<char, int> freqMap;
    for (char c : text) {
        freqMap[c]++;
    }

    TreeNode* root = nullptr;
    buildHuffmanTree(freqMap, root);

    unordered_map<char, string> codeTable;
    buildCodeTable(root, codeTable, "");

    string encodedText = encode(codeTable, text);
    cout << "Encoded Text: " << encodedText << endl;

    string decodedText = decode(root, encodedText);
    cout << "Decoded Text: " << decodedText << endl;

    delete root;

    return 0;
}