用c++对给定的一组键值W=(5,2,9,11,8,3,7),试设计算法构造其相应的哈夫曼树

哈夫曼树（Huffman Tree），也称最优二叉树，是一种带权路径长度最短的二叉树，常用于数据压缩编码。在C++中构建哈夫曼树，我们可以按照以下步骤：

1. **创建优先队列**：将所有键值(这里为5, 2, 9, 11, 8, 3, 7)及其对应的频率存储为一个结构体，如`pair<int, int>`，然后放入优先队列（例如`std::priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>`），其中`greater<pair<int, int>>`使得频率小的元素排在前面。

2. **构建Huffman码**：
- 当队列非空时，取出两个频率最小的节点（即优先级最高的两个）。
- 将这两个节点合并成一个新的节点，新节点的频率是两个原节点频率之和，左孩子是第一个节点，右孩子是第二个节点。
- 将新节点插入到优先队列中，并替换掉原来的两个节点。
- 重复此过程，直到队列只剩下一个元素，它就是哈夫曼树的根节点。

3. **生成Huffman编码**：
- 从根节点开始，对于每个叶子节点，从前往后遍历整个构建过程中记录的路径信息，0表示向左走，1表示向右走。最终得到的01序列就是该叶子节点的Huffman码。

4. **编码过程**：对于给定的键值集合中的每个元素，查找其在哈夫曼树中的对应路径，生成的Huffman码即为其编码。

以下是简单的伪代码实现：

struct Node {
    int val;
    int freq;
    Node* left, *right;
};

Node* buildHuffmanTree(vector<pair<int, int>>& weights) {
    // 其他细节省略...
}

vector<string> generateCodes(Node* root) {
    // 其他细节省略...
}

void main() {
    vector<pair<int, int>> weights = { {5, 1}, {2, 1}, {9, 1}, {11, 1}, {8, 1}, {3, 1}, {7, 1} };
    Node* root = buildHuffmanTree(weights);
    vector<string> codes = generateCodes(root);

    // 对每个键值W应用其Huffman编码
    // ...
}