用C++利用二叉树结构实现哈夫曼编码，并给出代码

以下是用 C++ 实现哈夫曼编码的示例代码：

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

// 定义节点类
class Node {
public:
    char ch;          // 节点对应的字符
    int freq;         // 节点对应的出现频率
    Node* left;       // 左子树指针
    Node* right;      // 右子树指针
    Node(char ch, int freq) {
        this->ch = ch;
        this->freq = freq;
        this->left = nullptr;
        this->right = nullptr;
    }
};

// 定义比较函数，用于优先队列的排序
class Compare {
public:
    bool operator() (Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 定义哈夫曼树类
class HuffmanTree {
public:
    Node* root;       // 根节点指针
    unordered_map<char, string> codes;  // 哈夫曼编码表
    // 构造函数，传入字符数组和对应的出现频率数组
    HuffmanTree(char arr[], int freq[], int n) {
        priority_queue<Node*, vector<Node*>, Compare> pq;
        // 将每个字符及其出现频率作为一个节点，并插入优先队列
        for (int i = 0; i < n; i++) {
            Node* node = new Node(arr[i], freq[i]);
            pq.push(node);
        }
        // 依次取出频率最小的两个节点进行合并，直到只剩一个根节点
        while (pq.size() > 1) {
            Node* left = pq.top();
            pq.pop();
            Node* right = pq.top();
            pq.pop();
            int sum_freq = left->freq + right->freq;
            Node* new_node = new Node('\0', sum_freq);
            new_node->left = left;
            new_node->right = right;
            pq.push(new_node);
        }
        // 最后剩下的节点即为根节点
        root = pq.top();
        pq.pop();
        // 生成哈夫曼编码表
        generate_codes(root, "");
    }
    // 递归生成哈夫曼编码表
    void generate_codes(Node* node, string code) {
        if (node == nullptr) {
            return;
        }
        if (node->left == nullptr && node->right == nullptr) {
            codes[node->ch] = code;
        }
        generate_codes(node->left, code + "0");
        generate_codes(node->right, code + "1");
    }
    // 获取字符对应的哈夫曼编码
    string get_code(char ch) {
        return codes[ch];
    }
};

int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(arr) / sizeof(arr[0]);
    HuffmanTree tree(arr, freq, n);
    // 输出每个字符对应的哈夫曼编码
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " : " << tree.get_code(arr[i]) << endl;
    }
    return 0;
}

在以上示例代码中，我们定义了节点类 `Node`，用于表示哈夫曼树中的每个节点，包含字符 `ch`、出现频率 `freq`、左右子树指针 `left` 和 `right`。同时，我们定义了比较函数类 `Compare`，用于优先队列的排序。

我们还定义了哈夫曼树类 `HuffmanTree`，包含根节点指针 `root` 和哈夫曼编码表 `codes`。在构造函数中，我们依次将每个字符及其出现频率作为一个节点，并插入优先队列。然后，我们依次取出频率最小的两个节点进行合并，直到只剩一个根节点。最后，我们递归生成哈夫曼编码表，并提供了获取字符对应哈夫曼编码的方法 `get_code`。

在 `main` 函数中，我们定义了字符数组和对应的出现频率数组，并调用哈夫曼树类的构造函数生成哈夫曼树和哈夫曼编码表。最后，我们逐个输出每个字符对应的哈夫曼编码。