哈夫曼树的定义和构造、哈夫曼编码
贪心造出最省空间的前缀编码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    // 6 个字符的出现频率（权重）
    long long w[] = {5, 9, 12, 13, 16, 45};
    int n = 6;
    priority_queue<long long, vector<long long>, greater<long long>> pq; // 小根堆
    for (int i = 0; i < n; i++) pq.push(w[i]);
    long long wpl = 0;
    cout << "合并过程（每次取两个最小权重的结点合并）：" << endl;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        long long s = a + b;
        cout << a << " + " << b << " = " << s << endl;
        wpl += s;          // 每次合并产生的新结点权重，累加起来就是 WPL
        pq.push(s);
    }
    cout << "带权路径长度 WPL = " << wpl << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
using namespace std;

struct Node {
    char ch;            // 叶子存字符；内部结点存 '\0'
    int w;
    Node *l, *r;
    Node(char c, int ww) : ch(c), w(ww), l(nullptr), r(nullptr) {}
};

// 按权重升序（stable_sort 保证权重相同时顺序稳定 → 输出确定）
bool cmp(Node* a, Node* b) { return a->w < b->w; }

void dfs(Node* u, const string& code, vector<pair<char,string>>& res) {
    if (!u) return;
    if (u->ch != '\0') {            // 叶子：记录 字符 → 哈夫曼编码
        res.push_back({u->ch, code});
        return;
    }
    dfs(u->l, code + "0", res);     // 左分支记 0
    dfs(u->r, code + "1", res);     // 右分支记 1
}

int main() {
    // 字符与频率
    Node* init[] = { new Node('A',5), new Node('B',9), new Node('C',12),
                     new Node('D',13), new Node('E',16), new Node('F',45) };
    vector<Node*> v(init, init + 6);

long long wpl = 0;
    while (v.size() > 1) {
        stable_sort(v.begin(), v.end(), cmp);
        Node* a = v[0];      // 最小
        Node* b = v[1];      // 次小
        Node* par = new Node('\0', a->w + b->w);
        par->l = a; par->r = b;
        wpl += par->w;       // 内部结点权重累加 = WPL
        v.erase(v.begin()); v.erase(v.begin());
        v.push_back(par);
    }

vector<pair<char,string>> res;
    dfs(v[0], "", res);
    sort(res.begin(), res.end());   // 按字符排序，输出更整齐

cout << "字符  频率  哈夫曼编码" << endl;
    int freq[] = {5,9,12,13,16,45}; // 与 A..F 对应
    for (auto& p : res) {
        int f = freq[p.first - 'A'];
        cout << p.first << "     " << f << "     " << p.second << endl;
    }
    cout << "带权路径长度 WPL = " << wpl << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
using namespace std;

struct Node {
    char ch;
    int w;
    Node *l, *r;
    Node(char c, int ww) : ch(c), w(ww), l(nullptr), r(nullptr) {}
};

bool cmp(Node* a, Node* b) { return a->w < b->w; }

// 由哈夫曼树生成 字符→编码 映射
void build_code(Node* u, const string& code, vector<pair<char,string>>& mp) {
    if (!u) return;
    if (u->ch != '\0') { mp.push_back({u->ch, code}); return; }
    build_code(u->l, code + "0", mp);
    build_code(u->r, code + "1", mp);
}

// 由编码串沿树走回字符
string decode(Node* root, const string& bits) {
    string out;
    Node* cur = root;
    for (char c : bits) {
        cur = (c == '0') ? cur->l : cur->r;
        if (cur->ch != '\0') { out += cur->ch; cur = root; }
    }
    return out;
}

int main() {
    Node* init[] = { new Node('A',5), new Node('B',9), new Node('C',12),
                     new Node('D',13), new Node('E',16), new Node('F',45) };
    vector<Node*> v(init, init + 6);
    while (v.size() > 1) {
        stable_sort(v.begin(), v.end(), cmp);
        Node* a = v[0], *b = v[1];
        Node* par = new Node('\0', a->w + b->w);
        par->l = a; par->r = b;
        v.erase(v.begin()); v.erase(v.begin()); v.push_back(par);
    }

vector<pair<char,string>> mp;
    build_code(v[0], "", mp);
    sort(mp.begin(), mp.end());

string msg = "ABFCADE";                 // 待压缩的报文
    string bits;
    for (char c : msg)
        for (auto& p : mp) if (p.first == c) { bits += p.second; break; }

cout << "原报文：      " << msg << endl;
    cout << "哈夫曼编码：  " << bits << endl;
    cout << "解码结果：    " << decode(v[0], bits) << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
using namespace std;
struct Node { char ch; int w; Node *l, *r; Node(char c, int ww) : ch(c), w(ww), l(nullptr), r(nullptr) {} };
bool cmp(Node* a, Node* b) { return a->w < b->w; }
void dfs(Node* u, const string& code, vector<pair<char,string>>& r) {
    if (!u) return;
    if (u->ch != '\0') { r.push_back({u->ch, code}); return; }
    dfs(u->l, code + "0", r); dfs(u->r, code + "1", r);
}
int main() {
    Node* init[] = { new Node('A',2), new Node('B',4), new Node('C',5), new Node('D',7) };
    vector<Node*> v(init, init + 4);
    long long wpl = 0;
    while (v.size() > 1) {
        stable_sort(v.begin(), v.end(), cmp);
        Node* a = v[0]; Node* b = v[1];
        Node* par = new Node('\0', a->w + b->w);
        par->l = a; par->r = b; wpl += par->w;
        v.erase(v.begin()); v.erase(v.begin()); v.push_back(par);
    }
    vector<pair<char,string>> res; dfs(v[0], "", res); sort(res.begin(), res.end());
    cout << "字符  频率  哈夫曼编码" << endl;
    int freq[] = {2,4,5,7};
    for (auto& p : res) cout << p.first << "     " << freq[p.first-'A'] << "     " << p.second << endl;
    cout << "WPL = " << wpl << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
using namespace std;
struct Node { char ch; int w; Node *l, *r; Node(char c, int ww) : ch(c), w(ww), l(nullptr), r(nullptr) {} };
bool cmp(Node* a, Node* b) { return a->w < b->w; }
void build_code(Node* u, const string& code, vector<pair<char,string>>& mp) {
    if (!u) return;
    if (u->ch != '\0') { mp.push_back({u->ch, code}); return; }
    build_code(u->l, code + "0", mp); build_code(u->r, code + "1", mp);
}
string decode(Node* root, const string& bits) {
    string out; Node* cur = root;
    for (char c : bits) { cur = (c == '0') ? cur->l : cur->r; if (cur->ch != '\0') { out += cur->ch; cur = root; } }
    return out;
}
int main() {
    Node* init[] = { new Node('A',1), new Node('B',2), new Node('C',3), new Node('D',4) };
    vector<Node*> v(init, init + 4);
    while (v.size() > 1) {
        stable_sort(v.begin(), v.end(), cmp);
        Node* a = v[0]; Node* b = v[1];
        Node* par = new Node('\0', a->w + b->w);
        par->l = a; par->r = b; v.erase(v.begin()); v.erase(v.begin()); v.push_back(par);
    }
    vector<pair<char,string>> mp; build_code(v[0], "", mp); sort(mp.begin(), mp.end());
    string msg = "ABCD"; string bits;
    for (char c : msg) for (auto& p : mp) if (p.first == c) { bits += p.second; break; }
    cout << "原报文：     " << msg << endl;
    cout << "哈夫曼编码： " << bits << endl;
    cout << "解码结果：   " << decode(v[0], bits) << endl;
    return 0;
}