哈夫曼树c++

哈夫曼树（Huffman Tree）是一种带权路径长度最短的树，通常用于数据压缩算法中。下面是一个简单的 C++ 实现：

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

struct Node {
    int weight;  // 权值
    Node *left, *right;  // 左右子节点

    Node(int w): weight(w), left(nullptr), right(nullptr) {}
};

struct cmp {
    bool operator()(Node *a, Node *b) {
        return a->weight > b->weight;
    }
};

Node* buildHuffmanTree(int* freq, int n) {
    // 构建哈夫曼树
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (int i = 0; i < n; i++) {
        Node *node = new Node(freq[i]);
        pq.push(node);
    }

    while (pq.size() > 1) {
        Node *left = pq.top(); pq.pop();
        Node *right = pq.top(); pq.pop();
        Node *parent = new Node(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

void printHuffmanCode(Node *root, string code = "") {
    // 打印哈夫曼编码
    if (!root) {
        return;
    }
    if (!root->left && !root->right) {
        cout << code << " ";
    }
    printHuffmanCode(root->left, code + "0");
    printHuffmanCode(root->right, code + "1");
}

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

    Node *root = buildHuffmanTree(freq, n);
    printHuffmanCode(root);

    return 0;
}

程序中先定义了一个 `Node` 结构体来表示哈夫曼树的节点，然后定义了一个 `cmp` 结构体作为优先队列中的比较函数，按照节点的权值从小到大排序。接着通过 `buildHuffmanTree` 函数构建哈夫曼树，使用优先队列来实现。最后通过 `printHuffmanCode` 函数打印出哈夫曼编码。