哈夫曼编码

💡 打个比方

上一课建好了哈夫曼树，这一课给它发门牌号：规定往左走记 0、往右走记 1，从根走到每个字母叶子的路上经过的方向，连起来就是这个字母的编码。就像小区地址："3 号楼 → 左拐 → 右拐"，走到门口刚好是 "3-左-右"。门牌越短的楼，是住得越"热闹"（出现越频繁）的楼。

更妙的是：哈夫曼树的每个字母都在叶子上，所以一个字母的门牌号绝不会是另一个字母门牌号的"开头"——送信的人读 01 串时永远不会读串！这叫前缀码。

🖼️ 大图看明白

沿用上一课的树（A=1、B=4、C=6、D=8、E=10）。边上标好左 0 右 1，每个字母的"门牌号"（编码）就出来了。

💻 完整代码

建树（复用上一课）→ DFS 生成每个字母的编码 → 编码报文 → 在树上走一遍解码，全流程一个文件搞定。

// 哈夫曼编码：建树 → 生成编码表 → 编/解码
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int w, ch, l, r;   // 权重/字母编号/左右孩子（0 = 无）
    Node(int weight, int c) : w(weight), ch(c), l(0), r(0) {}
};

int main() {
    int freq[] = {1, 4, 6, 8, 10};   // A B C D E
    int n = 5;
    vector<Node> pool;
    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;
    for (int i = 0; i < n; i++) {
        pool.push_back(Node(freq[i], i));
        pq.push({freq[i], i});
    }
    while (pq.size() > 1) {
        int a = pq.top().second; pq.pop();   // 较轻放左
        int b = pq.top().second; pq.pop();
        pool.push_back(Node(pool[a].w + pool[b].w, -1));
        int id = (int)pool.size() - 1;
        pool[id].l = a;  pool[id].r = b;
        pq.push({pool[id].w, id});
    }
    int root = pq.top().second;

    // DFS 生成编码表：左 0 右 1
    vector<string> code(n);
    function<void(int, string&)> dfs = [&](int id, string &s) {
        if (pool[id].ch >= 0) { code[pool[id].ch] = s; return; }
        s.push_back('0'); dfs(pool[id].l, s); s.pop_back();
        s.push_back('1'); dfs(pool[id].r, s); s.pop_back();
    };
    string path;
    dfs(root, path);
    for (int i = 0; i < n; i++)
        cout << (char)('A'+i) << " = " << code[i] << endl;
    // A = 000 / B = 001 / C = 01 / D = 10 / E = 11

    // 编码报文 "CEC"
    string msg = "CEC", out;
    for (char c : msg) out += code[c - 'A'];
    cout << "encode: " << out << endl;   // 011101

    // 解码：沿树走，踩到叶子输出字母、回根
    string bits = out, plain;
    int cur = root;
    for (char b : bits) {
        cur = (b == '0') ? pool[cur].l : pool[cur].r;
        if (pool[cur].ch >= 0) {
            plain += (char)('A' + pool[cur].ch);
            cur = root;
        }
    }
    cout << "decode: " << plain << endl;  // CEC
    return 0;
}

✋ 你来试试