哈夫曼树的概念以及算法简述

1.相关名词概念：

  路径和路径长度：从树中的一个节点到达另外一个节点的之间的分支为路径，其长度为路径长度。树的路径长度定义为从根节点开始到达每一个节点的路径长度之和。

  权值：节点的权值为该节点在所有节点中占的比重，拿一个文本文件来说，某个字符的节点权重即为该字符出现的次数与该文本文件中所有字符出现的次数的比值。

带权路径长度：树中某个节点的带权路径长度为该节点的路径长度与该节点的权重的乘积。一颗树的带权路径长度（WPL）为该树中的所有叶节点的带权路径长度之和。

带权路径长度最小的树二叉树即为哈夫曼树（最优二叉树）！

哈夫曼树的算法描述：

1.根据给定的n个权值，构成n棵二叉树的集合：F = {T1,T2,T3,T4,…}。其中每棵二叉树中只有一个带权值为W_i的根节点，其左右孩子都为空。
2，在F中选取两棵权值最小的树，作为一个新节点的左右子树，构造出一课新的二叉树，且置新的树的权值为两棵左右子树的权值之和。
3，在F中删除这两棵左右子树，并将新的二叉树加入F中。
4，重复2,3过程，直到F只含有一棵二叉树。（这里即为树中根节点）

哈夫曼树的抽象数据类型的定义

/* 哈夫曼树节点 */
typedef struct _haffman {
	char data;							//用来存放节点字符的数据域
	int weight;							//权重
	struct _haffman *leftChild;			//左孩子节点
	struct _haffman *rightChild;		//右孩子节点

}HaffNode;

宏定义

#define MAX_SIZE 256					//编码数量
#define HALF_MAX 128					//一半的数量
#define ASCII_SIZE 128					//ASCII码的数量

定义一些需要用到的全局变量

/* 以顺序结构存储的树节点--编码解码的字符映射表 --即存储原数据*/
HaffNode node[MAX_SIZE];

/* 用来保存所有左孩子节点--为总节点数的一半 */
HaffNode left[HALF_MAX];

/* 用来保存所有右孩子节点 --为总节点数的一半*/
HaffNode right[HALF_MAX];

/** 创建一个二维数组，用来保存每一个叶节点的编码 */
char code[MAX_SIZE][HALF_MAX];

构造哈夫曼树的代码实现：

/* 构造哈夫曼树
	@param node 哈夫曼树的根节点
	@param length 节点数组的长度

*/
void CreatHaffmanTree(HaffNode * node, int length)
{
	if (length <= 0)
	{
		printf("长度为0，无法创建哈夫曼树！\n");
		return;
	}
	SortHaffmanNode(node, length);		//先进行节点权值的排序
	HaffNode parent;									//构建一个以node数组最后两个节点组成的父节点
	left[length - 1] = node[length - 1];				//权重最小的节点
	right[length - 1] = node[length - 2];				//权重第二小的节点
	parent.weight = left[length - 1].weight + right[length - 1].weight;	//累加权重
	parent.leftChild = &left[length - 1];				//左孩子指向相对小的值	
	parent.rightChild = &right[length - 1];				//右孩子指向相对更大的值
	node[length - 2] = parent;					//将倒数第二个替代为parent节点，数组长度 - 1，递归创建哈夫曼树
	CreatHaffmanTree(node, length - 1);			//递归，并且长度自动减一，每一次都会进行一次重新排序。

}

实现构造哈夫曼树前需要先将节点数组的权重进行排序，即为上述SorHaffmanNode();函数，这里我使用的是冒泡排序的方法进行排序。
以下是其代码实现：

/* 哈夫曼树的排序 --使用冒泡排序
 *@param node 节点数组
 * @param length 节点的数量
*/
void SortHaffmanNode(HaffNode * node, int length)
{
	HaffNode tempNode;
	for (int i = 0; i < length - 1; i++)
	{
		for (int j = 0; j < length - i - 1; j++)
		{
			if (node[j].weight < node[j + 1].weight)		//根据权重比较来排序--从大到小
			{
				tempNode = node[j];
				node[j] = node[j + 1];
				node[j + 1] = tempNode;
			}
		}
	}
}

