哈夫曼树数据结构c++实现

哈夫曼树（Huffman Tree）是一种特殊的二叉树，它的构建基于贪心算法。哈夫曼树广泛应用于数据压缩领域。在哈夫曼编码中，每个字符对应一个唯一的编码，且不会出现任何一个编码是另一个编码的前缀，这种编码方式可以大大减少数据传输时的冗余。以下是哈夫曼树的C++实现。

#include <iostream>
#include <queue>

using namespace std;

// 哈夫曼树节点结构体
struct HuffmanNode {
    int value;              // 权值
    char ch;                // 字符
    HuffmanNode *left;      // 左儿子
    HuffmanNode *right;     // 右儿子
    HuffmanNode(int v = 0, char c = '\0', HuffmanNode *l = NULL, HuffmanNode *r = NULL) : value(v), ch(c), left(l), right(r) {}
};

// 比较函数，用于优先队列
struct cmp {
    bool operator() (HuffmanNode *a, HuffmanNode *b) {
        return a->value > b->value;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int *freq, char *ch, int n) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (int i = 0; i < n; i++) {
        pq.push(new HuffmanNode(freq[i], ch[i]));
    }
    while (pq.size() > 1) {
        HuffmanNode *left = pq.top(); pq.pop();
        HuffmanNode *right = pq.top(); pq.pop();
        HuffmanNode *node = new HuffmanNode(left->value + right->value, '\0', left, right);
        pq.push(node);
    }
    return pq.top();
}

// 遍历哈夫曼树，得到每个字符的哈夫曼编码
void traverseHuffmanTree(HuffmanNode *root, string code, string *huffmanCode) {
    if (!root) return;
    if (!root->left && !root->right) {
        huffmanCode[(int)root->ch] = code;
    }
    traverseHuffmanTree(root->left, code + "0", huffmanCode);
    traverseHuffmanTree(root->right, code + "1", huffmanCode);
}

// 主函数
int main() {
    int freq[] = { 5, 6, 9, 11, 14, 18, 25, 27 };
    char ch[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' };
    int n = sizeof(freq) / sizeof(int);
    HuffmanNode *root = buildHuffmanTree(freq, ch, n);
    string huffmanCode[256];
    traverseHuffmanTree(root, "", huffmanCode);
    for (int i = 0; i < n; i++) {
        cout << ch[i] << ": " << huffmanCode[(int)ch[i]] << endl;
    }
    return 0;
}