用c++写一份哈夫曼树编码

在C++中编写哈夫曼树（也称为最优二叉树或霍夫曼编码）的实现通常涉及以下几个步骤：

首先，你需要创建一个`HuffmanNode`类来表示节点，包含字符、频率、左子树和右子树等属性。然后构建一个优先队列用于存储频率，并实现插入和合并操作。

#include <queue>
#include <string>

class HuffmanNode {
public:
    char data;
    int freq;
    HuffmanNode* left, *right;

    HuffmanNode(char ch, int f) : data(ch), freq(f), left(nullptr), right(nullptr) {}
};

// 定义一个最小堆队列
typedef std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, std::greater<HuffmanNode*>> MinHeap;

// 插入节点到堆
void insert(HuffmanNode** heap, char ch, int freq) {
    HuffmanNode* newNode = new HuffmanNode(ch, freq);
    if (*heap->top() == nullptr || newNode->freq < (*heap)->top()->freq) {
        newNode->left = *heap->top();
        newNode->right = nullptr;
        *heap->top() = newNode;
    } else {
        newNode->right = *heap->top();
        newNode->left = nullptr;
        newNode->left->parent = newNode; // 更新父子关系
        heap->push(newNode);
    }
}

// 合并两个最小堆的顶部节点
HuffmanNode* mergeHeaps(MinHeap& heap1, MinHeap& heap2) {
    HuffmanNode* min1 = heap1.top(), *min2 = heap2.top();
    heap1.pop();
    heap2.pop();

    if (min1 == nullptr)
        return min2;
    else if (min2 == nullptr)
        return min1;

    if (min1->freq < min2->freq)
        min1->right = mergeHeaps(heap1, heap2);
    else
        min2->left = mergeHeaps(heap1, heap2);

    min1->left->parent = min1;
    min2->right->parent = min1;
    return min1;
}

最后，你可以通过一个递归函数来生成哈夫曼树并返回根节点，以及辅助函数生成编码表。

HuffmanNode* buildHuffmanTree(const std::vector<std::pair<char, int>>& freqs) {
    MinHeap huffTree;
    for (auto& pair : freqs)
        insert(&huffTree, pair.first, pair.second);

    while (huffTree.size() > 1)
        huffTree.push(mergeHeaps(huffTree, huffTree));

    return huffTree.top(); // 返回根节点
}

std::map<char, std::string> generateCodes(HuffmanNode* root) {
    std::map<char, std::string> codes;
    helperGenerateCodes(root, "", &codes);
    return codes;
}

void helperGenerateCodes(HuffmanNode* node, std::string code, std::map<char, std::string>* codes) {
    if (node == nullptr)
        return;

    if (node->left != nullptr)
        helperGenerateCodes(node->left, "0" + code, codes);
    if (node->right != nullptr)
        helperGenerateCodes(node->right, "1" + code, codes);

    (*codes)[node->data] = code;
}