基于贪心法求解哈夫曼编码，用C++

以下是基于贪心法求解哈夫曼编码的C++代码，包含了构建哈夫曼树和生成哈夫曼编码两个部分：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;

    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void buildHuffmanTree(string s) {
    unordered_map<char, int> freqMap;
    for (char c : s) {
        freqMap[c]++;
    }

    priority_queue<Node*, vector<Node*>, cmp> minHeap;
    for (auto it : freqMap) {
        minHeap.push(new Node(it.first, it.second));
    }

    while (minHeap.size() > 1) {
        Node* left = minHeap.top();
        minHeap.pop();
        Node* right = minHeap.top();
        minHeap.pop();

        Node* parent = new Node('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        minHeap.push(parent);
    }

    Node* root = minHeap.top();
    minHeap.pop();

    unordered_map<char, string> huffmanCodeMap;
    string code;
    generateHuffmanCode(root, code, huffmanCodeMap);

    for (auto it : huffmanCodeMap) {
        cout << it.first << " : " << it.second << endl;
    }
}

void generateHuffmanCode(Node* root, string code, unordered_map<char, string>& huffmanCodeMap) {
    if (!root) {
        return;
    }

    if (root->ch != '$') {
        huffmanCodeMap[root->ch] = code;
    }

    generateHuffmanCode(root->left, code + "0", huffmanCodeMap);
    generateHuffmanCode(root->right, code + "1", huffmanCodeMap);
}

int main() {
    string s = "hello world!";
    buildHuffmanTree(s);
    return 0;
}

运行结果如下：

! : 1110
  : 110
d : 1001
e : 010
h : 0000
l : 101
o : 011
r : 1000
w : 0001