目录

哈夫曼编码（最优二叉树）

一、优势：缩短电文长度

二、思想：

三、过程： 

四、图解实现过程： 

五、总代码 

---

哈夫曼编码（最优二叉树）

一、优势：缩短电文长度

 二、思想：

        获取每个字符出现的频率，用一个大小为[256]的数组保存（因为ASCII码是256个），最后作为每个字符的权重。权重越大，意味着出现频率越大，希望它的码长越短，这样总体电文最小。最后把这些字符（不重复部分）、权重依次放入结点中，把这些结点作为一个个元素，从小到大依次组成哈夫曼树。

三、过程： 

先统计出字符出现的频率，作为其权重。
编码保存：把每个不重复的字符频率作为权重，用二叉树进行排序，二叉树上面的字符权重大(出现频率高)，编码的码长短，下面的字符权重小(出现频率低)，编码码长长。
编码：输入字符，遍历整个二叉树，对比是否和叶子结点相同，是则保存编码。（左0右1）
译码：输入二进制码，在二叉树中走一遍，走到叶子结点即为需要保存的编码。（左0右1）

（向左走为0，向右走为1）

四、图解实现过程： 

五、总代码 

//哈夫曼编码
//优势：缩短电文长度
//先统计出字符出现的频率，作为其权重。
//编码保存：把每个不重复的字符作为权重，用二叉树进行排序，二叉树上面的字符权重高(出现频率高)，编码的码长短，
//下面的字符权重小(出现频率低)，编码码长长
//编码：输入字符，遍历整个二叉树，对比是否和叶子结点相同，是则保存编码
//译码：输入二进制码，在二叉树中走一遍，走到叶子结点即为需要保存的编码。
#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
using namespace std;#define MAXSIZE 100char str[MAXSIZE];						//要编码保存的电文
char str_en[MAXSIZE];					//编码时输入的电文
char str_de[MAXSIZE];					//解码时输出的电文
int code_de[MAXSIZE];				//解码时存储
int frequency[256] = { 0 };			//统计各字符出现频率
int flag_c[256] = { 0 };					//只存储一次，判断是否第一次出现
int length = 0;								//数组总长度
int LENGTH = 0;							//叶子结点长度
int sumFrequency = 0;					//权重之和
int index_s = 0;							//字符串数组
int code[64];								//编码
int index_c = -1;							//编码数组
int step = 0;									//编码/译码步数（从哈夫曼树的根往后下走）
int sumCode[4 * MAXSIZE];			//总编码
int flag_exit = 0;							//退出符号
int index = 0;								//译码数组
int decode_length;						//译码数组长度//树元素
typedef struct Tnode
{char data;									//存放数据int frequency;							//权重(出现的频率）struct Tnode* lchild, * rchild;	//左右孩子int code[64];							//每个字符的哈夫曼码int code_length;						//编码长度
}Tnode;
Tnode T[MAXSIZE];						//存放各结点
Tnode* hfmTree;							//哈夫曼根结点
Tnode* Pre;									//存放前一个结点//输入字符串
void Input()
{cout << "请输入需要编码并保存编码的电文：\n";gets_s(str, 100);
}//输入待编码数组
void Encode_Input()
{cout << "请输入需要编码的电文：\n";getchar();gets_s(str_en, MAXSIZE);
}//输出编码后的数组
void Encode_Output()
{int i = 0;//下标for (i = 0; i <= index_c; i++){cout << sumCode[i];}cout << endl;
}//输入待译码数组
void Decode_Input()
{int i = 0;char ch = ' ';step = 0;cout << "请输入需要译码的二进制码：\n";index = 0;getchar();									//吸收空格//读取每位字符，挨个化整存入整形数组while (ch != '\n')						//把每位字符保存到数组（换行退出）{ch = getchar();						//读取一位字符if (ch != '\n')code_de[i++] = ch - 48;	//字符化整}decode_length = i;					//译码数组长度
}//获取权重
void GetFrequency()
{int i = 0;//统计字符频率for (i = 0; i < strlen(str); i++){frequency[str[i]]++;					//频率表中对应字符出现数值+1}
}//创建树节点
void CreateTnode()
{int i = 0, count = 0;//添加字符和频率到树结构体数组中for (i = 0; i < strlen(str); i++){if (flag_c[str[i]] == 0)				//首次出现{flag_c[str[i]] = 1;					//标志出现过T[count].data = str[i];T[count].frequency = frequency[str[i]];T[count].lchild = NULL;T[count].rchild = NULL;sumFrequency += T[count].frequency;		//计算叶子结点总权重count++;}}LENGTH = count;length = count;
}//获取最小值						/***********注：要整体替换，否则后面会出现混乱**********/
Tnode Getmin()
{int i, j, max = 0;Tnode temp;//选择排序(权重从高到低)（最后的一个最小）for (i = 0; i < length; i++){max = i;for (j = i; j < length; j++){if (T[j].frequency > T[max].frequency)max = j;}if (max != i){temp = T[i];								//整体替换T[i] = T[max];T[max] = temp;}}return T[--length];			//取出最后一个结点（最小权重）
}//遍历
void Traverse(Tnode* N)
{int i = 0;if (N != NULL){Traverse(N->lchild);if (N->lchild == NULL && N->rchild == NULL)					//叶子结点{printf("%c结点权值：%d\t编码：", N->data, N->frequency);for (i = 0; i < N->code_length; i++){cout << N->code[i];}cout << endl;}Traverse(N->rchild);}
}//初始化哈夫曼树
void Init_hfmTree()
{hfmTree = (Tnode*)malloc(sizeof(Tnode));			//创建哈夫曼树hfmTree->lchild = NULL;hfmTree->rchild = NULL;Pre = hfmTree;														//前一个结点
}//创建哈夫曼树
Tnode Create_hfmTree()
{int len;Tnode* N = (Tnode*)malloc(sizeof(Tnode));while (N->frequency != sumFrequency){N = (Tnode*)malloc(sizeof(Tnode));N->lchild = (Tnode*)malloc(sizeof(Tnode));			//左孩子N->rchild = (Tnode*)malloc(sizeof(Tnode));			//右孩子if (length != -1)*N->lchild = Getmin();elseN->lchild = NULL;												//地址设为空if (length != -1)*N->rchild = Getmin();elseN->rchild = NULL;												//地址设为空N->data = '#';															//表示空N->frequency = N->lchild->frequency + N->rchild->frequency;		//求权重之和T[length++] = *N;													//放入数组}return *N;
}//结点编码（初始存档编码）
void NodeEncode(Tnode* N)
{int i = 0;if (N != NULL){//向左走if (Pre->lchild == N){code[step++] = 0;				//向左走}else if (Pre->rchild == N){code[step++] = 1;				//向右走}Pre = N;									//保存上一结点if (N->lchild != NULL && N->rchild != NULL)		//未到达叶子结点{NodeEncode(N->lchild);step--;										//向回走Pre = N;									//保存上一结点NodeEncode(N->rchild);step--;										//向回走}else												//到达叶子结点{for (i = 0; i < step; i++)N->code[i] = code[i];			//记录编码N->code_length = step;			//记录码长}}
}//编码
void Encode(Tnode* N)
{int i = 0;if (flag_exit)return;if (N != NULL && str[index_s] != '\0')				//到达叶子结点或者字符串到尾{if (N->lchild != NULL && N->rchild != NULL)		//未到达叶子结点{Encode(N->lchild);Encode(N->rchild);}else														//找到叶子结点{if (N->data == str_en[index_s])		//是要找的叶子结点{flag_exit = 1;							//退出标志for (i = 0; i < N->code_length; i++){sumCode[++index_c] = N->code[i];			//编码存入}}}}
}//译码
void Decode(Tnode* N)
{int i = 0;if (N != NULL){if (N->lchild != NULL || N->rchild != NULL)					//没有查找到叶子结点{if (code_de[index] == 0)			//向左走{index++;step++;Decode(N->lchild);step--;							//弹出来}else if (code_de[index] == 1)	//向右走{index++;step++;Decode(N->rchild);step--;							//弹出来}}else					//查找到叶子结点{cout << N->data;			//输出译码结果}}
}int main()
{int choice;int i;Input();						//输入字符GetFrequency();		//获取字符串//叶子结点的创建与排序CreateTnode();			//创建树节点//哈夫曼树的初始化与创建Init_hfmTree();*hfmTree = Create_hfmTree();//结点编码step = 0;NodeEncode(hfmTree);while (1){system("cls");cout << "请选择需要的服务：\n";cout << "1、查找所有已保存的结点编码和权\n";cout << "2、整体编码\n";cout << "3、整体译码\n";cout << "0、退出\n";cout << "请选择您需要的服务：\n";cin >> choice;//选项switch (choice){//0、退出case 0:exit(0);break;//1、遍历所有叶子结点case 1:Traverse(hfmTree);				//查找所有编码和权break;case 2:index_s = 0;Encode_Input();					//编码输入//逐字符编码while (str_en[index_s] != '\0'){flag_exit = 0;Encode(hfmTree);index_s++;}Encode_Output();					//编码输出break;//3、译码case 3://输入译码数组Decode_Input();index = 0;while (index < decode_length){//译码step = 0;Decode(hfmTree);			//译码并输出}cout << endl;break;default:cout << "无此选项！" << endl;break;}system("pause");}return 0;
}

总结

以上是生活随笔为你收集整理的数据结构与算法（6-5）二叉树的应用--哈夫曼树与哈夫曼编码的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。