在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)
 
 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如
 
 JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，
 
 是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点
 
 的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度
 
 为叶结点的层数）。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)
 
 ，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径
 
 长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
 
 哈夫曼编码步骤：
 
 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）
 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
 四、重复二和三两步，直到集合F中只有一棵二叉树为止。
 
 简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：
 
 
 
 虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图：
 
 
 
 再依次建立哈夫曼树，如下图：
 
 
 
 其中各个权值替换对应的字符即为下图：
 
 
 
 所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010
 
 霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。

哈夫曼树（最优二叉树）
 
百度百科：https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin
 
一. 目的：
 
找出存放一串字符所需的最少的二进制编码
 
二. 构造方法：
 
首先统计出每种字符出现的频率！（也可以是概率）//权值
 
------------------------------------------------------------------------------------------------
 
           例如：频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3
 
第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在频率表中删除此次找到的两个数，并加入此次最小两个数的频率和。
 
F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和 8给频率表
 
 
 重复第一步：
 
-------------------------------------------------------------------------------------------------
 
频率表 A：60,    B:45,   C:13   D:69   E:14   FG:8
 
最小的是 FG：8与C：13，因此如图，并返回FGC的和：21给频率表。
 
 
---------------------------------------------------------------------------------------------------
 
重复第一步：
 
---------------------------------------------------------------------------------------------------
 
频率表 A：60    B: 45   D: 69   E: 14   FGC: 21
 
如图
 
 
-----------------------------------------------------------------------------------------------------
 
重复第一步
 
-----------------------------------------------------------------------------------------------------
 
频率表 A：60    B: 45   D: 69  FGCE: 35
 
 
-----------------------------------------------------------------------------------------------------
 
重复第一步
 
-----------------------------------------------------------------------------------------------------
 
频率表 A：60   D: 69  FGCEB: 80
 
 
-----------------------------------------------------------------------------------------------------
 
重复第一步
 
-----------------------------------------------------------------------------------------------------
 
频率表 AD：129  FGCEB: 80
 
 
添加 0 和 1，规则左0 右1
 
 
 
 
频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3
 
每个 字符 的 二进制编码 为（从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码）
 
字符
编码
A
10
B
01
C
0011
D
11
E
000
F
00101
G
00100
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
那么当我想传送 ABC时，编码为 10 01 0011
 
思考：
 
大家观察 出现得越多的字母，他的编码越短 ，出现频率越少的字母，他的编码越长。
 
在信息传输过程中，如果这个字母越多，那么我们希望他越瘦小（编码短）这样占用的编码越少，其实编码长的字母也是让频率比它多的字母把编码短的位子都占用后，他才去占用当前最短的编码。至此让总的编码长度最短。
 
且要保证长编码的不与短编码的字母冲突：
 
比如 不能出现 读码 读到 01  还有长编码的 字母为011，如果短编码为一个长编码的左起子串，这就是冲突，意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母，
 
但哈夫曼树（最优二叉树）在构造的时候就避免了这个问题。为什么能避免呢，因为哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况。
 
 
 
提问：
 
1.为什么要保证长编码不与短编码冲突？
 
冲突情况：如果我们已经确定D，E，F，G 用 01 ，010 ，10，001的2进制编码来传输了。那么想传送FED时，我需要传送     1001001，接收方可以把它解析为FDG（10 01 001），当然也能解析为FED（10 010 01），他两编码一样的，这就是编码冲突，（这里编码冲突的原因，也是因为编码时，D的编码是E的编码的左起子串了）显然这是不行的，就像我说压脉带，你如果是日本人会理解为 （你懂得），这就是发出同一种语，得出不同的意的情况。所以不能让一个字母的二进制代表数，为另一个字母的二进制代表数的子串。但为什么实际情况只要求编码时，一个编码不是另一编码的左起子串呢而不是绝对意义上的非子串呢，因为计算机从数字串的左边开始读，如果从右边读，那么可以要求是非右起（无奈）。你又可以问了为什么编码要求是非左起或非右起不直接规定不能是子串呢（也行，不过=>），比如说原文中B就是C，F，G的子串，那这不就不符合规则了么。这里是为了哈夫曼的根本目的，优化编码位占用问题，如果完全不能有任何子串那么编码将会非常庞大。但这里计算机是一位一位的·读取编码的，只需要保证计算机在读取中不会误判就行。并且编码占用最少。
 