哈夫曼树的编码：

过程：从根节点出发，左支的编码为0，右支的编码为1.直到叶节点结束，其编码即为该节点数据的编码。每一次遍历都重新从根节点出发重新遍历。
代码实现：

/**
 * 创建一个编码函数
 * @param node 哈夫曼树节点数组
 * @param tempnode 编码后的字符数组
 * @param index 当前操作节点数组的下标
 */
void Coding(HaffNode * node, char * tempnode, int index)
{
	if (!node) return;
	if (node->leftChild == NULL || node->rightChild == NULL)
	{
		//使用字符数组，将编码形式保存
		tempnode[index] = '\0';			//字符串结束的标志
		strcpy(code[node->data - 0], tempnode);			//这里叶节点的值使用的是字母，可以使用ASCII码的形式确认存储的位置，也可以用强制类型转换
	}
	tempnode[index] = '0';			//左支路的编码为0
	Coding(node->leftChild, tempnode, index + 1);			//先递归调用左支路，
	tempnode[index] = '1';			//右支路的编码为1
	Coding(node->rightChild, tempnode, index + 1);			//再递归调用右支路
}

哈夫曼树的解码过程：

过程：对于一段由编码0/1构成的二进制文件，在同个树而言，重第一个开始，遇到0则访问左子树，遇到1则访问右子树。直到该节点没有了左右节点为止，即这段01字符即可解码为该叶子节点所对应的字符。
代码实现

/** 解码过程 -- flag 0/1 来表示往哪边走，左走0，右走1 */
HaffNode *Unziped(HaffNode *node, int flag)
{
	if (flag == 1)
		return node->rightChild;		//右子树
	else if(flag == 0)
		return node->leftChild;			//左子树
	return NULL;
}

下面是所有的代码实现:
main.c

#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include "HaffmanTree.h"
#include <string.h>

/**
	进行哈夫曼树编码的过程
	1，打开文件，进行文件的字符读取，并进行哈夫曼编码，将压缩的数据保存另外一个文件ziped.txt中
	2，解码文件，对二进制文件进行解码，将解码的结果保留在另外一个文件result.txt中

*/

