C++ —哈夫曼树与哈夫曼编码，打印出编码及左右孩子

下面是用C++实现哈夫曼树和哈夫曼编码，并打印出编码及左右孩子的示例代码：

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

// 哈夫曼树节点
struct HuffmanNode {
    char ch;                // 字符
    int freq;               // 出现频率
    HuffmanNode *left, *right;  // 左右子节点

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

// 用于比较哈夫曼树节点的函数对象
class HuffmanNodeCompare {
public:
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;   // 以出现频率为优先级
    }
};

// 构建哈夫曼树并打印出编码及左右孩子
HuffmanNode* buildHuffmanTree(string str) {
    unordered_map<char, int> freqMap;   // 统计各字符出现频率
    for (char c : str) {
        freqMap[c]++;
    }

    priority_queue<HuffmanNode*, vector<HuffmanNode*>, HuffmanNodeCompare> pq;
    // 将字符及其出现频率构建成哈夫曼树节点，并加入优先队列
    for (auto it = freqMap.begin(); it != freqMap.end(); it++) {
        HuffmanNode* node = new HuffmanNode(it->first, it->second);
        pq.push(node);
    }

    // 逐步合并哈夫曼树节点，直到只剩下一个节点，即根节点
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        HuffmanNode* parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
        cout << "Parent: " << parent->freq << " (" << parent->ch << ")" << endl;
        if (left->ch != '$') {
            cout << "Left child of " << parent->freq << ": " << left->freq << " (" << left->ch << ")" << endl;
        }
        if (right->ch != '$') {
            cout << "Right child of " << parent->freq << ": " << right->freq << " (" << right->ch << ")" << endl;
        }
    }

    return pq.top();
}

// 递归遍历哈夫曼树，得到字符的哈夫曼编码
void getHuffmanCode(HuffmanNode* node, string code, unordered_map<char, string>& codeMap) {
    if (!node) {
        return;
    }
    if (node->ch != '$') {
        codeMap[node->ch] = code;
    }
    getHuffmanCode(node->left, code + "0", codeMap);
    getHuffmanCode(node->right, code + "1", codeMap);
}

int main() {
    string str = "hello world";
    HuffmanNode* root = buildHuffmanTree(str);
    unordered_map<char, string> codeMap;
    getHuffmanCode(root, "", codeMap);
    cout << "Huffman codes:" << endl;
    for (auto it : codeMap) {
        cout << it.first << ": " << it.second << endl;
    }

    return 0;
}

在构建哈夫曼树时，打印出每个节点的编码及左右孩子。在递归遍历哈夫曼树时，得到各字符的哈夫曼编码，并打印出来。