哈夫曼树（构建、编码、译码）（详细分析+C++代码实现）

🕗 发布于 2025-01-22 08:17 数据结构 算法考研

D 哈夫曼树

题目要求

编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。
为确保构建的哈夫曼树唯一，本题做如下限定：

选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。

输入格式:

输入为3行。第1行为一个字符串，包含不超过5000个字符，至少包含两个不同的字符，每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串，表示待译码的哈夫曼编码。

输出格式:

输出第一行为用空格间隔的2个整数，分别为压缩前后文本大小，以字节为单位，一个字符占1字节，8个二进制位占1字节，若压缩后文本不足8位，则按1字节算。输出从第二行开始，每行为1个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出INVALID。

输入样例:

cbaxyyzz
0100
011

输出样例:

8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID

题目分析

要点1：原文本字符数据整理

根据输入的字符串，整理字符的种类数，以及各字符的个数，并将其按照出现次数从小到大进行排列，若次数相同，则先出现的仍在前。

//数据预处理
//计算输入的文本出现的所有不同的字符和对应数量
const int N = 5010;
int h[N], idx,w[N];  //w数组存储字符在文本中出现的个数，idx最终保存不同的字符种类数，h数组存储对应字符的下标
char da[N];  //da数组存储字符
int PreLengh;  //初始文本的长度
string line;  //初始文本
void input() {
cin >> line;
PreLengh = line.size();
for (char ch : line) {  //遍历文本中的每一个字符
if (w[h[ch]] == 0) {  //字符的权重为0，该字符第一次出现
da[++idx] = ch;
h[ch] = idx;
w[idx] = 1;
}
else {
w[h[ch]]++;  //否则，不是第一次出现，权重+1
}
}
//数据录入结束，进行排序
//冒泡排序，从小到大排列，权重相同的原来在前仍在前
for (int i = 1; i <= idx; i++) {
for (int j = 1; j <= idx - 1; j++) {
if (w[j] > w[j + 1]) {
swap(w[j], w[j + 1]);
swap(da[j], da[j + 1]);  //权重和数据都要交换
}
}
}
}

要点2：构建huffman树

1.在森林中取权值最小的两个根结点s和nl，合并成一棵二叉树，并生成一个新结点T作为这两个结点的父亲，T的权值是它的两个子结点的权值之和。

2.对新森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。

//创建哈夫曼树
HuffmanTree* createHuffmanTree(char data[],int weight[],int n) {
HuffmanTree* tree=new HuffmanTree;
tree->m = n;  //结点总数
tree->H = new HuffmanNode * [tree->m + 1];
HuffmanNode* p1, * p2, * p, * t;
//初始化结点
for (int i = 1; i <= tree->m; i++) {
tree->H[i] = new HuffmanNode;
tree->H[i]->INFO = data[i];
tree->H[i]->Weight = weight[i];
tree->H[i]->LLINK = NULL;
tree->H[i]->RLINK = NULL;
}
//组合结点
int i, j;
for (int i = 1; i < tree->m; i++) {  //遍历所有结点
t = new HuffmanNode;
p1 = tree->H[i];  //选取最小的两个结点作为左右子树
p2 = tree->H[i + 1];
t->LLINK = p1;
t->RLINK = p2;
t->Weight = p1->Weight + p2->Weight;
p = t;
j = i + 2;
//比较排列，仍要保证从小到大排列
while (j <= tree->m && (p->Weight) >= tree->H[j]->Weight) {
tree->H[j - 1] = tree->H[j];
j++;
}
//将新生成的树放入森林中
tree->H[j - 1] = p;
}
return tree;
}

要点3：Huffman编码

要输出所有字符的编码，遍历思想，走左子树则+0，走右子树则+1，直至走到叶结点，为字符，存储为对应字符的Huffman编码。

//Huffman编码
//char标志字符，与其对应的Huffman编码
typedef unordered_map<char, string> UMCS;
UMCS HuffmanCode;
void CreateHuffmanCode(HuffmanNode* root, string code) {
if (root == NULL) return;
if (!root->LLINK && !root->RLINK) {  //如果是叶结点，遍历到字符
HuffmanCode[root->INFO] = code; 
}
CreateHuffmanCode(root->LLINK, code + "0");  //左子树+0
CreateHuffmanCode(root->RLINK, code + "1");  //右子树+1
}

要点4：对二进制进行译码

读入一整串的二进制数，遇到0就走左子树，遇到1就走右子树，直至走到叶结点，为字符，一个字符到此译码成功，将该字符串到总答案中。若此时还有编码剩余，则重新从树根开始，继续译码，直至读入全部二进制编码。

