哈夫曼树存储形式c++

哈夫曼树可以使用二叉树来存储，每个节点有左右子节点和权值。以下是一个基于C++的哈夫曼树结构体定义：

struct HuffmanNode {
    int weight; // 权值
    char ch; // 字符
    HuffmanNode *left, *right; // 左右子节点
    HuffmanNode(int w = 0, char c = '\0', HuffmanNode *l = nullptr, HuffmanNode *r = nullptr) :
        weight(w), ch(c), left(l), right(r) {}
};

typedef HuffmanNode *HuffmanTree;

这里使用了指针来表示哈夫曼树的节点，定义了一个结构体 `HuffmanNode` 来表示每个节点，其中包括该节点的权值、字符、左右子节点等信息。而 `HuffmanTree` 则是一个指向 `HuffmanNode` 的指针，表示整个哈夫曼树的根节点。

在实际使用时，我们可以使用数组来存储哈夫曼树的节点，然后通过指针来访问它们。下面是一个创建哈夫曼树的示例代码：

// 根据给定的权值构造哈夫曼树
HuffmanTree buildHuffmanTree(const vector<int>& weights) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, function<bool(HuffmanNode*, HuffmanNode*)>> q(
        [](HuffmanNode* a, HuffmanNode* b) { return a->weight >= b->weight; }
    );
    for (int i = 0; i < weights.size(); ++i) {
        if (weights[i] > 0) {
            q.push(new HuffmanNode(weights[i], char(i)));
        }
    }
    while (q.size() > 1) {
        auto left = q.top(); q.pop();
        auto right = q.top(); q.pop();
        auto parent = new HuffmanNode(left->weight + right->weight, '\0', left, right);
        q.push(parent);
    }
    return q.top();
}

这里使用了一个优先队列来维护待合并的哈夫曼树节点，每次取出两个权值最小的节点进行合并。最终，队列中仅剩一个节点，即为整个哈夫曼树的根节点，返回它即可。