哈夫曼树编码问题(数据压缩)C++

### C++ 实现哈夫曼树编码数据压缩算法

#### 构建哈夫曼树
为了实现基于哈夫曼树的数据压缩，在C++中首先要创建哈夫曼树。这涉及到计算输入字符串中各个字符的频率，并以此为基础构建最小带权路径长度（WPL）的二叉树。

struct MinHeapNode {
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;

    MinHeapNode(char data, unsigned freq) : data(data), freq(freq),
                                            left(nullptr), right(nullptr) {}
};

此结构体用于表示哈夫曼树中的节点，其中`data`存储字符而`freq`保存该字符出现次数[^3]。

接着通过优先队列来辅助构造过程：

#include <queue>
using namespace std;

class compare {
public:
    bool operator()(MinHeapNode* l, MinHeapNode* r) {
        return (l->freq > r->freq);
    }
};

priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;

上述代码片段定义了一个比较器类以及一个最小堆，用来高效管理待处理节点列表并始终能够快速获取当前具有最低频次的两个元素组合成新的内部节点直至形成完整的哈夫曼树[^4]。

#### 生成哈夫曼编码表
一旦获得了最终形态的哈夫曼树，则可以自底向上遍历每条分支从而得到对应于各字符的独特编码序列：

unordered_map<char, string> codes;
string str;

void encodeCodes(struct MinHeapNode* root, string str) {
    if (!root)
        return;

    if (root->data != '$')
        codes[root->data] = str;

    encodeCodes(root->left, str + "0");
    encodeCodes(root->right, str + "1");
}

这里采用递归的方式访问每一个叶节点并将沿途经过边标记为'0'(左子树方向)或'1'(右子树方向)，进而完成整个编码映射关系建立工作[^2]。

#### 应用场景——文件压缩
当拥有了一套有效的哈夫曼编码方案之后便可以直接应用于实际的信息缩减任务当中去。对于给定的一段文本内容而言，只需按照预先设定好的规则替换原文里所有的原始字节串即可达到减少冗余的目的；而在解压阶段则相反操作恢复初始状态下的比特流形式输出目标文档副本[^1]。