构造哈夫曼树实现c++

构造哈夫曼树是一种常用的数据压缩算法，下面是C++实现哈夫曼树的简单介绍：

1. 定义哈夫曼树的节点结构体，包括字符、权值、左右子节点等信息。

2. 定义一个哈夫曼树的节点比较器，用于按照权值从小到大排序。

3. 构造哈夫曼树时，首先将所有的字符和权值存储到一个vector中，并按照权值从小到大排序。

4. 从vector中取出前两个节点，将它们合并成一个新节点，并将新节点的权值设置为前两个节点的权值之和。

5. 将新节点插入到vector中，并按照权值从小到大排序。

6. 重复步骤4和5，直到vector中只剩下一个节点，此时就构造完成了哈夫曼树。

下面是一个C++实现哈夫曼树的例子：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct HuffmanNode {
    char c;
    int weight;
    HuffmanNode* left;
    HuffmanNode* right;

    HuffmanNode(char _c, int _weight) : c(_c), weight(_weight), left(nullptr), right(nullptr) {}
};

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

void buildHuffmanTree(vector<HuffmanNode*>& nodes) {
    while (nodes.size() > 1) {
        sort(nodes.begin(), nodes.end(), Compare());
        HuffmanNode* left = nodes;
        HuffmanNode* right = nodes;
        nodes.erase(nodes.begin(), nodes.begin() + 2);
        HuffmanNode* parent = new HuffmanNode('\0', left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        nodes.push_back(parent);
    }
}

int main() {
    string input = "hello world";
    vector<int> weights(256, 0);
    for (char c : input) {
        weights[c]++;
    }
    vector<HuffmanNode*> nodes;
    for (int i = 0; i < 256; i++) {
        if (weights[i] > 0) {
            nodes.push_back(new HuffmanNode((char)i, weights[i]));
        }
    }
    buildHuffmanTree(nodes);
    return 0;
}