实现哈夫曼树构造 数据结构 C++

以下是C++实现哈夫曼树构造的代码和解释：

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

// 定义哈夫曼树结点
struct HuffmanTreeNode {
    int weight; // 结点的权重
    int value; // 结点的值
    HuffmanTreeNode* LChild; // 结点的左孩子
    HuffmanTreeNode* RChild; // 结点的右孩子
};

// 定义比较函数，用于优先队列中结点的排序
struct cmp {
    bool operator()(HuffmanTreeNode* a, HuffmanTreeNode* b) {
        return a->weight > b->weight;
    }
};

// 构造哈夫曼树
HuffmanTreeNode* buildHuffmanTree(int* weight, int n) {
    priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, cmp> q;
    // 将所有结点加入优先队列
    for (int i = 0; i < n; i++) {
        HuffmanTreeNode* node = new HuffmanTreeNode;
        node->weight = weight[i];
        node->value = i;
        node->LChild = NULL;
        node->RChild = NULL;
        q.push(node);
    }
    // 不断取出队列中权值最小的两个结点，合并成一个新结点，再加入队列
    while (q.size() > 1) {
        HuffmanTreeNode* node1 = q.top();
        q.pop();
        HuffmanTreeNode* node2 = q.top();
        q.pop();
        HuffmanTreeNode* newNode = new HuffmanTreeNode;
        newNode->weight = node1->weight + node2->weight;
        newNode->value = -1;
        newNode->LChild = node1;
        newNode->RChild = node2;
        q.push(newNode);
    }
    // 队列中最后剩下的结点即为哈夫曼树的根结点
    return q.top();
}

int main() {
    int weight[] = {5, 2, 4, 7, 1, 3, 6};
    int n = sizeof(weight) / sizeof(int);
    HuffmanTreeNode* root = buildHuffmanTree(weight, n);
    return 0;
}

解释：

1. 定义哈夫曼树结点，包括权重、值、左孩子和右孩子。

2. 定义比较函数cmp，用于优先队列中结点的排序。这里采用小根堆，即权重小的结点排在前面。

3. 构造哈夫曼树的函数buildHuffmanTree，输入参数为权重数组和数组长度，返回值为哈夫曼树的根结点。

4. 在buildHuffmanTree函数中，首先将所有结点加入优先队列中。

5. 然后不断取出队列中权值最小的两个结点，合并成一个新结点，再加入队列。这里采用贪心策略，即每次取出权值最小的两个结点合并，保证最终构造出的哈夫曼树是最优的。

6. 最后，队列中最后剩下的结点即为哈夫曼树的根结点，返回即可。