哈夫曼树 / 哈夫曼编码的完整实现
哈夫曼树（Huffman Tree）是一种最优二叉树，常用于数据压缩，比如文本文件的压缩。它是通过一种贪心算法构造的，可以使得所有叶子节点的带权路径长度（WPL，Weighted Path Length）最小化。
1. 什么是路径和路径长度？
在树结构中，路径指的是从一个节点到另一个节点之间的连接。路径长度是指经过的边的数量。
- 例如，从根节点到某个节点的路径长度是从根节点开始，经过多少条边才能到达该节点。
- 如果规定根节点的层数是1，那么从根节点到第L层节点的路径长度就是L-1。
2. 什么是结点的权和带权路径长度？
- 节点的权（Weight）通常是一个数值，表示该节点的某种重要性或频率。例如，在文本压缩中，每个字符的频率就可以作为其权。
-
带权路径长度（WPL）是指从根节点到某个叶子节点的路径长度乘以该节点的权。简单来说，WPL是权值和路径长度的乘积。
- 例如，某个节点的路径长度是3，权是20，那么该节点的带权路径长度就是 3×20=603×20=60。
3. 什么是树的带权路径长度？
一棵树的带权路径长度（WPL）是指所有叶子节点的带权路径长度之和。计算时，只考虑树中所有叶子节点的路径和权值的乘积。
例子：
假设有一棵树，其中叶子节点的带权路径长度如下：
- 节点100，路径长度1，WPL = 1 × 100 = 100
- 节点50，路径长度2，WPL = 2 × 50 = 100
- 节点20，路径长度3，WPL = 3 × 20 = 60
- 节点10，路径长度3，WPL = 3 × 10 = 30
这棵树的总WPL = 100 + 100 + 60 + 30 = 290。
4. 哈夫曼树的构造
哈夫曼树是通过一种贪心算法构建的，目的是使得树的带权路径长度最小。我们通过以下步骤来构建哈夫曼树：
构造步骤：
- 创建森林：每个权值（叶子节点）作为一个独立的树。
- 合并最小权值的两棵树：从森林中选择两棵权值最小的树，合并成一棵新树，新树的权值是这两棵树的权值之和。
- 更新森林：删除原来两棵树，将新树加入到森林中。
- 重复以上过程，直到森林中只剩下一个树，这棵树就是哈夫曼树。
例子：
假设有一组权值 {5, 6, 7, 8, 15}，我们来构建哈夫曼树：
- 第1步：创建森林，森林中包含5棵树，权值分别为5、6、7、8和15。
- 第2步：选择权值最小的两棵树，5和6，合并成一棵新树，新树的权值为5 + 6 = 11。然后将这两棵树从森林中删除，添加新树11。
- 第3步：选择权值最小的两棵树，7和8，合并成一棵新树，新树的权值为7 + 8 = 15。然后将这两棵树从森林中删除，添加新树15。
- 第4步：现在森林中剩下的树权值为{11, 15, 15}，选择11和15，合并成一棵新树，新树的权值为11 + 15 = 26。
- 第5步：选择15和26，合并成一棵新树，新树的权值为15 + 26 = 41。
现在森林中只剩下最后一棵树，权值为41，这就是哈夫曼树。
5. 总结
哈夫曼树的构造过程是基于贪心算法的：每次都选择权值最小的两棵树进行合并，直到最终形成一棵包含所有节点的树。通过这种方式构建的哈夫曼树，可以有效地最小化带权路径长度，从而在数据压缩中达到最优效果。
哈夫曼树不仅在压缩算法中广泛应用，它的思想也可以用在许多其他优化问题中。
代码实现（结尾有完整代码实现，这里讲解思路）：
- 使用的存储结构
c++
// 定义哈夫曼树的节点结构
struct htNode {
char data; // 当前节点存储的字符
int weight; // 当前节点的权重（字符出现的频率）
htNode* left; // 左子树指针
htNode* right; // 右子树指针
};
2. 定义三个文件
c++
string filename = "ceshi.txt"; // 读取的文件，需要自己创建并写入文本，与程序在同一文件夹下即可
string codename = "codeFile.txt"; // 编码后的文件（生成）
string outname = "deCodeFile.txt"; // 将编码文件解码
3. 读取文件并统计字频
```c++
// 定义字典
map
// 使用范围for循环遍历map
for (const auto& pair : freMap) {
cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
}
htNode* root = buildHt(freMap); // 构建哈夫曼树的函数 需修改为传入字典进行构建
printTree(root); // 前序遍历
map<char, string> cW;
inTree(root, cW); // 创建码表
for (const auto& pair : cW) {
cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
}
```
统计结果
4. 构建哈夫曼编码的函数（重点！）
```c++
// 用于构建哈夫曼树的函数
htNode buildHt(map
// 遍历频率表，将每个字符和它的频率放入哈夫曼树节点中
for (const auto &pair : Mp) {
newNode = new htNode();
newNode->data = pair.first; // 设置节点的数据（字符）
newNode->weight = pair.second; // 设置节点的权重（频率）
nodeList[i] = newNode; // 将节点加入到节点数组中
i++;
}
// 输出所有字符及其频率，调试用
for (int i = 0; i < maxmum; i++) {
cout << nodeList[i]->data << ": " << nodeList[i]->weight << endl;
}
// 合并节点，构建哈夫曼树
int n = maxmum - 1; // 要合并n-1次节点，最终得到一个树
htNode* rnode = NULL; // 右子树节点
htNode* lnode = NULL; // 左子树节点
int r = -1; // 右子树的索引
int l = -1; // 左子树的索引
// 开始合并过程，直到只剩一个节点为止
while (n > 0) {
int min1 = 100000; // 设置初始的最小权重值，初始化为一个很大的值
int min2 = 100000; // 设置第二小的最小权重值
// 寻找最小的第一个节点
for (int i = 0; i < maxmum; i++) {
if (nodeList[i] == NULL) continue;
if (nodeList[i]->weight <= min1) {
min1 = nodeList[i]->weight;
rnode = nodeList[i];
r = i; // 记录该节点的索引
}
}
nodeList[r] = NULL; // 从数组中移除该节点
// 寻找第二小的节点
for (int i = 0; i < maxmum; i++) {
if (nodeList[i] == NULL) continue;
if (nodeList[i]->weight <= min2) {
min2 = nodeList[i]->weight;
lnode = nodeList[i];
l = i; // 记录该节点的索引
}
}
nodeList[l] = NULL; // 从数组中移除该节点
// 创建新节点，将最小的两个节点合并
htNode* newNode = new htNode();
newNode->data = tidai; // 新节点的数据为空字符
newNode->weight = rnode->weight + lnode->weight; // 新节点的权重为两个子节点权重之和
newNode->left = lnode; // 设置左子节点
newNode->right = rnode; // 设置右子节点
nodeList[r] = newNode; // 将新节点加入节点列表
n--; // 合并次数减少
// 这里我将最小的两个节点拿出来，构建新的节点，其左右子树为这两个节点，新节点的值为两者之和，符合哈夫曼编码的思想。
}
// 最终返回合并后的哈夫曼树的根节点
htNode* root = NULL;
for (int i = 0; i < maxmum; i++) {
if (nodeList[i] != NULL) {
root = nodeList[i]; // 最后一个非空的节点即为根节点，存着一个完整的树
break;
}
}
return root; // 返回哈夫曼树的根节点
} ``` 5. 对文件编码并输出
```c++
void codeFile(string filename, string putname, map
if (!ofile.is_open()) {
cerr << "源文件打开错误: " << filename << endl;
return;
}
char och;
// 逐字读取源文件，使用哈夫曼编码表进行编码，并写入输出文件
while (ofile.get(och)) {
txtFile << mp[och]; // 使用哈夫曼编码表将字符编码并输出
}
ofile.close();
txtFile.close();
} ```
以上便是代码中重要的部分，接下来附上完整代码实现:
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<sstream>
#include<fstream>
#define tidai '\0' // 定义一个特殊字符tidai用于表示哈夫曼树中的空节点
using namespace std;
// 定义哈夫曼树的节点结构
struct htNode {
char data; // 当前节点存储的字符
int weight; // 当前节点的权重（字符出现的频率）
htNode* left; // 左子树指针
htNode* right; // 右子树指针
};
// 用于构建哈夫曼树的函数
htNode* buildHt(map<char, int> &Mp) {
// 获取频率表中字符的数量
int maxmum = Mp.size();
htNode *newNode = NULL;
htNode *nodeList[maxmum] = {NULL}; // 用于存储所有创建的节点
int i = 0;
// 遍历频率表，将每个字符和它的频率放入哈夫曼树节点中
for (const auto &pair : Mp) {
newNode = new htNode();
newNode->data = pair.first; // 设置节点的数据（字符）
newNode->weight = pair.second; // 设置节点的权重（频率）
nodeList[i] = newNode; // 将节点加入到节点数组中
i++;
}
// 输出所有字符及其频率，调试用
for (int i = 0; i < maxmum; i++) {
cout << nodeList[i]->data << ": " << nodeList[i]->weight << endl;
}
// 合并节点，构建哈夫曼树
int n = maxmum - 1; // 要合并n-1次节点，最终得到一个树
htNode* rnode = NULL; // 右子树节点
htNode* lnode = NULL; // 左子树节点
int r = -1; // 右子树的索引
int l = -1; // 左子树的索引
// 开始合并过程，直到只剩一个节点为止
while (n > 0) {
int min1 = 10000; // 设置初始的最小权重值
int min2 = 10000; // 设置第二小的最小权重值
// 寻找最小的两个节点
for (int i = 0; i < maxmum; i++) {
if (nodeList[i] == NULL) continue;
if (nodeList[i]->weight <= min1) {
min1 = nodeList[i]->weight;
rnode = nodeList[i];
r = i; // 记录该节点的索引
}
}
nodeList[r] = NULL; // 移除该节点
// 寻找第二小的节点
for (int i = 0; i < maxmum; i++) {
if (nodeList[i] == NULL) continue;
if (nodeList[i]->weight <= min2) {
min2 = nodeList[i]->weight;
lnode = nodeList[i];
l = i; // 记录该节点的索引
}
}
nodeList[l] = NULL; // 移除该节点
// 创建新节点，将最小的两个节点合并
htNode* newNode = new htNode();
newNode->data = tidai; // 新节点的数据为空字符
newNode->weight = rnode->weight + lnode->weight; // 新节点的权重为两个子节点权重之和
newNode->left = lnode; // 设置左子节点
newNode->right = rnode; // 设置右子节点
nodeList[r] = newNode; // 将新节点加入节点列表
n--; // 合并次数减少
}
// 最终返回合并后的哈夫曼树的根节点
htNode* root = NULL;
for (int i = 0; i < maxmum; i++) {
if (nodeList[i] != NULL) {
root = nodeList[i]; // 最后一个非空的节点即为根节点
break;
}
}
return root; // 返回哈夫曼树的根节点
}
// 打印哈夫曼树
void printTree(htNode* root, const string& prefix = "", bool isLeft = true) {
if (root == nullptr) {
return;
}
// 打印当前节点的信息，包括字符和权重
cout << prefix;
cout << (isLeft ? "├── " : "└── "); // 根据是否是左子树，选择不同的前缀
if (root->data == '\n') {
cout << "\\n"; // 如果字符是换行符，输出特殊标记
} else if (root->data == '\t') {
cout << "\\t"; // 如果字符是制表符，输出特殊标记
} else {
cout << root->data; // 打印字符
}
cout << ":" << root->weight << endl;
// 递归打印左子树和右子树
printTree(root->left, prefix + (isLeft ? "│ " : " "), true);
printTree(root->right, prefix + (isLeft ? "│ " : " "), false);
}
// 读取文件，统计每个字符的频率
bool readFile(string filename, map<char, int>& m) {
ifstream file(filename); // 打开文件
if (!file.is_open()) { // 判断文件是否成功打开
cerr << "无法打开文件: " << filename << " 请检查文件是否存在" << endl;
return false;
}
char ch;
// 逐字符读取文件并统计字符频率
while (file.get(ch)) {
m[ch]++; // 将字符出现的次数存入 map 中
}
file.close(); // 关闭文件
return true;
}
// 对文件进行编码并输出
void codeFile(string filename, string putname, map<char, string> &mp) {
ifstream ofile(filename); // 打开源文件
ofstream txtFile(putname, ios::out); // 打开输出文件
if (!txtFile) {
cerr << "无法打开文本文件!" << endl;
return;
}
if (!ofile.is_open()) {
cerr << "源文件打开错误: " << filename << endl;
return;
}
char och;
// 逐字读取源文件，使用哈夫曼编码表进行编码，并写入输出文件
while (ofile.get(och)) {
txtFile << mp[och]; // 使用哈夫曼编码表将字符编码并输出
}
ofile.close();
txtFile.close();
}
// 解码文件并输出
void decodeFile(string filename, string outname, map<char, string> &mp, htNode *root) {
ifstream ofile(filename); // 打开编码后的文件
ofstream txtFile(outname, ios::out); // 打开输出文件
if (!txtFile) {
cerr << "无法打开文本文件!" << endl;
}
if (!ofile.is_open()) {
cerr << "源文件打开错误: " << filename << endl;
}
char och;
htNode *node = root; // 从哈夫曼树的根节点开始解码
// 逐字读取文件，按照哈夫曼树解码字符
while (ofile.get(och)) {
if (node->data != tidai) {
txtFile.put(node->data); // 如果是叶子节点，输出字符
node = root; // 回到根节点
}
// 根据字符是 '0' 还是 '1'，决定遍历左子树或右子树
if (och == '0') {
node = node->left;
} else if (och == '1') {
node = node->right;
} else {
cout << "_______________Error: 发现非法字符: " << och << endl;
}
}
// 输出最后的字符
if (node->data != tidai) {
txtFile.put(node->data);
}
txtFile.close();
ofile.close();
}
// 遍历哈夫曼树生成编码表
void inTree(htNode *root, map<char, string> &cW, string str = ""){
if(root == NULL){
return;
}
if(root->data != tidai){
cW[root->data] = str;
}
// 递归生成码
inTree(root->left, cW, str+"0");
inTree(root->right, cW, str+"1");
}
void open(string filename, string codename, string outname){
// 定义字典
map<char, int> freMap;
if(!readFile(filename, freMap)){
return;
}
// 使用范围for循环遍历map
for (const auto& pair : freMap) {
cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
}
htNode* root = buildHt(freMap); // 构建哈夫曼树的函数 需修改为传入字典进行构建
printTree(root); // 前序遍历
map<char, string> cW;
inTree(root, cW); // 创建码表
for (const auto& pair : cW) {
cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
}
// 对文件编码并输出
codeFile(filename, codename, cW);
// 解码并输出
decodeFile(codename, outname, cW, root);
}
int main(){
string filename = "ceshi.txt";
string codename = "codeFile.txt";
string outname = "deCodeFile.txt";
open(filename, codename, outname);
system("pause");
return 0;
}
其中打印树的部分为ai生成，挺好看的。
结果展示：
测试时对字符量超过12000的大段文本代码运行结果出现错误，怀疑是栈溢出或树结构过大等原因，对8000字符以内的小文本有优良表现。