code：0110101001110
 
左起子串：011
 
右起子串：110
 
绝对非子串：1110111  此串在code中完全找不到
 
2.那么哈夫曼树怎么避免左起子串问题呢？
 
因为哈夫曼是从叶子节点开始构造，构造到根节点的，而且构造时，都是计算两个权值的节点的和再与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。在有权值的节点又不会出现在任何一条路的路途中的情况，只会出现在终点的情况下，因此不会出现01代表一个字母011又代表一个字母。
 
又如原文ABC编码为10010011的情况，当计算机读到10时，由于有左起子串不冲突的原则。那么计算机完全可以保证当前的10就是A字母，然后再往下读010011的部分，然后当读到01时，也完全能确定B，C同理，而不用说因为会出现冲突的编码而接着继续读取之后的编码来确定前面的编码。这样对信息的判断和效率是相当的不利的，也不是说不可以。即使你ABCD,分别用01,011,0111,01111来代替也行，传输后也能精确识别，但是数据量极大呢，想代替整个中文编码呢，那0后面得多少个1才能代表完。因此哈夫曼就是为了获得最少编码量代替最多字符串，并且不冲突，系统不会误判而产生的。
 
3.这里要提一下同权不同构
 
已经有朋友问起这个问题了。这里要说一下哈夫曼树的构造并不是唯一的。
 
考虑如下情况：
 
有权值分别为 5,29,7,8,14,23,3,11的情况，可以如下图一样构造。
 
 
带权路径长度：
 
(5+3+7+8)*4+
 
(11+14)*3+
 
(23+29)*2
 
=271
 
也可以如下图构造：
 
 
带权路径长度：
 
（3+5)*5+
 
7*4+
 
(8+11+14)*3+
 
(23+29)*2
 
=271
 
这两种不同的方式构造出来的哈夫曼树，得出的带权路径长度相等，那么选哪颗树都可以，这就叫同权不同构。
 
 
 
此问题由博主 https://me.csdn.net/weixin_43690959 昵称：叫我Tim就好了～ 提出，在这里对他表示感谢。
 
 
 
 
 
 
 
看懂的朋友留个赞，没看懂的留言我给你单独讲 _(:з」∠)_

参考书籍：数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社
 
本文中的代码可从这里下载：https://github.com/qingyujean/data-structure
 
1.哈夫曼树
 
    假设有n个权值{w1, w2, ..., wn}，试构造一棵含有n个叶子结点的二叉树，每个叶子节点带权为wi，则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树。
 
    特点：哈夫曼树中没有度为1的结点，故由n0 = n2+1以及m= n0+n1+n2，n1=0可推出m=2*n0-1，即一棵有n个叶子节点的哈夫曼树共有2n-1个节点。
 
2.哈夫曼编码
 
    通信传送的目标是使总码长尽可能的短。
 
    变长编码的原则：
     1.使用频率高的字符用尽可能短的编码（这样可以减少数据传输量）；
     2.任一字符的编码都不能作为另一个字符编码的开始部分（这样就使得在两个字符的编码之间不需要添加分隔符号）。这种编码称为前缀编码。
 
    根据每种字符在电文中出现的次数构造哈夫曼树，将哈夫曼树中每个分支结点的左分支标上0，右分支标上1，把从根结点到每个叶子结点的路径上的标号连接起来，作为叶结点所代表的字符的编码。这样得到的编码称为哈夫曼编码。
 
    思考：为什么哈夫曼编码符合变长编码的原则？哈夫曼树所构造出的编码的长度是不是最短的？
 
     哈夫曼树求得编码为最优前缀码的原因： 在构造哈夫曼树的过程中：
 
    1.权值大的在上层，权值小的在下层。满足出现频率高的码长短。
 　2.树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。
     假设每种字符在电文中出现的次数为wi （出现频率即为权值），其码长为li，电文中只有n种字符，则编码后电文总码长为，而哈夫曼树是WPL最小的二叉树，因此哈夫曼编码的码长最小。
 
