构造哈夫曼树c++源代码

以下是基于数组实现的哈夫曼树构造的C++源代码：

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

// 定义哈夫曼树节点结构体
struct HuffmanNode {
    int weight;             // 权值
    int parent, left, right;    // 父节点和左右子节点下标
};

// 定义优先队列比较函数
struct cmp {
    bool operator()(const HuffmanNode &a, const HuffmanNode &b) {
        return a.weight > b.weight;
    }
};

// 构造哈夫曼树
void HuffmanTree(HuffmanNode *huffmanTree, int *w, int n) {
    priority_queue<HuffmanNode, vector<HuffmanNode>, cmp> q;    // 定义小根堆优先队列
    int m = 2 * n - 1;  // 哈夫曼树节点数
    for (int i = 0; i < n; i++) {
        huffmanTree[i].weight = w[i];
        huffmanTree[i].parent = huffmanTree[i].left = huffmanTree[i].right = -1;
        q.push(huffmanTree[i]);
    }
    for (int i = n; i < m; i++) {
        HuffmanNode node1 = q.top(); q.pop();
        HuffmanNode node2 = q.top(); q.pop();
        huffmanTree[i].weight = node1.weight + node2.weight;
        huffmanTree[i].left = node1.weight < node2.weight ? node1.parent : node2.parent;
        huffmanTree[i].right = node1.weight >= node2.weight ? node1.parent : node2.parent;
        node1.parent = node2.parent = i;
        q.push(node1); q.push(node2);
    }
}

int main() {
    int w[] = { 5, 6, 8, 7, 15 };
    int n = sizeof(w) / sizeof(int);

    HuffmanNode *huffmanTree = new HuffmanNode[2 * n - 1];
    HuffmanTree(huffmanTree, w, n);

    for (int i = 0; i < 2 * n - 1; i++) {
        cout << huffmanTree[i].weight << " ";
    }
    cout << endl;

    delete[] huffmanTree;
    return 0;
}