哈夫曼树及应用(实验7--作业)
哈夫曼树是一种非常重要的数据结构，在数据压缩等诸多领域有着广泛的应用。本文将详细讲解一段实现哈夫曼树构建、编码以及译码功能的C++代码，帮助大家深入理解哈夫曼树的原理和实现细节。
一、代码整体结构概述
这段C++代码主要实现了以下几个功能模块：
- 定义哈夫曼树节点结构体和相关类型别名：通过
typedef定义了HTNode结构体来表示哈夫曼树的节点，包含了权值、双亲、左孩子和右孩子的下标信息。同时定义了HuffmanTree作为指向HTNode结构体的指针类型，以及HuffmanCode作为二维字符指针类型用于存储哈夫曼编码。 - 查找最小值函数（SelectMin）：用于在给定的哈夫曼树节点数组中，找到权值最小和次小且父节点为
0的两个节点。这是构建哈夫曼树过程中选择节点合并的关键步骤。 - 构建哈夫曼树函数（CreateHuffmanTree）：根据输入的叶子节点个数，初始化哈夫曼树节点数组，并通过不断选择权值最小和次小的节点进行合并，逐步构建出完整的哈夫曼树。
- 保存哈夫曼编码函数（CreateHuffmanCode）：在已经构建好的哈夫曼树基础上，从叶子节点到根节点逆向遍历，为每个叶子节点生成对应的哈夫曼编码，并存储在
HuffmanCode类型的二维数组中。 - 打印哈夫曼树数组函数（printHaffmamTree）：将哈夫曼树节点数组的信息，包括节点索引、权值、父节点、左孩子和右孩子下标等，以清晰的格式打印输出，方便查看哈夫曼树的结构。
- 打印哈夫曼编码数组函数（printHaffmanCode）：把每个叶子节点对应的哈夫曼编码以及其索引和对应的字符（这里假设按照索引 + 96转换为字符）以表格形式打印出来，展示哈夫曼编码的结果。
- 翻译哈夫曼树函数（HuffmanCodeTranslate）：实现对输入的二进制码进行译码操作，根据已经构建好的哈夫曼树和编码规则，将二进制码还原为对应的字符序列。
二、关键代码模块详解
（一）哈夫曼树节点结构体及类型别名定义
typedef struct {
int weight; //权值
int parent, lchild, rchild; //双亲、左右孩子下标
} HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树
//指针数组，存放每个编码首元素地址
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
在这里，我们定义了HTNode结构体来描述哈夫曼树的节点特征。每个节点包含了自身的权值（weight），以及指向其双亲（parent）、左孩子（lchild）和右孩子（rchild）的下标信息。通过HuffmanTree和HuffmanCode这两个类型别名，使得后续代码在处理哈夫曼树和哈夫曼编码时更加方便和清晰。
（二）查找最小值函数（SelectMin）
//查找最小值
void SelectMin(HuffmanTree& HT, int k, int& s1, int& s2) {
//初始化为极大的数来查找最小的两个数
int min1 = MaxValue;
int min2 = MaxValue;
//前k个节点中找
for(int i = 1; i <= k; i++) {
if (HT[i].weight < min1 && HT[i].parent == 0) {
min1 = HT[i].weight;
s1 = i;
}
}
for(int j = 1; j <= k; j++) {
if (HT[j].weight < min2 && HT[j].parent == 0 && j!= s1) {
min2 = HT[j].weight;
s2 = j;
}
}
}
这个函数的目的是在哈夫曼树节点数组HT的前k个节点中，找到权值最小和次小且父节点为0的两个节点。首先，我们将min1和min2初始化为一个极大值（这里通过MaxValue定义）。然后，通过两个嵌套的for循环来实现查找。第一个循环找到权值最小且父节点为0的节点，记录其权值到min1，下标到s1。第二个循环在排除已经找到的s1节点的情况下，找到权值次小且父节点为0的节点，记录其权值到min2，下标到s2。需要注意的是，这里的实现方式虽然能够完成功能，但存在一定的局限性，后续在构建哈夫曼树过程中可能会出现一些逻辑上的小瑕疵（后面会详细讲解）。
（三）构建哈夫曼树函数（CreateHuffmanTree）
//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree& HT, int n) {
if (n <= 1) return; //叶子节点数量为1，直接退出函数
int m = 2 * n - 1; //HT空间数
HT = new HTNode[m + 1]; //申请2n空间（0号不用），每个节点都是一个只有根节点的树
//先初始化
//所有节点的孩子节点、父母节点都为0
for(int i = 1; i <= m; i++) {
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
}
//再输入每个节点的权值
//前n个存放叶子节点的权值
for(int i = 1; i <= n; i++) {
cout << "请输入第" + i << "个节点的权值：";
cin >> HT[i].weight;
}
//然后根据哈夫曼树的规则进行一系列操作构建哈夫曼树
//前n个为未被操作的节点，从n + 1个开始构建
for(int i = n + 1; i <= m; i++) {
int s1, s2;
//在HT中的前i - 1个节点中选两个最小且父母节点为0的点
//因为选出来后会当作HT第i个节点的左右孩子，且插入左右孩子后
//得到的新节点的parent为0，所以每次从前i - 1个节点中找
SelectMin(HT, i - 1, s1, s2);
//选出来最小节点下标s1，次小节点下标s2后
HT[s1].parent = i;
HT[s2].parent = i; //都接在第i个节点下，相当于删除操作
HT[i].lchild = s1;
HT[i].rchild = s2; //选择操作
//HT[i]为HT[s1],HT[s2]合并后的节点，weight要合并
HT[i].weight = HT[s1].weight + HT[s2].weight; //合并操作
}
}
在这个函数中，我们首先判断输入的叶子节点个数n，如果小于等于1，则直接返回，因为哈夫曼树至少需要两个叶子节点才能构建。然后，我们根据公式m = 2 * n - 1计算出哈夫曼树总共需要的节点数m，并动态分配了相应的内存空间来存储哈夫曼树节点数组HT。接着，对所有节点的孩子节点、父母节点进行初始化设置为0。之后，通过循环输入每个叶子节点的权值。最后，在构建哈夫曼树的核心循环中，每次调用SelectMin函数在前i - 1个节点中选择两个最小且父节点为0的节点，将它们作为新节点i的左右孩子，并更新相关节点的父节点、孩子节点以及新节点的权值等信息，逐步构建出完整的哈夫曼树。
（四）保存哈夫曼编码函数（CreateHuffmanCode）
//保存哈夫曼编码
void CreateHuffmanCode(HuffmanTree& HT, int n, HuffmanCode& HC) {
// 先为HC分配内存，假设每个编码最长不超过n位
HC = new char *[n + 1];
for (int i = 1; i <= n; i++) {
HC[i] = new char[n + 1]; // 多分配一位用于存储字符串结束符'\0'
}
//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
stack<char> S; //临时栈 用来存放每个根节点的逆向路径后正向输出
for(int i = 1; i <= n; i++) { // n个叶子节点对应的哈夫曼编码
int c = i; // 当前节点
and p = HT[i].parent; //向上查找当前节点的父母节点
while(p!= 0) { //当前节点的父母节点还不是根节点时
if (HT[p].lchild == c) S.push('0'); //左0
else if (HT[p].rchild == c) S.push('1'); //右1
c = p;
p = HT[c].parent; //向上倒推
} //此时S中存放的为第i个节点的逆向路径
//正向存储在HC[i][…]中
int j = 0;
while(!S.empty()) {
HC[i][j++] = S.top();
S.pop();
}
HC[i][j] = '\0';
}
}
此函数用于为已经构建好的哈夫曼树生成哈夫曼编码。首先，为HuffmanCode类型的二维数组HC分配内存空间，假设每个编码最长不超过n位（这里n是叶子节点个数），并多分配一位用于存储字符串结束符'\0'。然后，通过从叶子节点到根节点逆向遍历哈夫曼树，利用一个临时栈S来记录从叶子节点到根节点的路径（通过判断是左孩子还是右孩子来压入0或1）。最后，将栈中的元素依次弹出并存储到HC[i]数组中，形成每个叶子节点对应的哈夫曼编码，并在末尾添加'\0'表示字符串结束。
（五）打印哈夫曼树数组函数（printHaffmamTree）
//打印HT数组
void printHaffmamTree(HuffmanTree& HT, int n) {
cout << "哈夫曼树如下所示\n";
cout << "index\tweight\tparent\tlchild\trchild\n";
for(int i = 1; i <= 2 * n - 1; i++) {
cout << i << "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << HT[i].rchild << "\t" << endl;
}
}
这个函数的功能很简单，就是将哈夫曼树节点数组HT的相关信息以清晰的表格形式打印出来。包括节点的索引、权值、父节点、左孩子和右孩子下标等信息，方便我们直观地查看哈夫曼树的结构。
（六）打印哈夫曼编码数组函数（printHaffmanCode）
//打印HC数组
void printHaffmanCode(HuffmanCode& HC, int n) {
cout << "哈夫曼编码如下所示\n";
cout << "index\tchar\tcode" << endl;
for(int i = 1; i <= n; i++) {
cout << i << "\t" << (char)(i + 96) << "\t";
int j = 0;
while(HC[i][j]!= '\0') {
cout << HC[i][j];
j++;
}
cout << endl;
}
}
该函数用于打印每个叶子节点对应的哈夫曼编码。首先输出表头信息，然后通过循环遍历每个叶子节点，输出节点的索引、根据索引转换得到的字符（这里通过(char)(i + 96)进行简单转换，假设是按照某种字符编码规则）以及对应的哈夫曼编码内容，方便我们查看每个叶子节点的编码情况。
（七）翻译哈夫曼树函数（HuffmanCodeTranslate）
// 翻译哈夫曼树
void HuffmanCodeTranslate(HuffmanTree& HT, int n) {
cout << "请输入一个二进制码 " << endl;
string Code;
cin >> Code;
int currentNode = 2 * n - 1; // 从根节点开始，根节点索引假设为2 * n - 1
for (char bit : Code) {
if (bit == '0') {
currentNode = HT[currentNode].lchild;
} else if (bit == '1') {
currentNode = HT[currentNode].rchild;
}
if (HT[currentNode].lchild == 0 && HT[currentNode].rchild == 0) {
// 到达叶子节点，输出对应的字符编码
cout << (char)(current太极 + 96);
currentNode = 2 * n - 1; // 回到根节点，继续处理下一段编码
}
}
}
这个函数实现了对输入的二进制码进行译码的功能。首先获取用户输入的二进制码字符串Code，然后从哈夫曼树的根节点（假设索引为2 * n - 1）开始，根据二进制码的每一位，判断是走向左子树还是右子树。当走到叶子节点（即节点的左右子树都为0）时，输出对应的字符编码，并回到根节点继续处理下一段二进制码，从而将输入的二进制码还原为对应的字符序列。
三、代码存在的一些问题及改进思路
（一）查找最小值函数（SelectMin）的改进
在SelectMin函数中，通过两个嵌套的for循环来查找权值最小和次小且父节点为0的两个节点的方式存在一定的局限性。在后续构建哈夫曼树过程中，可能会出现逻辑上的小瑕疵。例如，在第二次调用SelectMin函数时，可能会因为第一次调用后对节点的父节点进行了设置，导致第二次循环找次小节点时错误地排除了一些原本应该作为候选的节点。
改进思路：可以将两个循环合并为一个循环，在一个循环内同时找到权值最小和次小且父节点为0的两个节点。这样可以避免因为多次调用导致的节点状态变化而引起的错误。
（二）内存管理方面的考虑
在代码中，虽然对哈夫曼树节点数组HT和哈夫曼编码二维数组HC都进行了内存分配，但在程序结束时，没有对这些动态分配的内存进行释放。这可能会导致内存泄漏问题，特别是在长时间运行或频繁调用相关函数的程序中。
改进思路：在程序结束或不再需要使用这些动态分配的内存时，应该及时释放它们。例如，在main函数结束之前，可以添加相应的代码来释放HT和HC所占用的内存。
四、总结
通过对这段C++代码的详细讲解，我们深入了解了哈夫曼树的构建、编码以及译码的实现过程。哈夫曼树作为一种重要的数据结构，在数据压缩、编码理论等领域有着重要的应用。同时，我们也分析了代码中存在的一些问题及改进思路，希望大家在学习和使用哈夫曼树相关知识时，能够更加深入地理解其原理和实现细节，并且能够写出更加完善、高效的代码。
五、代码汇总
#include<bits/stdc++.h>//万能头文件
using namespace std;//命名空间
const int MaxValue = 1e9;
typedef struct {
int weight; //权值
int parent, lchild, rchild;//双亲 左右孩子下标
}HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树
//指针数组 存放每个编码首元素地址
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
//查找最小值
void SelectMin(HuffmanTree&HT,int k,int &s1,int &s2){
//初始化为极大的数来查找最小的两个数
int min1 = MaxValue;
int min2 = MaxValue;
//前k个节点中找
for(int i =1;i<=k;i++){
if(HT[i].weight<min1&&HT[i].parent==0){//最小值且父母为0
min1 = HT[i].weight;
s1 = i;//更新下s1
}
}
for(int j =1;j<=k;j++){
if(HT[j].weight<min2&&HT[j].parent==0&&j!=s1){//次大的 所以j!=s1
min2 = HT[j].weight;
s2 = j;
}
}
}
//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT,int n){
if(n<=1) return ;//叶子节点数量为1 直接退出函数
int m = 2*n - 1;//HT空间数
HT = new HTNode[m+1];//申请2n空间（0号不用） 每个节点都是一个只有跟节点的树
//先初始化
//所有节点的孩子节点 父母节点都为0
for(int i = 1;i<=m;i++){
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
}
//再输入每个节点的权值
//前n个存放叶子节点的权值
for(int i = 1;i<=n;i++){
cout<<"请输入第"<<i<<"个节点的权值：";
cin>>HT[i].weight;
}
//然后根据哈夫曼树的规则进行一系列操作构建哈夫曼树
//前n个为未被操作的节点 从n+1个开始构建
for(int i = n+1;i<=m;i++){
int s1,s2;
//在HT中的前i-1个节点中选两个最小且父母节点为0的点
//因为选出来后会当作HT第i个节点的左右孩子 且插入左右孩子后
//得到的新节点的parent为0 所以每次从前i-1个节点中找
SelectMin(HT,i-1,s1,s2);
//选出来最小节点下标s1 次小节点下标s2后
HT[s1].parent = i;HT[s2].parent = i;//都接在第i个节点下 相当于删除操作
HT[i].lchild = s1;HT[i].rchild = s2;//选择操作
//HT[i]为HT[s1],HT[s2]合并后的节点 weight要合并
HT[i].weight = HT[s1].weight + HT[s2].weight;//合并操作
}
}
//保存哈夫曼编码
void CreateHuffmanCode(HuffmanTree&HT,int n,HuffmanCode&HC){
// 先为HC分配内存，假设每个编码最长不超过n位
HC = new char *[n + 1];
for (int i = 1; i <= n; i++) {
HC[i] = new char[n + 1]; // 多分配一位用于存储字符串结束符'\0'
}
//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
stack<char>S;//临时栈 用来存放每个跟节点的逆向路径后正向输出
for(int i = 1;i<=n;i++){//n个叶子节点对应的哈夫曼编码
int c = i;//当前节点
int p = HT[i].parent;//向上查找当前节点的父母节点
while(p!=0){//当前节点的父母节点还不是根节点时
if(HT[p].lchild == c) S.push('0');//左0
else if(HT[p].rchild == c) S.push('1');//右1
c = p;p = HT[c].parent;//向上倒推
}//此时S中存放的为第i个节点的逆向路径
//正向存储在HC[i][…]中
int j =0;
while(!S.empty()){
HC[i][j++] = S.top();
S.pop();
}
HC[i][j] = '\0';
}
}
//打印HT数组
void printHaffmamTree(HuffmanTree&HT,int n){
cout<<"哈夫曼树如下所示\n";
cout<<"index\tweight\tparent\tlchild\trchild\n";
for(int i = 1;i<=2*n-1;i++){
cout<<i<<"\t"<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<"\t"<<endl;
}
}
//打印HC数组
void printHaffmanCode(HuffmanCode&HC,int n){
cout<<"哈夫曼编码如下所示\n";
cout<<"index\tchar\tcode"<<endl;
for(int i = 1;i<=n;i++){
cout<<i<<"\t"<<(char)(i+96)<<"\t";
int j = 0;
while(HC[i][j]!='\0'){
cout<<HC[i][j];
j++;
}
cout<<endl;
}
}
// 翻译哈夫曼树
void HuffmanCodeTranslate(HuffmanTree& HT, int n) {
cout << "请输入一个二进制码 " << endl;
string Code;
cin >> Code;
int currentNode = 2 * n - 1; // 从根节点开始，根节点索引假设为2*n - 1
for (char bit : Code) {
if (bit == '0') {
currentNode = HT[currentNode].lchild;
} else if (bit == '1') {
currentNode = HT[currentNode].rchild;
}
if (HT[currentNode].lchild == 0 && HT[currentNode].rchild == 0) {
// 到达叶子节点，输出对应的字符编码
cout << (char)(currentNode + 96);
currentNode = 2 * n - 1; // 回到根节点，继续处理下一段编码
}
}
}
int main(){
int n;//叶子节点个数
cout<<"请输入您所要构建的哈夫曼树的叶子节点的个数：";
cin>>n;
HuffmanTree HT;
HuffmanCode HC;
//构建哈夫曼树
CreateHuffmanTree(HT,n);
//打印HT数组
printHaffmamTree(HT,n);
//构建哈夫曼编码
CreateHuffmanCode(HT,n,HC);
//打印HC数组
printHaffmanCode(HC,n);
//译码
HuffmanCodeTranslate(HT,n);
return 0;
}
运行结果如下所示
输入
8
5
29
7
8
14
23
3
11
代表有8个叶子节点 分别是 5，29，7，5，14，23，3，11
原文地址：https://blog.csdn.net/ByteMaster_/article/details/143696078
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！