c＋＋构建哈夫曼树及译码并逐行注释

C++构建哈夫曼树通常涉及以下几个步骤，这里我们使用优先队列和贪心算法：

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

using namespace std;

// 定义节点结构体，包含字符和频率
struct Node {
    char data;
    int freq;
    Node* left = nullptr;
    Node* right = nullptr;
};

// 创建新节点函数
Node* createNode(char data, int freq) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->freq = freq;
    return newNode;
}

// 用于存储节点及其频率的结构体，以及优先队列操作
struct Compare {
    bool operator()(const pair<Node*, int>& a, const pair<Node*, int>& b) {
        return a.second > b.second; // 按频率降序排序
    }
};

// 构建哈夫曼树
vector<Node*> buildHuffmanTree(vector<int>& freqs) {
    priority_queue<pair<Node*, int>, vector<pair<Node*, int>>, Compare> pq;
    for (int freq : freqs) {
        pq.push({createNode('\0', freq), freq}); // 初始化队列，空字符作为默认值
    }

    while (pq.size() > 1) { // 当队列大小大于1时，继续构建
        Node* left = pq.top().first;
        pq.pop(); // 弹出左节点
        Node* right = pq.top().first;
        pq.pop(); // 弹出右节点

        // 合并左右节点，并更新新的节点频率
        Node* newNode = createNode('\0', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;

        // 将新节点加入队列
        pq.push({newNode, newNode->freq});
    }

    // 最后队列剩下的就是根节点
    return {pq.top().first};
}

// 哈夫曼编码，对给定的字符进行编码
string huffmanCode(Node* root, char data, string code) {
    if (!root || root->data == data) {
        return code;
    }

    if (root->left && root->left->data == data) {
        return huffmanCode(root->left, data, code + "0");
    } else {
        return huffmanCode(root->right, data, code + "1");
    }
}

// 译码函数，接收编码和构建好的哈夫曼树
void decode(const vector<Node*>& tree, const string& encoded, string decoded) {
    Node* currentNode = tree[0]; // 从根节点开始
    for (char bit : encoded) {
        if (bit == '0') {
            currentNode = currentNode->left;
        } else {
            currentNode = currentNode->right;
        }

        // 如果到达叶子节点，则添加字符到解码结果
        if (!currentNode->left && !currentNode->right) {
            decoded += currentNode->data;
            currentNode = tree[0]; // 继续解码下一个字符
        }
    }
}

int main() {
    // 示例：输入字符频率向量
    vector<int> freqs = {9, 4, 3, 2, 5}; // {'e': 9, 't': 4, 'a': 3, 'o': 2, 'i': 5}
    vector<Node*> tree = buildHuffmanTree(freqs);

    // 对每个字符进行编码
    map<char, string> codes;
    for (auto& node : tree) {
        codes[node->data] = huffmanCode(tree[0], node->data, ""); // 假设根节点为整个树
    }

    // 测试编码和解码
    string encoded = codes['e']; // 编码 'e'
    string decoded = "";
    decode(tree, encoded, decoded);

    cout << "Encoded: " << encoded << endl;
    cout << "Decoded: " << decoded << endl;

    // 清理内存
    for (auto& node : tree) {
        delete node;
    }

    return 0;
}