c++:哈夫曼树的代码

C++中的哈夫曼树是一种用于数据压缩的树形结构。下面是一个简单的C++代码示例，用于构建哈夫曼树：

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

// 哈夫曼树节点
struct HuffmanNode {
    int data; // 数据
    HuffmanNode* left; // 左子节点
    HuffmanNode* right; // 右子节点
};

// 哈夫曼树比较函数
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->data > b->data;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int freq[], int n) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;

    // 创建叶子节点并加入优先队列
    for (int i = 0; i < n; i++) {
        HuffmanNode* node = new HuffmanNode();
        node->data = freq[i];
        node->left = nullptr;
        node->right = nullptr;
        pq.push(node);
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();

        HuffmanNode* parent = new HuffmanNode();
        parent->data = left->data + right->data;
        parent->left = left;
        parent->right = right;

        pq.push(parent);
    }

    return pq.top();
}

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

    if (root->left == nullptr && root->right == nullptr) {
        cout << root->data << ": " << code << endl;
    }

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

int main() {
    int freq[] = {5, 9, 12, 13, 16, 45}; // 数据频率
    int n = sizeof(freq) / sizeof(freq);

    HuffmanNode* root = buildHuffmanTree(freq, n);

    cout << "Huffman Tree:" << endl;
    printHuffmanTree(root, "");

    return 0;
}

这段代码实现了哈夫曼树的构建和打印功能。首先，通过优先队列（最小堆）将频率数组中的元素转化为叶子节点，并按照频率从小到大的顺序加入队列。然后，循环从队列中取出两个频率最小的节点，合并为一个新的父节点，并将父节点加入队列。最终，队列中只剩下一个节点，即为哈夫曼树的根节点。

打印哈夫曼树时，采用递归的方式遍历树的所有节点。当遍历到叶子节点时，输出节点的数据和对应的编码（0表示左子节点，1表示右子节点）。