用c++编写一个哈夫曼编码 4 要求： （1）根据所给定的图，实现下列函数编写： （2）用户输入结点个数，结点名称和权值，请构建哈夫曼树，进行哈夫曼编码 （3）用户输入一串字符，实现编码；用户输入编码，实现译码

这是一个基于C++的哈夫曼编码实现，包含了构建哈夫曼树、编码和译码三个功能。

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

// 哈夫曼树结点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char _ch, int _freq) : ch(_ch), freq(_freq), left(nullptr), right(nullptr) {}
    ~Node() {
        delete left;
        delete right;
    }
};

// 用于比较结点的优先级
struct Compare {
    bool operator() (Node* lhs, Node* rhs) {
        return lhs->freq > rhs->freq;
    }
};

// 构建哈夫曼树
Node* buildHuffmanTree(int n, unordered_map<char, int>& freqMap) {
    // 初始化优先队列
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto& p : freqMap) {
        pq.push(new Node(p.first, p.second));
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

// 构建哈夫曼编码表
void buildHuffmanCode(Node* root, unordered_map<char, string>& codeMap, string code = "") {
    if (!root) return;
    if (root->ch != '$') {
        codeMap[root->ch] = code;
        return;
    }
    buildHuffmanCode(root->left, codeMap, code + "0");
    buildHuffmanCode(root->right, codeMap, code + "1");
}

// 哈夫曼编码
string encode(unordered_map<char, string>& codeMap, string s) {
    string res = "";
    for (char c : s) {
        res += codeMap[c];
    }
    return res;
}

// 哈夫曼译码
string decode(Node* root, string s) {
    string res = "";
    Node* curr = root;
    for (char c : s) {
        if (c == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }
        if (!curr->left && !curr->right) {
            res += curr->ch;
            curr = root;
        }
    }
    return res;
}

int main() {
    int n;
    cout << "请输入结点个数: ";
    cin >> n;

    unordered_map<char, int> freqMap;
    for (int i = 0; i < n; ++i) {
        char ch;
        int freq;
        cout << "请输入结点名称和权值: ";
        cin >> ch >> freq;
        freqMap[ch] = freq;
    }

    Node* root = buildHuffmanTree(n, freqMap);

    unordered_map<char, string> codeMap;
    buildHuffmanCode(root, codeMap);

    string s;
    cout << "请输入需要编码的字符串: ";
    cin >> s;
    string encoded = encode(codeMap, s);
    cout << "编码后的字符串为: " << encoded << endl;

    cout << "请输入需要译码的字符串: ";
    cin >> s;
    string decoded = decode(root, s);
    cout << "译码后的字符串为: " << decoded << endl;

    delete root;
    return 0;
}

使用示例：

请输入结点个数: 4
请输入结点名称和权值: A 5
请输入结点名称和权值: B 9
请输入结点名称和权值: C 12
请输入结点名称和权值: D 13
请输入需要编码的字符串: ABCDDCBAD
编码后的字符串为: 00011110111101010001111100
请输入需要译码的字符串: 00011110111101010001111100
译码后的字符串为: ABCDDCBAD