C++实现哈夫曼树算法

C++实现哈夫曼树算法攻略

哈夫曼树，又称最优二叉树，是一种带权路径长度最短的二叉树。它常用于数据压缩和编码的算法中。

1. 哈夫曼树的定义

哈夫曼树是一种满足以下属性的二叉树：

1. 树中每个叶子节点都对应一个权值；
2. 树中每个非叶子节点的权值是其左右子树中权值之和；
3. 树的带权路径长度最小。

2. 哈夫曼编码的实现

哈夫曼编码是一种前缀编码，它把每个不同符号对应到一段等长的编码，使得解码时不会有歧义。编码的长度与该符号在文本中出现的频率有关。

3. 具体实现步骤

3.1 定义哈夫曼树节点结构体

定义一个节点结构体来存储哈夫曼树的信息，包括权值、左右子节点以及哈夫曼编码等。

struct HuffmanNode {
    int weight;             // 权值
    int parent, left, right;// 双亲链及左右孩子链
    string code;            // 结点的哈夫曼编码
};

3.2 定义比较器

定义比较器用于对哈夫曼树节点进行排序，保证构建哈夫曼树时权值较小的节点排在前面。

struct cmp {
    bool operator()(const HuffmanNode &a, const HuffmanNode &b) {
        return a.weight > b.weight;
    }
};

3.3 生成哈夫曼树

输入每个节点的权值，按权值从小到大排序后初始化哈夫曼树的n个叶子节点，再根据哈夫曼树的定义合并这些节点，最终生成完整的哈夫曼树。

priority_queue<HuffmanNode, vector<HuffmanNode>, cmp> huff_q;     // 优先队列
int n, m;

void init() {
    for (int i = 1; i <= n; i++) {
        cin >> node[i].weight;
        huff_q.push(node[i]);
    }
    m = (n << 1) - 1;   // 计算哈夫曼树节点总数
    for (int i = n + 1; i <= m; i++) {
        int p1 = huff_q.top().weight;
        huff_q.pop();
        int p2 = huff_q.top().weight;
        huff_q.pop();
        node[i].left = p1;
        node[i].right = p2;
        node[i].weight = p1 + p2;
        huff_q.push(node[i]);
    }
}

3.4 生成哈夫曼编码

对于哈夫曼树的每个叶子节点，由于左孩子编码为0，右孩子编码为1，我们可从叶子节点出发向根节点反向求出每个节点的哈夫曼编码。

void getHuffmanCode(int n) {
    int len = node[n].code.length();
    if (len) {
        return;
    }
    if (!node[n].parent) {
        return;
    }
    if (node[node[n].parent].left == n) {
        getHuffmanCode(node[n].parent);
        node[n].code = node[node[n].parent].code + '0';
    } else {
        getHuffmanCode(node[n].parent);
        node[n].code = node[node[n].parent].code + '1';
    }
}

3.5 示例说明

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    init();
    for (int i = 1; i <= n; i++) {
        getHuffmanCode(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << node[i].weight << " " << node[i].code << "\n";
    }
    return 0;
}

输入：

5
5 2 4 7 10

输出：

5 00001
2 100
4 001
7 01
10 0000

另一个示例：当输入为12 7 8 10时，得到的哈夫曼编码为：

12 0
7 11
8 100
10 101

4. 总结

哈夫曼树是一种非常有用的数据结构，它能够快速生成最优编码方案。本文中详细讲解了哈夫曼树算法的实现，包括定义节点结构体、优先队列的使用、哈夫曼树的生成以及哈夫曼编码的计算过程等。通过以上步骤，我们可以轻松实现哈夫曼树算法，并得到正确的编码结果。