为了提高通信的效率，在实际的通信中，要求设计长度不等的二进制编码，使任一字符的编码都不是另一个字符的编码的前缀，同时保证编码的信息量最小。哈夫曼编码能够满足以上特性。用学习到的二叉树的知识，编码实现哈夫曼编码算法

哈夫曼编码（Huffman Coding）是一种基于贪心策略的最优二进制编码方法，它被用于数据压缩中，旨在为每个出现频率较低的字符分配较短的编码，而频繁出现的字符则分配较长的编码，从而达到信息量最小的目的。这个过程可以通过构建一棵哈夫曼树（也称霍夫曼树或最优二叉树）来完成。

以下是一个简单的步骤介绍如何实现哈夫曼编码：

1. **计算频率**：首先统计每个字符出现的次数（频率）。

2. **创建初始集合**：将字符及其频率作为一个个节点放入一个空的优先队列或堆中。在这个阶段，所有节点都是叶子节点，表示原始的字符。

3. **合并节点**：重复以下操作直到只剩下一个节点：从堆顶取出两个频率最低的节点（通常称为“父”节点），将它们合并成一个新的节点，新节点的频率是这两个子节点频率之和。将新节点放回堆中。

4. **构建哈夫曼树**：每次合并后堆的顶部总是剩余节点中的最小频节点，所以最后堆顶的就是树的根节点。

5. **生成编码**：从根节点开始遍历树，对于每个非叶节点，如果它的左孩子先访问，则给该节点的字符分配编码为0；如果右孩子先访问，则分配编码为1。沿着路径下来，就得到了字符对应的二进制编码。

6. **编码表生成**：记录下每个字符与其对应编码的关系。

下面是简单代码示例，使用了`priority_queue`（C++标准库）来实现优先队列：

#include <queue>

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

// 插入节点、删除节点等操作略...

Node* HuffmanCoding(char* input, int freq[], int n) {
    std::priority_queue<Node*, std::vector<Node*>, std::greater<Node*>> huffTree;

    // 填充节点并加入优先级队列
    for (int i = 0; i < n; ++i)
        huffTree.push(new Node{input[i], freq[i], NULL, NULL});

    while (huffTree.size() != 1) {
        Node* left = huffTree.top(); huffTree.pop();
        Node* right = huffTree.top(); huffTree.pop();

        // 创建新的节点，将其添加回堆
        Node* newNode = new Node{0, left->freq + right->freq, left, right};
        huffTree.push(newNode);
    }

    return huffTree.top();
}

void generateCodes(Node* root, std::string& codes, char* input) {
    if (!root)
        return;

    if (root->data != 0)
        codes[root->data - 1] = '0';
    else
        codes[root->data - 1] = '1';

    generateCodes(root->left, codes, input);
    generateCodes(root->right, codes, input);
}

// 使用时
int main() {
    // ... 输入数据频率数组 ...
    Node* root = HuffmanCoding(input, freqs, n);
    std::string codes[n];
    generateCodes(root, codes, input);

    // 输出编码表
    // codes[] now contains the Huffman codes for each character
    // ...

    return 0;
}