int main() {
    
	//保存到二进制文件中的无符号字符，即解码过后对应的字符，这里即为00000000
	unsigned char saveChar = 0;
	//中间变量
	unsigned char tempchar = 0;	
	
	printf("使用哈夫曼树实现文件的压缩，（只支持ASCII字符）\n");
	//以只读的形式打开文本文件，该文件就是要进行压缩的源文件
	FILE * inputFile = fopen("input.txt", "r");			
	//以二进制的形式写入该文本文件，相当于压缩包	
	FILE * zipedFile = fopen("ziped.txt","wb");					
	
	//文件中保存的字符个数，源文件
	int fileLength = 0;		
	//定义一个 数组，用来保存每个ASCII码的权重									
	int asciicount[128] = {
    0};	
	//保留读取到的字符								
	char readChar;												

	while ((readChar = fgetc(inputFile)) != EOF) {
    
		//逐个读取字符，并累加
		fileLength++;
		//将读取到的字符作为下标，统计每个字符出现的次数										
		asciicount[readChar - 0]++;								
	}
	//字符种类计数器					
	int cnt = 0;												
	for (int i = 0; i < 128; i++) {
    
		if(asciicount[i] != 0) {
     //统计节点的数量，即文件中出现多少种字符 
			node[cnt].data = i;
			// 将字符出现的次数当成权重 
			node[cnt].weight = asciicount[i];
			//节点数量累加
			cnt++;								
		}
	}
	CreatHaffmanTree(node, cnt);	//创建哈夫曼树
	char tempcode[10];				//编码的值 0/1
	Coding(node, tempcode, 0);		//编码，从零开始
	cnt = 0;						//计数器置零
	fseek(inputFile, 0L, 0);		//将文件定位于文件头，偏移0个字节长度
	int zipedLength = 0;
	while ((readChar = fgetc(inputFile)) != EOF) {
    		//逐位将编码保存到文件中
		for (int i = 0; i < strlen(code[(int)readChar]); i++) {
    
			saveChar |= (code[(int)readChar][i] - '0');			//将saveChar的最后一位赋值为0/1
			cnt++;												//累加计数器
			if (cnt == 8) {
    	//如果计数累加到8，8位一个字符，则写入文件
				//在文件中写入一个unsigned char 大小的字符
				fwrite(&saveChar, sizeof(unsigned char), 1, zipedFile);		
				cnt = 0;
				saveChar = 0;
				zipedLength++;					//压缩文件字符大小累加，方便算出压缩比
			} else {
    
				//saveChar的值左移一位，为下次给最低位赋值做好准备
				saveChar <<= 1;										
			}

		}

	}
	if (cnt < 8) {
    			//处理不足8个字符的情况
		saveChar <<= (8 - cnt);
		cnt = 0;
		saveChar = 0;
		fwrite(&saveChar, sizeof(unsigned char), 1, zipedFile);
		zipedLength++;
	}
	fclose(inputFile);
	fclose(zipedFile);
	printf("文件压缩成功，请在文件夹中查看以压缩的文件\n");
	printf("源文件的字符个数：%d,压缩后文件的个数：%d  %.2lf\n", fileLength, zipedLength, (double)zipedLength / fileLength);

	//哈夫曼树的解码过程
	zipedFile = fopen("ziped.txt", "rb");
	FILE * resultFile = fopen("result.txt", "w");
	cnt = 0;	//计数器清零
	HaffNode * currNode = &node[0];
	while (fread(&readChar, sizeof(unsigned char), 1, zipedFile)) {
    
		if (fileLength == 0)
			break;
		//遍历readChar中的每个二进制
		for (int i = 0; i < 8; i++) {
    
			tempchar = readChar & 128;				//取readChar的最高128为10000000
			tempchar >>= 7;							//每一次右移7位
			readChar <<= 1;							//最高位已经被取了，所以在进行移动
			currNode = Unziped(currNode, tempchar - 0);
			//判断叶节点
			if (currNode->leftChild == NULL || currNode->rightChild == NULL) {
    
				fprintf(resultFile, "%c", currNode->data);
				cnt++;
				currNode = &node[0];			//每一次遍历都需从根节点开始
			}
		}
	}
	fclose(inputFile);
	fclose(resultFile);
	printf("解码成功，请查看文件；result.txt");

	system("pause");

	return 0;
}

Haffman.h

#pragma warning(suppress : 4996)

/*
  哈夫曼树的顺序存储
  哈夫曼树编码的压缩文件的主要思路
  1，读取某个文本文件，统计各个字符出现的个数，作为权重
  2，构建哈夫曼树，生成每个字符对应的编码，将编码保存到压缩文件中
  3，文件解压缩，实际就是将压缩文件翻译过来，然后在保存在解压缩文件中的过程
  
  @autor 小机

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 256					//编码数量
#define HALF_MAX 128					//一半的数量
#define ASCII_SIZE 128					//ASCII码的数量

/* 哈夫曼树节点 */
typedef struct _haffman {
    
	char data;							//用来存放节点字符的数据域
	int weight;							//权重
	struct _haffman *leftChild;			//左孩子节点
	struct _haffman *rightChild;		//右孩子节点

}HaffNode;

/* 以顺序结构存储的树节点--编码解码的字符映射表 --即存储原数据*/
HaffNode node[MAX_SIZE];

/* 用来保存所有左孩子节点--为总节点数的一半 */
HaffNode left[HALF_MAX];

