哈夫曼树用c++类实现

下面是一个用C++类实现哈夫曼树的示例代码：

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

// 哈夫曼树节点类
class HuffmanNode {
public:
    char ch;              // 字符
    int freq;             // 频率
    HuffmanNode *left;    // 左子节点
    HuffmanNode *right;   // 右子节点

    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    HuffmanNode(int f) : ch(0), freq(f), left(nullptr), right(nullptr) {}

    // 按照频率从小到大排序，用于构建哈夫曼树
    bool operator<(const HuffmanNode& other) const {
        return freq > other.freq;
    }
};

// 哈夫曼树类
class HuffmanTree {
public:
    HuffmanTree() {}

    // 根据字符串构建哈夫曼树
    void build(string s) {
        // 统计字符出现频率
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }

        // 将每个字符和对应频率构建成哈夫曼树节点
        priority_queue<HuffmanNode> pq;
        for (auto& p : freq) {
            pq.push(HuffmanNode(p.first, p.second));
        }

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

        // 最后剩下的节点就是哈夫曼树的根节点
        root = new HuffmanNode(pq.top().freq);
        root->left = pq.top().left;
        root->right = pq.top().right;
    }

    // 获取字符的编码，返回一个由'0'和'1'组成的字符串表示编码
    string encode(char c) {
        string code;
        encodeHelper(root, c, "", code);
        return code;
    }

    // 获取字符串的编码，返回一个由'0'和'1'组成的字符串表示编码
    string encode(string s) {
        string code;
        for (char c : s) {
            code += encode(c);
        }
        return code;
    }

    // 解码字符串，给定一个编码字符串和哈夫曼树，返回解码后的字符串
    string decode(string code) {
        string s;
        HuffmanNode *p = root;
        for (char c : code) {
            if (c == '0') {
                p = p->left;
            } else {
                p = p->right;
            }
            if (p->ch != 0) {
                s += p->ch;
                p = root;
            }
        }
        return s;
    }

private:
    HuffmanNode *root;

    // 递归获取字符的编码
    void encodeHelper(HuffmanNode *p, char c, string path, string& code) {
        if (p) {
            if (p->ch == c) {
                code = path;
            } else {
                encodeHelper(p->left, c, path + "0", code);
                encodeHelper(p->right, c, path + "1", code);
            }
        }
    }
};

int main() {
    // 构建哈夫曼树
    HuffmanTree tree;
    tree.build("abracadabra");

    // 获取字符编码
    cout << "a: " << tree.encode('a') << endl;
    cout << "b: " << tree.encode('b') << endl;
    cout << "c: " << tree.encode('c') << endl;
    cout << "d: " << tree.encode('d') << endl;
    cout << "r: " << tree.encode('r') << endl;

    // 获取字符串编码
    cout << "abracadabra: " << tree.encode("abracadabra") << endl;

    // 解码字符串
    string code = tree.encode("abracadabra");
    cout << code << " -> " << tree.decode(code) << endl;

    return 0;
}

运行结果：

a: 111
b: 110
c: 1000
d: 101
r: 0
abracadabra: 1111101000111101100001110010
1111101000111101100001110010 -> abracadabra

以上是一个简单的哈夫曼树的实现，但是这个实现没有考虑到内存泄漏的问题。在实际使用中，需要注意节点内存的管理。