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

 D 哈夫曼树

题目要求

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

1. 选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
2. 若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
3. 生成哈夫曼编码时，哈夫曼树左分支标记为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");  //左子树+0CreateHuffmanCode(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) {  //走到叶结点，译码成功，串入答案ansans = 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;  //存储哈夫曼树结点的数组Hint 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");  //左子树+0CreateHuffmanCode(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) {  //走到叶结点，译码成功，串入答案ansans = 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;
}

 提交结果