/* 用来保存所有右孩子节点 --为总节点数的一半*/
HaffNode right[HALF_MAX];

/** 创建一个二维数组，用来保存每一个叶节点的编码 */
char code[MAX_SIZE][HALF_MAX];

/* 哈夫曼树的排序 --使用冒泡排序的方法*/
void SortHaffmanNode(HaffNode * node, int length);

/* 构造哈夫曼树
	@param node 哈夫曼树的节点数组
	@param length 节点数组的长
*/
void CreatHaffmanTree(HaffNode * node, int length);

/** 
 * 创建一个编码函数
 * @param node 哈夫曼树节点数组
 * @param tempnode 编码后的字符数组
 * @param index 当前操作节点数组的下标
 */
void Coding(HaffNode * node, char * tempnode, int index);

/** 解码过程 -- flag 0/1 来表示往哪边边的树枝走，左走0，右走1 */
HaffNode *Unziped(HaffNode *node, int flag);

Haffman.c

#include "HaffmanTree.h"


/* 哈夫曼树的排序 --使用冒泡排序*/
void SortHaffmanNode(HaffNode * node, int length) {
    
	HaffNode tempNode;
	for (int i = 0; i < length - 1; i++) {
    
		for (int j = 0; j < length - i - 1; j++) {
    
			if (node[j].weight < node[j + 1].weight) {
    	//根据权重比较来排序--从大到小
				tempNode = node[j];
				node[j] = node[j + 1];
				node[j + 1] = tempNode;
			}
		}
	}
}
/* 构造哈夫曼树
	@param node 哈夫曼树的根节点
	@param length 节点数组的长度

*/
void CreatHaffmanTree(HaffNode * node, int length) {
    
	if (length <= 0) {
    
		printf("长度为0，无法创建哈夫曼树！\n");
		return;
	}
	// 先排序
	SortHaffmanNode(node, length);
	//构建一个以node数组最后两个节点组成的父节点
	HaffNode parent;
	//权重最小的节点
	left[length - 1] = node[length - 1];
	//权重第二小的节点
	right[length - 1] = node[length - 2];
	parent.weight = left[length - 1].weight + right[length - 1].weight;	//累加权重
	//左孩子指向相对小的值
	parent.leftChild = &left[length - 1];
	//右孩子指向相对更大的值
	parent.rightChild = &right[length - 1];
	//将倒数第二个替代为parent节点，数组长度 - 1，递归创建哈夫曼树
	node[length - 2] = parent;
	//递归，并且长度自动减一
	CreatHaffmanTree(node, length - 1);

}

/**
 * 创建一个编码函数
 * @param node 哈夫曼树节点数组
 * @param tempnode 编码后的字符数组
 * @param index 当前操作节点数组的下标
 */
void Coding(HaffNode * node, char * tempnode, int index) {
    
	if (!node) return;
	if (node->leftChild == NULL || node->rightChild == NULL) {
    
		//使用字符数组，将编码形式保存
		tempnode[index] = '\0';			//字符串结束的标志
		//这里叶节点的值使用的是字母，可以使用ASCII码的形式确认存储的位置，也可以用强制类型转换
		strcpy(code[node->data - 0], tempnode);			
	}
	tempnode[index] = '0';			//左支路的编码为0
	Coding(node->leftChild, tempnode, index + 1);			//先递归调用左支路，
	tempnode[index] = '1';			//右支路的编码为1
	Coding(node->rightChild, tempnode, index + 1);			//再递归调用右支路
}


/** 解码过程 -- flag 0/1 来表示往哪边走，左走0，右走1 */
HaffNode *Unziped(HaffNode *node, int flag) {
    
	if (flag == 1)
		return node->rightChild;		//右子树
	else if(flag == 0)
		return node->leftChild;			//左子树
	return NULL;
}

注意上面程序只能编码ASCII码的文件，如果文件中有中文字符的存在会存在乱码的情况，默认输入文件为input.txt，压缩文件为ziped.txt,解压文件为result.txt