1#include <iostream>
2#include <vector>
3using namespace std;
4
5// 定义一个霍夫曼树节点的结构
6struct HuffmanNode {
7    string huffmanCode; // 存储霍夫曼编码
8    char value; // 存储节点代表的字符（在本例中未使用）
9    int weight; // 节点的权重
10    HuffmanNode *left; // 指向左子节点的指针
11    HuffmanNode *right; // 指向右子节点的指针
12};
13
14// 创建霍夫曼树
15HuffmanNode *huffmanTreeCreate(vector<HuffmanNode *> huffmanTreeNode) {
16    int times = huffmanTreeNode.size() - 1;
17    for (int i = 0; i < times; i++) {
18        int min1Idx = -1;
19        int min2Idx = -1;
20        // 找到权重最小的两个节点
21        for (int j = 0; j < huffmanTreeNode.size(); j++) {
22            if (min1Idx == -1 || huffmanTreeNode[j]->weight < huffmanTreeNode[min1Idx]->weight) {
23                min2Idx = min1Idx;
24                min1Idx = j;
25            } else if (min2Idx == -1 || huffmanTreeNode[j]->weight < huffmanTreeNode[min2Idx]->weight) {
26                min2Idx = j;
27            }
28        }
29        // 创建一个新节点，其子节点为找到的两个最小权重节点
30        HuffmanNode *node = new HuffmanNode;
31        node->left = huffmanTreeNode[min1Idx];
32        node->right = huffmanTreeNode[min2Idx];
33        node->weight = node->left->weight + node->right->weight; // 新节点的权重为两个子节点权重之和
34        // 从列表中移除已经使用的两个节点
35        if (min1Idx > min2Idx) {
36            huffmanTreeNode.erase(huffmanTreeNode.begin() + min1Idx);
37            huffmanTreeNode.erase(huffmanTreeNode.begin() + min2Idx);
38        } else {
39            huffmanTreeNode.erase(huffmanTreeNode.begin() + min2Idx);
40            huffmanTreeNode.erase(huffmanTreeNode.begin() + min1Idx);
41        }
42        huffmanTreeNode.push_back(node); // 将新节点加入列表中
43    }
44    return huffmanTreeNode[0]; // 返回霍夫曼树的根节点
45}
46
47// 使用中序遍历打印霍夫曼树的节点权重
48void inOrder(HuffmanNode *node) {
49    if (!node) {
50        return;
51    }
52    inOrder(node->left);
53    cout << node->weight << endl;
54    inOrder(node->right);
55}
56
57// 为霍夫曼树中的每个叶子节点生成霍夫曼编码
58void huffmanCoding(HuffmanNode *node, string code) {
59    if (!node->left && !node->right) {
60        cout << node->weight << " " << code << endl; // 打印叶子节点的权重和编码
61        return;
62    }
63    // 递归为左子树生成编码，编码加'0'
64    huffmanCoding(node->left, code + '0');
65    // 递归为右子树生成编码，编码加'1'
66    huffmanCoding(node->right, code + '1');
67}
68
69int main() {
70    int n = 0;
71    cin >> n; // 读取节点数量
72    vector<HuffmanNode *> huffmanTreeNode; // 存储所有节点的向量
73    for (int i = 0; i < n; i++) {
74        HuffmanNode *node = new HuffmanNode;
75        cin >> node->weight; // 读取节点的权重
76        node->left = NULL;
77        node->right = NULL;
78        huffmanTreeNode.push_back(node); // 将节点加入向量
79    }
80    HuffmanNode *root = huffmanTreeCreate(huffmanTreeNode); // 创建霍夫曼树
81    // inOrder(root); // 使用中序遍历打印树的节点权重（如果需要的话）
82    huffmanCoding(root, ""); // 为霍夫曼树生成编码
83    return 0;
84}

优先队列：[C:1, D:1, B:2, E:3, A:5]

优先队列：[B:2, CD:2, E:3, A:5]
    2
   / \
  C:1 D:1

1优先队列：[E:3, BCD:4, A:5]
2      4
3     / \
4    B:2  2
5        / \
6       C:1 D:1

1优先队列：[A:5, EBCD:7]
2        7
3       / \
4      E:3  4
5          / \
6         B:2  2
7             / \
8            C:1 D:1

112
2           /  \
3         A:5    7
4   / \
5  E:3  4
6      / \
7     B:2  2
8         / \
9        C:1 D:1