(10)              (10)
    /    \            /    \
  (5)    (5)        (2)    (8)
        /   \             /   \
      (2)   (3)         (3)   (5)

                (55)
               /    \
            (25)    (30)
           /    \   /   \
         (12) (13)(14) (16)
               C    D   /  \
                    (5)  (9)
                     A    B

A: 100
B: 101
C: 00
D: 01
E: 11

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
using namespace std;

// 哈夫曼树节点
struct HuffmanNode {
    char ch;            // 字符（内部节点设为 '\0'）
    int freq;           // 频率（权值）
    HuffmanNode *left, *right;   // 左右子节点指针
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 用于最小堆的比较器：频率小的优先级高
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;  // 注意：最小堆需要 greater，即a.freq > b.freq时a优先级低
    }
};

// 递归生成编码，存入vector
// root: 当前节点，code: 当前路径编码，codes: 存放结果的数组（下标为字符ASCII码）
void getCodes(HuffmanNode* root, string code, vector<string>& codes) {
    if (!root) return;
    // 如果是叶子节点（有实际字符），记录编码
    if (!root->left && !root->right) {
        codes[root->ch] = code;
        return;
    }
    getCodes(root->left, code + "0", codes);
    getCodes(root->right, code + "1", codes);
}

// 递归释放整棵树的内存
void deleteTree(HuffmanNode* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    int n;  // 字符个数
    cout << "请输入字符个数: ";
    cin >> n;

    vector<char> chars(n);           // 存储字符
    vector<int> freqs(n);            // 存储对应频率
    cout << "请输入每个字符及其频率(例如 A 5):" << endl;
    for (int i = 0; i < n; i++) {
        cin >> chars[i] >> freqs[i];
    }

    // 使用优先队列（最小堆）存储节点指针
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (int i = 0; i < n; i++) {
        pq.push(new HuffmanNode(chars[i], freqs[i]));
    }

    // 构建哈夫曼树：不断取出两个最小节点合并
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();   // 最小权值的节点
        HuffmanNode* right = pq.top(); pq.pop();  // 次小权值的节点
        // 创建父节点，权值为两者之和，字符设为'\0'表示内部节点
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    HuffmanNode* root = pq.top(); // 最终根节点

    // 生成编码（ASCII可打印字符范围通常0~127，这里分配128就足够）
    vector<string> codes(128, "");
    getCodes(root, "", codes);

    // 输出每个字符的编码
    cout << "\n字符和对应的哈夫曼编码:" << endl;
    for (int i = 0; i < n; i++) {
        cout << chars[i] << " : " << codes[chars[i]] << endl;
    }

    // 计算压缩前后的总比特数（假设原来每个字符用8位固定编码）
    int originalTotal = 0, compressedTotal = 0;
    for (int i = 0; i < n; i++) {
        originalTotal += freqs[i] * 8;                     // 原编码8位
        compressedTotal += freqs[i] * codes[chars[i]].size(); // 哈夫曼编码长度
    }
    cout << "\n原始总比特数: " << originalTotal << endl;
    cout << "哈夫曼压缩后总比特数: " << compressedTotal << endl;
    cout << "压缩率: " << fixed << setprecision(2)
         << (double)compressedTotal / originalTotal * 100 << "%" << endl;

    // 释放所有动态内存
    deleteTree(root);

    return 0;
}

请输入字符个数: 5
请输入每个字符及其频率(例如 A 5):
A 5
B 9
C 12
D 13
E 16

字符和对应的哈夫曼编码:
A : 100
B : 101
C : 00
D : 01
E : 11

原始总比特数: 440
哈夫曼压缩后总比特数: 131
压缩率: 29.77%