解析解析C++哈夫曼树编码和译码的实现哈夫曼树编码和译码的实现
一．背景介绍：一．背景介绍：
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼
树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
二．实现步骤：二．实现步骤：
1.构造一棵哈夫曼树
2.根据创建好的哈夫曼树创建一张哈夫曼编码表
3.输入一串哈夫曼序列，输出原始字符
三．设计思想：三．设计思想：
1.首先要构造一棵哈夫曼树，哈夫曼树的结点结构包括权值，双亲，左右孩子；假如由n个字符来构造一棵哈夫曼树，则共有
结点2n-1个；在构造前，先初始化，初始化操作是把双亲，左右孩子的下标值都赋为0；然后依次输入每个结点的权值
2.第二步是通过n-1次循环，每次先找输入的权值中最小的两个结点，把这两个结点的权值相加赋给一个新结点，，并且这个
新结点的左孩子是权值最小的结点，右孩子是权值第二小的结点；鉴于上述找到的结点都是双亲为0的结点，为了下次能正确
寻找到剩下结点中权值最小的两个结点，每次循环要把找的权值最小的两个结点的双亲赋值不为0（i）.就这样通过n-1循环
下、操作，创建了一棵哈夫曼树，其中，前n个结点是叶子（输入的字符结点）后n-1个是度为2的结点
3.编码的思想是逆序编码，从叶子结点出发，向上回溯，如果该结点是回溯到上一个结点的左孩子，则在记录编码的数组里
存“0”，否则存“1”，注意是倒着存；直到遇到根结点（结点双亲为0），每一次循环编码到根结点，把编码存在编码表中，然
后开始编码下一个字符（叶子）
4．译码的思想是循环读入一串哈夫曼序列，读到“0”从根结点的左孩子继续读，读到“1”从右孩子继续，如果读到一个结点的
左孩子和右孩子是否都为0，如果是说明已经读到了一个叶子（字符），翻译一个字符成功，把该叶子结点代表的字符存在一
个存储翻译字符的数组中，然后继续从根结点开始读，直到读完这串哈夫曼序列，遇到结束符便退出翻译循环
四．源代码：四．源代码：
/***************************************
目的：1.根据输入的字符代码集及其权值集，
构造赫夫曼树，输出各字符的赫夫曼编码
2.输入赫夫曼码序列，输出原始字符代码
作者：Dmego 时间：2016-11-11
****************************************/
#include<iostream>
#define MAX_MA 1000
#define MAX_ZF 100
using namespace std;
//哈夫曼树的储存表示
typedef struct
{
int weight; //结点的权值
int parent, lchild, rchild;//双亲，左孩子，右孩子的下标
}HTNode,*HuffmanTree; //动态分配数组来储存哈夫曼树的结点
//哈夫曼编码表的储存表示
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码
//返回两个双亲域为0且权值最小的点的下标
void Select(HuffmanTree HT, int n, int &s1, int &s2)
{
/*n代表HT数组的长度
*/
//前两个for循环找所有结点中权值最小的点（字符）
for (int i = 1; i <= n; i++)
{//利用for循环找出一个双亲为0的结点
if (HT[i].parent == 0)
{
s1 = i;//s1初始化为i
break;//找到一个后立即退出循环
}
}
资源评论
郭逗2023-07-26：作者以通俗易懂的方式，解释了哈夫曼树编码和译码的原理，让读者能够快速上手。
阿葱的葱白2023-07-26：这篇文件通过简洁明了的语言，给出了哈夫曼树编码和译码的实现思路，非常实用。
Period熹微2023-07-26：作者在解析C中的哈夫曼树编码和译码时深入浅出，让读者即使没有编程基础，也能轻松理解。
爱吃番茄great2023-07-26：这篇文件对哈夫曼树编码和译码进行了详细解析，让人一目了然。
老光私享2023-07-26：这篇文件结合了实例操作，使得读者对哈夫曼树编码和译码的实现有了更直观的认识，值得推荐阅读。