3.哈夫曼编码实例
 
四种字符以及他们的权值：a:30, b:5, c:10, d:20
 
第一步：构建哈夫曼树
 
 
第二步：为哈夫曼树的每一条边编码
 
 
第三步：生成哈夫曼编码表
 
 
4.代码实现
 
4.1哈夫曼树定义
 
哈夫曼树的存储结构：采用静态三叉链表
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define N 4//带权值的叶子节点数或者是需要编码的字符数
#define M 2*N-1//n个叶子节点构造的哈夫曼树有2n-1个结点
#define MAX 10000
typedef char TElemType;
//静态三叉链表存储结构
typedef struct{
	//TElemType data;
	unsigned int weight;//权值只能是正数
	int parent;
	int lchild;
	int rchild;
}HTNode;//, *HuffmanTree;
typedef HTNode HuffmanTree[M+1];//0号单元不使用

typedef char * HuffmanCode[N+1];//存储每个字符的哈夫曼编码表，是一个字符指针数组，每个数组元素是指向字符指针的指针
 
 
 
4.2构造哈夫曼树
 
//构造哈夫曼树
void createHuffmanTree(HuffmanTree &HT, int *w, int n){
	if(n <= 1)
		return;
	//对树赋初值
	for(int i = 1; i <= n; i++){//HT前n个分量存储叶子节点，他们均带有权值
		HT[i].weight = w[i];
		HT[i].lchild = 0;
		HT[i].parent = 0;
		HT[i].rchild = 0;
	}
	for(int i=n+1; i <=M; i++){//HT后m-n个分量存储中间结点，最后一个分量显然是整棵树的根节点
		HT[i].weight = 0;
		HT[i].lchild = 0;
		HT[i].parent = 0;
		HT[i].rchild = 0;
	}
	//开始构建哈夫曼树，即创建HT的后m-n个结点的过程，直至创建出根节点。用哈夫曼算法
	for(int i = n+1; i <= M; i++){
		int s1, s2;
		select(HT, i-1, s1, s2);//在HT[1...i-1]里选择parent为0的且权值最小的2结点，其序号分别为s1,s2，parent不为0说明该结点已经参与构造了，故不许再考虑
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}
 
 
 
//在HT[1...k]里选择parent为0的且权值最小的2结点，其序号分别为s1,s2，parent不为0说明该结点已经参与构造了，故不许再考虑
void select(HuffmanTree HT, int k, int &s1, int &s2){
	//假设s1对应的权值总是<=s2对应的权值
	unsigned int tmp = MAX, tmpi = 0;
	for(int i = 1; i <= k; i++){
		if(!HT[i].parent){//parent必须为0
			if(tmp > HT[i].weight){
				tmp = HT[i].weight;//tmp最后为最小的weight
				tmpi = i;
			}
		}
	}
	s1 = tmpi;
	
	tmp = MAX;
	tmpi = 0;
	for(int i = 1; i <= k; i++){
		if((!HT[i].parent) && i!=s1){//parent为0
			if(tmp > HT[i].weight){
				tmp = HT[i].weight;
				tmpi = i;
			}
		}
	}
	s2 = tmpi;
}
 
 
 
打印哈夫曼树
 
//打印哈夫曼满树
void printHuffmanTree(HuffmanTree HT, char ch[]){
	printf("\n");
	printf("data, weight, parent, lchild, rchild\n");
	for(int i = 1; i <= M; i++){
		if(i > N){
			printf("  -, %5d, %5d, %5d, %5d\n", HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
		}else{
			printf("  %c, %5d, %5d, %5d, %5d\n", ch[i], HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
		}
	}
	printf("\n");
}
 
 
 
4.3编码
 
为哈夫曼树的每一条分支编码，并生成哈夫曼编码表HC
 
//为每个字符求解哈夫曼编码，从叶子到根逆向求解每个字符的哈夫曼编码
void encodingHuffmanCode(HuffmanTree HT, HuffmanCode &HC){
	//char *tmp = (char *)malloc(n * sizeof(char));//将每一个字符对应的编码放在临时工作空间tmp里，每个字符的编码长度不会超过n
	char tmp[N];
	tmp[N-1] = '\0';//编码的结束符
	int start, c, f;
	for(int i = 1; i <= N; i++){//对于第i个待编码字符即第i个带权值的叶子节点
		start = N-1;//编码生成以后，start将指向编码的起始位置
		c = i;
		f = HT[i].parent;

		while(f){//f!=0,即f不是根节点的父节点
			if(HT[f].lchild == c){
				tmp[--start] = '0';
			}else{//HT[f].rchild == c,注意:由于哈夫曼树中只存在叶子节点和度为2的节点，所以除开叶子节点，节点一定有左右2个分支
				tmp[--start] = '1';
			}
			c = f;
			f = HT[f].parent;
		}
		HC[i] = (char *)malloc((N-start)*sizeof(char));//每次tmp的后n-start个位置有编码存在
		strcpy(HC[i], &tmp[start]);//将tmp的后n-start个元素分给H[i]指向的的字符串
	}
}
 
打印哈夫曼编码表，当编码表生成以后，以后就可以对字符串进行编码了，只要对应编码表进行转换即可
 
//打印哈夫曼编码表
void printHuffmanCoding(HuffmanCode HC, char ch[]){
	printf("\n");
	for(int i = 1; i <= N; i++){
		printf("%c:%s\n", ch[i], HC[i]);
	}
	printf("\n");
}
 
 
 
4.4解码
 
//解码过程：从哈夫曼树的根节点出发，按字符'0'或'1'确定找其左孩子或右孩子，直至找到叶子节点即可，便求得该字串相应的字符
void decodingHuffmanCode(HuffmanTree HT, char *ch, char testDecodingStr[], int len, char *result){
	int p = M;//HT的最后一个节点是根节点，前n个节点是叶子节点
	int i = 0;//指示测试串中的第i个字符
	//char result[30];//存储解码以后的字符串
	int j = 0;//指示结果串中的第j个字符
	while(i<len){
		if(testDecodingStr[i] == '0'){
			p = HT[p].lchild;
		}
		if(testDecodingStr[i] == '1'){
			p = HT[p].rchild;
		}

		if(p <= N){//p<=N则表明p为叶子节点,因为在构造哈夫曼树HT时，HT的m个节点中前n个节点为叶子节点
			result[j] = ch[p];
			j++;
			p = M;//p重新指向根节点
		}
		i++;
	}
	result[j] = '\0';//结果串的结束符	
}
 
 
 
4.5演示
 
int main(){
	HuffmanTree HT;
	
	TElemType ch[N+1];//0号单元不使用，存储n个等待编码的字符
	int w[N+1];//0号单元不使用，存储n个字符对应的权值
	printf("请输入%d个字符以及该字符对应的权值(如:a,20):\n", N);
	for(int i = 1; i <= N; i++){
		scanf("%c,%d", &ch[i], &w[i]);
		getchar();//吃掉换行符
	}//即w里第i个权值对应的是ch里第i个字符元素


	createHuffmanTree(HT, w , N);//构建哈夫曼树
	printHuffmanTree(HT, ch);
	
	HuffmanCode HC;//HC有n个元素，每个元素是一个指向字符串的指针，即每个元素是一个char *的变量
	encodingHuffmanCode(HT, HC);//为每个字符求解哈夫曼编码
	printHuffmanCoding(HC, ch);

	//解码测试用例：abaccda----01000101101110
	char * testDecodingStr = "01000101101110";
	int testDecodingStrLen = 14;
	printf("编码%s对应的字符串是：", testDecodingStr);
	char result[30];//存储解码以后的字符串
	decodingHuffmanCode(HT, ch, testDecodingStr, testDecodingStrLen, result);//解码（译码），通过一段给定的编码翻译成对应的字符串
	printf("%s\n", result);

    return 0;
}
 

 
 
 
本文中的代码可从这里下载：https://github.com/qingyujean/data-structure

 
 
这篇文章存了一年了，因为最近需求颇多，在此分享出来。
 
 
 
 
本文举例帮助理解哈夫曼树的构造过程，并使用C语言实现了哈夫曼树的构造（代码可直接运行）。更多的基础知识不是本文的重点，请自行补充。
 
 
 
0.举例
 
要传输一则报文内容如下：
 
“AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF”
 
请为这段报文设计哈夫曼编码。
以下几点基本此实例进行，梳理了构造哈夫曼树的过程，C原因实现代码，算法时空效率分析。
 
1.构造哈夫曼树并得到哈夫曼编码的过程
 
第一步：计算各个字符的出现次数及频率
 
字符
A
B
C
D
E
F
出现的次数
15
9
8
12
10
5
出现的频率
0.254
0.153
0.136
0.203
0.169
0.085
第二步：选定权值（出现次数及频率是等价的）
 
由于以频率作为权值和以出现的次数作为权值是等价的（频率同时扩大一定倍数即可得到出现的次数），故可以出现的次数作为哈夫曼树的权值。
 
第三步：开始构造哈夫曼树
 
整体构造哈夫曼树的思路如下：
 
从给定的n个权值中选出两个最小的权值，将这两个结点组成一棵新的二叉树，这棵二叉树的根结点的权值是这两个结点的权值之和。
将上述最小的两个权值删去，将新的根节点的权值加入。
重复1和2，直到所有的结点构成一棵二叉树（哈夫曼树）。
 
构造过程图：
 
 
第四步：得到哈夫曼编码
 
按：左分支表示字符‘0’，右分支表示字符‘1’，即可从哈夫曼树中读取哈夫曼编码。
 最终得到的哈夫曼编码如下：
 
原字符
A
B
C
D
E
F
哈夫曼编码
10
110
011
00
111
010
2.代码实现上述哈夫曼编码
 
代码实现哈夫曼编码的总体思路是：
 
初始化输入的字符串，得到权值数组。
将这个权值数组拿来构造哈夫曼树。
从根节点开始读取哈夫曼编码。
 
其中，构造哈夫曼树的具体思路是：
 
先设计一个函数实现每次从权值数组中获取最小的两个权值。
模拟上述构造哈夫曼树的过程进行构造。
 
具体实现代码（C语言）
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//哈夫曼树结点结构
typedef struct {
    int weight;//权值
    int parent;//父结点在数组中的位置下标
    int left;//左孩子在数组中的位置下标
    int right;//右孩子在数组中的位置下标
}HTNode, * HuffmanTree;

//存储哈夫曼编码
typedef char** HuffmanCode;


/*
    函数作用说明：找到两个最小的权值并以w1，w2的形式传递
    主要实现思路：先找到最先出现的两个未参与构建树的结点，再与后面所有未参与构建树的结点比较，更新minFirst，minSecond
    该函数的时间复杂度：O(n) 只需遍历一次数组即可找到最小的两个权值
    参数说明：
        HT是哈夫曼树数组
        n是HT有效的最后一个位置
        w1和w2传递HT数组中权重值最小的两个结点在数组中的位置
*/
void GetTwoMin(HuffmanTree HT, int n, int* w1, int* w2){
    int minFirst, minSecond;
    //遍历
    int index = 1;
    //找到第一个未参与构建树的结点
    while (HT[index].parent != 0 && index <= n) {
        index++;
    }
    minFirst = HT[index].weight;
    *w1 = index;
    //找到第二个未参与构建树的结点
    index++;
    while (HT[index].parent != 0 && index <= n) {
        index++;
    }
    //更新minFirst，minSecond
    if (HT[index].weight < minFirst) {
        minSecond = minFirst;
        *w2 = *w1;
        minFirst = HT[index].weight;
        *w1 = index;
    }else {
        minSecond = HT[index].weight;
        *w2 = index;
    }
    //一一比较
    for (int i = index + 1; i <= n; i++){
        //参与构建树，不考虑
        if (HT[i].parent != 0) {
            continue;
        }
        //更新minFirst，minSecond
        if (HT[i].weight < minFirst) {
            minSecond = minFirst;
            minFirst = HT[i].weight;
            *w2 = *w1;
            *w1 = i;
        }else if (HT[i].weight >= minFirst && HT[i].weight < minSecond) {
            minSecond = HT[i].weight;
            *w2 = i;
        }
    }
}


/*
    函数作用说明：根据输入的权值数组构建哈夫曼树
    主要实现思路：先分配空间并初始化，再依次选两个最小权值进行构建哈夫曼树
    该函数的时间复杂度分析：嵌套主要发生在构建过程，设结点数为n，则时间复杂度为O(n*n)
    参数说明：
        HT是存储哈夫曼树的数组（传递的是地址）
        w是存储结点权值的数组
        n是结点个数
*/
void CreateHuffmanTree(HuffmanTree* HT, int* w, int n){
    //一个字符，无需构建哈夫曼树
    if (n <= 1) return; 
    //计算哈夫曼树总节点数（n只是叶子结点数）
    int m = 2 * n - 1; 
    //分配HT的空间，下标从1开始
    *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); 
    HuffmanTree ht = *HT;
    // 初始化叶子结点
    for (int i = 1; i <= n; i++){
        (ht + i)->weight = *(w + i - 1);
        (ht + i)->parent = 0;
        (ht + i)->left = 0;
        (ht + i)->right = 0;
    }
    //初始化其它结点
    for (int i = n + 1; i <= m; i++){
        (ht + i)->weight = 0;
        (ht + i)->parent = 0;
        (ht + i)->left = 0;
        (ht + i)->right = 0;
    }
    //构建哈夫曼树的过程
    for (int i = n + 1; i <= m; i++){
        int w1, w2;
        GetTwoMin(*HT, i - 1, &w1, &w2);
        (*HT)[w1].parent = (*HT)[w2].parent = i;
        (*HT)[i].left = w1;
        (*HT)[i].right = w2;
        (*HT)[i].weight = (*HT)[w1].weight + (*HT)[w2].weight;
    }
}

/*
    函数作用说明：根据哈夫曼树读取哈夫曼编码
    主要实现思路：从叶子结点开始逆向的读取哈夫曼编码
    该函数时间复杂度：O（n*log n）
    参数说明：
        HT是哈夫曼树
        HC是存储结点哈夫曼编码的二维数组
        n是哈夫曼树叶子结点的个数
*/
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) {
    //为HC分配空间
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
    //存放结点哈夫曼编码
    char* codes = (char*)malloc(n * sizeof(char)); 
    codes[n - 1] = '\0';
    //逆序读取编码
    for (int i = 1; i <= n; i++) {
        //控制该结点哈夫曼编码的起始点
        int begin = n - 1;
        //当前结点在数组中的位置
        int curr = i;
        //当前结点的父结点在数组中的位置
        int parent = HT[i].parent;
        // 向根方向遍历，直到遍历到根
        while (parent != 0) {
            // 左孩子对应编码为0，右孩子编码为1
            if (HT[parent].left == curr) {
                codes[--begin] = '0';
            }else {
                codes[--begin] = '1';
            }
            //继续向根结点的方向遍历
            curr = parent;
            parent = HT[parent].parent;
        }
        //从begin开始，存放的是哈夫曼编码
        (*HC)[i] = (char*)malloc((n - begin) * sizeof(char));
        strcpy((*HC)[i], &codes[begin]);
    }
    free(codes);
}

//输出哈夫曼编码
void PrintHuffmanCode(HuffmanCode htable, char* zf, int n){
    printf("该字符串中每个字符对应的哈夫曼编码如下 : \n");
    for (int i = 1; i <= n; i++) {
        printf("%c 的哈夫曼编码是 = %s\n", zf[i - 1], htable[i]);
    }
}



int main(){
    printf("请输入你需要编码的字符串(999字符以内)：\n");
    char str[1000];
    gets_s(str);
    int len = strlen(str);
    //模拟ascii表
    char asiTable[129];
    int n = 0;
    //初始化
    for (int i = 1; i <= 128; i++) {
        asiTable[i] = 0;
    }
    //将字符个数写入
    for (int i = 0; i < len; i++) {
        asiTable[str[i]]++;
    }
    //统计有效字符个数
    for (int i = 1; i <= 128; i++) {
        if (asiTable[i] != 0) {
            n++;
        }
    }
    //动态分配数组
    int* w = (int*)malloc(n * sizeof(int));
    char* f = (char*)malloc((n + 1) * sizeof(char));
    int index = 0;
    //得到权值数组和对应的字符
    for (int i = 1; i <= 128; i++) {
        if (asiTable[i] != 0) {
            w[index] = asiTable[i];
            f[index] = (char)i;
            index++;
        }
    }
    HuffmanTree huffmanTree;
    HuffmanCode huffmanCodes;
    CreateHuffmanTree(&huffmanTree, w, n);
    HuffmanCoding(huffmanTree, &huffmanCodes, n);
    PrintHuffmanCode(huffmanCodes, f, n);
    return 0;
}
 
运行结果图：
 
 
3.算法效率分析
 
时间复杂度：
 
假设输入的字符串长度为k，不同字符数为n，时间复杂度的分析如下：
 
整体分析： 整个程序主要消耗的时间在于构造哈夫曼树和得到哈夫曼编码，其中构造哈夫曼树所消耗的时间最多，故总的时间复杂度为O(n^2)
对于处理输入字符串的数据部分：主要消耗的时间是统计不同字符出现的次数，此处的时间复杂度为：O(k)
对于构造哈夫曼树的部分：主要消耗的时间是循环构造树，其中每次循环构造树时，需要先选取两个最小权值，这个选取是线性的，时间复杂度为O(n)，因此总的时间复杂度为O(n^2)
对于得到哈夫曼编码的部分：主要消耗的时间是循环获取编码，其中每次循环获取编码时，需要向上遍历到根节点，时间复杂度为O(log n)，因此总的时间复杂度为O(n*log n)
对于输出哈夫曼编码的部分：线性的输出，时间复杂度为O(n)
 
空间复杂度：
 
假设输入的字符串长度为k，不同字符数为n，空间复杂度的分析如下：
 
整体分析： 整个程序中所用到的空间有：ascii表占128，w数组占n，f数组占n+1，HT数组占2n，HC数组占nlogn。其中HC数组所消耗的空间最多，因此，总的空间复杂度为**O(nlog n)**
对于处理数据部分： 主要为n数组和f数组所消耗的空间，为O(n)
对于构造哈夫曼树部分： 主要为哈夫曼树所消耗的空间，为O(n)
对于得到哈夫曼编码部分： 主要为存储哈夫曼编码的HC数组所消耗，为O(n*log n)
 
 
 
 
ATFWUS POST：2021-06-20 WRITE：2020-07-01