C语言-哈夫曼树与哈夫曼编码的实现

1、什么是哈夫曼树

结点的权：树中的结点被赋予一个表示某种意义的数值；
结点的带权路径长度：从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积；
树的带权路径长度（WPL）：$WPL=\sum _{i=1}^n{w}_i{l}_i$
$w_i$是第i个叶结点所带的权值，$l_i$是该叶结点到根结点的路径长度；
哈夫曼树：在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树；

---

2、哈夫曼树的构造

哈夫曼树的构造过程：

给定n个权值分别为$w_1$,$w_2$,…,$w_n$的结点：

• 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F；
• 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，新结点的权值为左右子树根结点的权值之和；
• 从F中删除刚才选出的两棵树，同时将新得到的树加入F中；
• 重复2,3，直到F中只剩下一棵树为止；

以如下结点为例，构造一棵哈夫曼树：
结点：{a:45 , b:13 , c:12 , d:16 , e:9 , f:5}

哈夫曼树的特点：

• 每个初始结点最终都是叶结点，且权值越小的结点到根结点的路径越大；
• 构造过程中共新建了n-1个结点，因此哈夫曼树的结点总数为2n-1；
• 哈夫曼树中不存在度为1的结点；

---

3、哈夫曼编码

哈夫曼编码：又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。
该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码(有时也称为霍夫曼编码)。

由哈夫曼树得到哈夫曼编码：可将字符的编码解释为从根至该字符的路径上边标记的序列，其中一般边标记0表示左孩子，标记1表示右孩子。

---

3、哈夫曼树与哈夫曼编码的代码实现

哈夫曼树与哈夫曼编码的结构体：

//赫夫曼树结点
typedef struct
{
	int weight;//权值
	int parent, lchild, rchild;
}HTNode,*HTTree;

//赫夫曼编码
typedef struct
{
	char ch;//结点名称
	char code[10];//结点的编码
}CodeNode,*HuffmanCode;

哈夫曼树的初始化：

//赫夫曼树的初始化,m表示赫夫曼树总的结点个数
void InitHuffmanTree(HTTree &HT, int m)
{
	HT=(HTTree)malloc(m * sizeof(HTNode));//为赫夫曼树结点申请空间

	//赫夫曼树结点的初始化
	for (int i = 0; i < m; i++)
	{
		HT[i].weight = 0;
		HT[i].parent = -1;
		HT[i].lchild = -1;
		HT[i].rchild = -1;
	}
}

哈夫曼树挑选2个最小权值的结点(重点)：

//从n个结点中选取2个最小的结点,将其下标保存到min1,min2
void SelectMin(HTTree &HT, int n, int &min1, int &min2)
{
	//临时结点，保存没有父结点的结点
	typedef struct
	{
		int LocWeight;
		int loc;//结点原始的下标
	}TempNode,*TempTree;

	int i, j=0;
	int m1, m2;
	m1 = m2 = 0;

	TempTree temptree = (TempTree)malloc(n * sizeof(TempNode));

	//将无父结点的结点存入temptree
	for (i = 0; i < n; i++)
	{
		if (HT[i].parent == -1 && HT[i].weight != 0)
		{
			temptree[j].LocWeight = HT[i].weight;
			temptree[j].loc = i;
			j++;
		}
	}

	//选择权值最小的结点
	for (i = 0; i < j; i++)
	{
		if (temptree[i].LocWeight < temptree[m1].LocWeight)//不取等号，让其选择前面最小的结点
			m1 = i;
	}

	//选择权值次小的结点
	for (i = 0; i < j; i++)
	{
		if (m1 == m2)
			m2++;//当m1在第一个位置时，m2后移一位
		if (i != m1 && temptree[i].LocWeight <= temptree[m2].LocWeight)
			m2 = i;
	}
	min1 = temptree[m1].loc;
	min2 = temptree[m2].loc;
}

哈夫曼树的创建：

//由n个结点创建HuffmanTree
void CreateHuffmanTree(HTTree &HT, int weigh[],int n)
{
	int total = 2 * n - 1;//HuffmanTree中总的结点个数
	int i, min1, min2;

	InitHuffmanTree(HT, total);

	for (i = 0; i < n; i++)
		HT[i].weight = weigh[i];

	//每次选择两个权值最小的结点合并
	for (i = n; i < total; i++)
	{
		SelectMin(HT, i, min1, min2);
		HT[min1].parent = i;
		HT[min2].parent = i;
		HT[i].lchild = min1;
		HT[i].rchild = min2;
		HT[i].weight = HT[min1].weight + HT[min2].weight;
	}

}

哈夫曼编码的创建：

注意：这里采用的方法是从叶子结点向根结点遍历的方式，保存哈夫曼编码，在实现时要注意字符的赋值问题。

//HuffmanCode的创建
void CreateHuffmanCode(HTTree &HT, HuffmanCode &HC, char codename[], int n)
{
	int i, start,par,c;
	char *cd = (char *)malloc(n * sizeof(char ));
	cd[n-1] = '\0';//临时存储编码

	HC = (HuffmanCode)malloc(n * sizeof(CodeNode));

	//为每个结点创建HuffmanCode
	for (i = 0; i < n; i++)
	{
		HC[i].ch = codename[i];
		start = n - 1;
		c = i;

		//从叶子结点向上查找到根
		while ((par = HT[c].parent) >= 0)
		{
			--start;

			//看c是父结点的左子树还是右子树
			if (HT[par].lchild == c)
				cd[start] = '0';
			else
				cd[start] = '1';
			c = par;
		}

		int g = 0;
		for (int l = start; l < n; l++)
			HC[i].code[g++] = cd[l];
	}
	free(cd);
}

哈夫曼编码的输出函数：

void OutPutHuffmanCode(HuffmanCode HC, int n)
{

	for (int i = 0; i < n; i++)
		printf("%c: %s\n", HC[i].ch, HC[i].code);

}

至此，哈夫曼树与哈夫曼编码的函数实现都已完成，接下来在main函数中测试一下，与下面这种图对比。

int main()
{
	int n = 6;
	char codename[6] = { 'a','b','c','d','e','f' };
	int weigh[6] = { 45,13,12,16,9,5 };

	HTTree HT;
	HuffmanCode HC;

	CreateHuffmanTree(HT, weigh, n);
	CreateHuffmanCode(HT, HC, codename, n);
	OutPutHuffmanCode(HC, n);

	return 0;
}

---