若全部二进制读入完毕，但此时指针不位于叶结点，证明译码失败，没有正确结束。输出"INVALID"。

//对二进制进行译码
void TransHuffmanCode(HuffmanNode* root) {
HuffmanNode* t = root;
for (int num = 2; num > 0; num--) {
string op,ans="";
cin >> op;  //读入整串的二进制编码
for (int i = 0; i < op.size(); i++) {
char k = op[i];
if (k == '0') t = t->LLINK;  //如果是0，就走左指针
if (k == '1') t = t->RLINK;  //如果是1，就走右指针
if (!t->LLINK && !t->RLINK) {  //走到叶结点，译码成功，串入答案ans
ans = ans + t->INFO;
if (i != op.size() - 1) t = root;  //若还有编码未译完，重新返回树根，继续译码
}
}
if (!(!t->LLINK && !t->RLINK)) cout<<"INVALID";  //如果译码到最后，没有走到叶结点，证明译码失败
else cout << ans;
cout << endl;
t = root;
}
}

完整代码

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;

//Huffman结点
typedef struct HuffmanNode {
char INFO;  //信息域
int Weight;  //权值
HuffmanNode* LLINK;  //左链接
HuffmanNode* RLINK;  //右链接
}HuffmanNode;

//Huffman树的构建
typedef struct HuffmanTree {
HuffmanNode** H;  //存储哈夫曼树结点的数组H
int m;  //哈夫曼树结点总数
}HuffmanTree;

//数据预处理
//计算输入的文本出现的所有不同的字符和对应数量
const int N = 5010;
int h[N], idx,w[N];  //w数组存储字符在文本中出现的个数，idx最终保存不同的字符种类数，h数组存储对应字符的下标
char da[N];  //da数组存储字符
int PreLengh;  //初始文本的长度
string line;  //初始文本
void input() {
cin >> line;
PreLengh = line.size();
for (char ch : line) {  //遍历文本中的每一个字符
if (w[h[ch]] == 0) {  //字符的权重为0，该字符第一次出现
da[++idx] = ch;
h[ch] = idx;
w[idx] = 1;
}
else {
w[h[ch]]++;  //否则，不是第一次出现，权重+1
}
}
//数据录入结束，进行排序
//冒泡排序，从小到大排列，权重相同的原来在前仍在前
for (int i = 1; i <= idx; i++) {
for (int j = 1; j <= idx - 1; j++) {
if (w[j] > w[j + 1]) {
swap(w[j], w[j + 1]);
swap(da[j], da[j + 1]);  //权重和数据都要交换
}
}
}
}

//创建哈夫曼树
HuffmanTree* createHuffmanTree(char data[],int weight[],int n) {
HuffmanTree* tree=new HuffmanTree;
tree->m = n;  //结点总数
tree->H = new HuffmanNode * [tree->m + 1];
HuffmanNode* p1, * p2, * p, * t;
//初始化结点
for (int i = 1; i <= tree->m; i++) {
tree->H[i] = new HuffmanNode;
tree->H[i]->INFO = data[i];
tree->H[i]->Weight = weight[i];
tree->H[i]->LLINK = NULL;
tree->H[i]->RLINK = NULL;
}
//组合结点
int i, j;
for (int i = 1; i < tree->m; i++) {  //遍历所有结点
t = new HuffmanNode;
p1 = tree->H[i];  //选取最小的两个结点作为左右子树
p2 = tree->H[i + 1];
t->LLINK = p1;
t->RLINK = p2;
t->Weight = p1->Weight + p2->Weight;
p = t;
j = i + 2;
//比较排列，仍要保证从小到大排列
while (j <= tree->m && (p->Weight) >= tree->H[j]->Weight) {
tree->H[j - 1] = tree->H[j];
j++;
}
//将新生成的树放入森林中
tree->H[j - 1] = p;
}
return tree;
}

//Huffman编码
//char标志字符，与其对应的Huffman编码
typedef unordered_map<char, string> UMCS;
UMCS HuffmanCode;
void CreateHuffmanCode(HuffmanNode* root, string code) {
if (root == NULL) return;
if (!root->LLINK && !root->RLINK) {  //如果是叶结点，遍历到字符
HuffmanCode[root->INFO] = code; 
}
CreateHuffmanCode(root->LLINK, code + "0");  //左子树+0
CreateHuffmanCode(root->RLINK, code + "1");  //右子树+1
}

