使用c++实现哈夫曼树

哈夫曼树是一种基于字符频率来构建的最优二叉树，用于压缩和解压缩数据。在 C++ 中，可以通过以下步骤来实现哈夫曼树：

1. 定义结构体存储哈夫曼树节点信息，包括字符、权值、左右子节点等信息。

struct TreeNode {
    char ch;
    int freq;
    TreeNode *left, *right;
};

2. 构建哈夫曼树的主要过程是先将字符按照频率从小到大排序，然后将最小的两个节点合并为一个新节点，其权值为两个节点权值之和。重复此过程直到只剩下一个节点，即为哈夫曼树的根节点。可以使用 STL 中的 priority_queue 来实现节点合并的过程。

struct cmp {
    bool operator() (TreeNode* a, TreeNode* b) {
        return a->freq > b->freq;
    }
};
void buildHuffmanTree(vector<char>& chars, vector<int>& freqs) {
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
    for (int i = 0; i < chars.size(); ++i) {
        TreeNode* node = new TreeNode(chars[i], freqs[i]);
        pq.push(node);
    }
    while (pq.size() > 1) {
        TreeNode* left = pq.top(); pq.pop();
        TreeNode* right = pq.top(); pq.pop();
        TreeNode* parent = new TreeNode('#', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
}

3. 对于给定的字符串，可以通过哈夫曼树得到每个字符的编码，即左子节点对应编码为 0，右子节点对应编码为 1。可以使用递归的方式遍历哈夫曼树，生成编码表。

unordered_map<char, string> generateCodeMap(TreeNode* root) {
    unordered_map<char, string> codeMap;
    function<void(TreeNode*, string)> dfs = [&](TreeNode* node, string code) {
        if (!node) return;
        if (node->ch != '#') codeMap[node->ch] = code;
        dfs(node->left, code + "0");
        dfs(node->right, code + "1");
    };
    dfs(root, "");
    return codeMap;
}

以上就是使用 C++ 实现哈夫曼树的基本步骤。