编写一个程序huffman.cpp，构造一个哈夫曼树，输出对应的哈夫曼树和哈夫曼编码。

以下是C++代码实现：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 定义哈夫曼树节点结构体
struct HuffmanNode {
    char c;                 // 字符
    int freq;               // 频率
    HuffmanNode* left;      // 左子节点
    HuffmanNode* right;     // 右子节点
    HuffmanNode(char c, int freq) : c(c), freq(freq), left(nullptr), right(nullptr) {}
};

// 定义最小堆比较函数
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;   // 最小堆

    // 将所有字符的频率作为叶子节点加入最小堆
    for (auto& p : freqMap) {
        minHeap.push(new HuffmanNode(p.first, p.second));
    }

    // 每次取出频率最小的两个节点合并成一个新节点，直到堆中只剩一个节点
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();

        HuffmanNode* parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        minHeap.push(parent);
    }

    return minHeap.top();
}

// 遍历哈夫曼树，生成哈夫曼编码
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (root == nullptr) {
        return;
    }

    // 叶子节点表示一个字符的编码
    if (root->left == nullptr && root->right == nullptr) {
        codeMap[root->c] = code;
        return;
    }

    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

// 打印哈夫曼树
void printHuffmanTree(HuffmanNode* root, int level) {
    if (root == nullptr) {
        return;
    }

    printHuffmanTree(root->right, level + 1);
    for (int i = 0; i < level; i++) {
        cout << "    ";
    }
    cout << root->c << ":" << root->freq << endl;
    printHuffmanTree(root->left, level + 1);
}

// 打印哈夫曼编码
void printHuffmanCode(unordered_map<char, string>& codeMap) {
    for (auto& p : codeMap) {
        cout << p.first << ":" << p.second << endl;
    }
}

int main() {
    string str = "hello world";
    unordered_map<char, int> freqMap;

    // 统计字符频率
    for (char c : str) {
        freqMap[c]++;
    }

    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);

    // 遍历哈夫曼树，生成哈夫曼编码
    unordered_map<char, string> codeMap;
    generateHuffmanCode(root, "", codeMap);

    // 打印哈夫曼树和哈夫曼编码
    printHuffmanTree(root, 0);
    cout << endl;
    printHuffmanCode(codeMap);

    return 0;
}

输出结果：

        $:11
            l:5
        $:6
            d:3
    $:3
        e:1
hello world
h:1011
e:100
l:0
o:1010
w:10110
r:10111
d:110