//计算压缩后文本的大小
int PostLength = 0;
void PostNum(UMCS HuffmanCode) {
for (char k : line) {  //从头到位按照原文本的逐一计算
PostLength += HuffmanCode[k].size();
}
PostLength = (PostLength + 7) / 8;  //以字节为单位计算，不足8位，按一字节算
}

//打印输出huffman编码
void printHuffmanCode() {
for (int i = 1; i <= idx; i++) {  //da数组内存储的即为数据字符
cout << da[i] << ":" << HuffmanCode[da[i]] << endl;
}
}

//对二进制进行译码
void TransHuffmanCode(HuffmanNode* root) {
HuffmanNode* t = root;
for (int num = 2; num > 0; num--) {
string op,ans="";
cin >> op;  //读入整串的二进制编码
for (int i = 0; i < op.size(); i++) {
char k = op[i];
if (k == '0') t = t->LLINK;  //如果是0，就走左指针
if (k == '1') t = t->RLINK;  //如果是1，就走右指针
if (!t->LLINK && !t->RLINK) {  //走到叶结点，译码成功，串入答案ans
ans = ans + t->INFO;
if (i != op.size() - 1) t = root;  //若还有编码未译完，重新返回树根，继续译码
}
}
if (!(!t->LLINK && !t->RLINK)) cout<<"INVALID";  //如果译码到最后，没有走到叶结点，证明译码失败
else cout << ans;
cout << endl;
t = root;
}
}
int main() {
//数据预处理
input();
//创建Huffman树
HuffmanTree* tree = createHuffmanTree(da, w, idx);
//构造Huffman编码
CreateHuffmanCode(tree->H[idx], "");
//计算编码后文本大小
PostNum(HuffmanCode);
//输出压缩前后文本大小
cout << PreLengh << ' ' << PostLength << endl;
//输出各字符的Huffman编码
printHuffmanCode();
//对输入的Huffman二进制编码进行译码
TransHuffmanCode(tree->H[idx]);
return 0;
}

提交结果

原文地址：https://blog.csdn.net/fcc13461862452/article/details/145284163

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Docker网段和服务器ip冲突导致无法访问网络的解决方法
下一篇：数据结构单链表

Spring Boot框架下的上海特产销售商城网站开发之旅
本项目基于Spring Boot框架开发，旨在创建一个网络上海特产销售商城网站。在黄菊华老师的指导下，该项目不仅涵盖了核心代码讲解和答辩指导，还提供了详尽的开发文档、开题报告、任务书及PPT等毕业设计
阅读更多2025-01-22
CKS认证 | Day1 K8s集群部署与安全配置
Kubernetes（K8s）是一个广泛使用的容器编排平台，用于自动化部署、扩展和管理容器化应用程序。随着 K8s 在生产环境中的普及，安全运维成为确保系统稳定性和数据安全的关键。
阅读更多2025-01-22
.netframeworke4.6.2升级.net8问题处理
【代码】.netframeworke4.6.2升级.net8问题处理。
阅读更多2025-01-22
【Java】Java抛异常到用户界面公共封装
这里我们可以看到interface里面，不再是单纯函数的定义，还有函数的实现。这样使接口的实现多了一份灵活性，但是如果接口里单纯的只定义函数，没有函数的实现的话，可能代码逻辑和结构更加清晰一些，这也是
阅读更多2025-01-22
Redis：解锁集群共享Session的秘密武器
在当今互联网技术蓬勃发展的时代，分布式系统和集群架构已成为构建大规模、高并发应用的关键技术手段。然而，在享受这些技术带来的强大性能和扩展性的同时，我们也面临着一系列挑战，其中 Session 共享问题
阅读更多2025-01-22
【设计模式-行为型】观察者模式
他是朱元璋的锦衣卫
阅读更多2025-01-22
设计模式概述 - 设计模式的重要性
设计模式是经过验证的、可重用的解决方案，用于解决在软件设计中反复出现的问题。它们不是具体的代码实现，而是一种设计思想或模板，可以在不同的上下文中应用。模式名称：一个简洁的名称，用于描述模式的核心思想。
阅读更多2025-01-22
Web安全攻防入门教程——hvv行动详解
Web安全攻防是一个动态变化的领域，攻防技术日新月异。在学习Web安全的过程中，掌握基础的安全理论和常见的攻击类型、漏洞防御技术是最基本的要求。通过不断的学习和实践，你能够提升自己的安全攻防能力，保护
阅读更多2025-01-22
vue一键换肤
（2）设置全局scss变量。
阅读更多2025-01-22
VUE之参数传递
【代码】VUE之参数传递。
阅读更多2025-01-22