用数据结构编写哈夫曼树的构造

哈夫曼树是一种用于数据压缩的树形数据结构，其构造过程涉及到使用优先队列和贪心算法。以下是用C++代码实现哈夫曼树的构造过程。

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 哈夫曼树结点的定义
struct HuffmanNode {
    int weight;             // 权值
    int parent, left, right;// 父结点、左子结点、右子结点在数组中的下标
};

// 哈夫曼树的构造函数
void BuildHuffmanTree(HuffmanNode* huffmanTree, int n, int* weights) {
    // 优先队列按权值从小到大排序
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < n; ++i) {
        huffmanTree[i].weight = weights[i];
        huffmanTree[i].parent = huffmanTree[i].left = huffmanTree[i].right = -1;
        q.push(i);
    }

    // 构造哈夫曼树
    for (int i = n; i < 2*n-1; ++i) {
        int x = q.top();
        q.pop();
        int y = q.top();
        q.pop();
        huffmanTree[x].parent = huffmanTree[y].parent = i;
        huffmanTree[i].left = x;
        huffmanTree[i].right = y;
        huffmanTree[i].weight = huffmanTree[x].weight + huffmanTree[y].weight;
        q.push(i);
    }
}

int main() {
    int weights[] = { 5, 6, 8, 7, 15 };
    int n = sizeof(weights) / sizeof(weights[0]);
    HuffmanNode huffmanTree[n*2-1];

    BuildHuffmanTree(huffmanTree, n, weights);

    return 0;
}

在以上实现中，我们使用了一个优先队列来维护哈夫曼树结点的排序。每次从队列中取出两个权值最小的结点，合并成一个新的结点，直到队列中只剩一个结点，即为哈夫曼树的根结点。构造过程的时间复杂度为 O(nlogn)。