哈夫曼树使用c++实现

哈夫曼树（Huffman Tree），也称为最优二叉树，是一种带权路径长度最短的二叉树，常用于数据压缩算法如 Huffman 编码。在 C++ 中实现哈夫曼树通常会包括以下几个步骤：

1. **构建优先队列**：用于存储节点及其权值，可以使用 `std::priority_queue` 或自定义结构体结合比较函数。

2. **创建节点**：每个节点包含权值、左子节点和右子节点。

3. **构造初始序列**：输入的字符与其出现频率形成一个序列。

4. **合并操作**：从队列中取出权值最小的两个节点，将它们合并成一个新的节点，新节点的权值是这两个节点之和，然后将其放入队列中。

5. **递归过程**：当队列中只剩下一个元素时，说明生成了完整的哈夫曼树，这个节点就是根节点。

6. **编码生成**：遍历哈夫曼树，从根节点开始，根据左孩子指向0，右孩子指向1的原则生成每个字符的编码。

下面是简单的 C++ 伪代码示例：

struct Node {
    char data;
    int freq;
    Node* left, *right;
};

Node* createNode(int freq) {
    // 创建节点并返回
}

void huffmanCoding(Node* root, std::string& codes) {
    // 递归生成编码
}

// 主函数
void buildHuffmanTree(std::vector<int>& frequencies, std::string& codes) {
    priority_queue<Node*, vector<Node*>, greater<Node*>> pq(frequencies.begin(), frequencies.end());
    // ... (按上述步骤实现)
}