【数据结构——哈夫曼树及其应用】

一、哈夫曼树的基本概念

1、权：赋予某个实体的一个量
2、路径：从树中的一个结点到另一个结点之间的分支构成这两个结点间的路径

1、路径长度：路径上的分支数
2、树的路径长度：从树根到每个结点的路径长度之和
3、结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积
4、树的带权路径长度：树中所有带权结点的路径长度之和

3、哈夫曼树：带权路径长度最小的树

权值分别为7、5、2、4，构造有4个叶子结点的二叉树

二、哈夫曼树的构造算法

基本思想： 使权值大的结点靠近根
操作要点：对权值的合并、删除与替换，总是合并当前权值最小的两个

（一）哈夫曼树的构造过程

1、根据给定的n个权值（w1,w2…wn）,构造n棵只有根结点的二叉树，这n棵树构成一个森林F
2、在森林中选取两棵结点权值最小的树做左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和
3、在森林中删除这两棵树，同时将新得到的二叉树加入森林中
4、重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

（二）哈夫曼树构造算法的实现

建立哈夫曼树： 树种度为1的结点为0
一棵有n个叶子结点的哈夫曼树中，度为2的结点有n-1个，则共有2n-1个，可以用大小为2n-1的一维数组来存储，每个结点结构可以根据操作设置

需要的操作： 在求编码时，要从叶子结点出发走一条叶子到根的路径；而译码需要从根出发走一条从根到叶子的路径。对于每个结点而言，既需要双亲信息，又需要孩子结点的信息，由此，设定如下的存储结构：

typedef struct
{
	int weight;//结点的权值
	int parent, lchild, rchild;//双亲、左孩子、右孩子的下标
}HTnode,*HuffmanTree;

构造哈夫曼树

1、初始化

1、首先开辟2n个存储单元
2、循环2n-1次，依次将1到2n-1所有单元的双亲，左右孩子的下标初始化为0
3、循环n次，输入所以叶子结点的权值

	/*初始化*/
	if (n <= 1)
		return;
	int m = 2 * n - 1;//m为哈夫曼树中总结点的个数
	HT = new HTnode[m + 1];//0号单元未用，所以需要开辟m+1个单元，HT[m]表示根结点
	for (int i = 1;i <= m;++i)//将1-m号单元的双亲，左右孩子的下标都初始化为0
	{
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	for (int i = 1;i <= n;++i)
	{
		cin >> HT[i].weight;//输入前n个单元中叶子结点的权值
	}

2、创建树

创建树：循环n-1次，通过n-1次的选择，删除与合并来创建哈夫曼树
1、选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2;
2、删除是指将结点s1和s2的双亲改为非0
3、合并就是将s1和s2的权值和作为一个新结点的权值依次存入到数组的第n+1之后的单元中，同时记录这个新结点左孩子的下标s1，右孩子的下标s2

	/*初始化工作结束，下面开始创建哈夫曼树*/
	for (int i = n + 1;i <= m;++i)
	{//通过n-1次的选择、删除、合并来创建哈夫曼树
		Select(HT, i - 1, s1, s2);//选择两个其双亲域为0且权值最小的结点
		HT[s1].parent = i;HT[s2].parent = i;//得到新结点i,将s1\s2的双亲域由0改为i
		HT[i].lchild = s1;HT[i].rchild = s2;//s1、s2分别作为i的左右孩子
		HT[i].weight = HT[s1].weight + HT[s2].weight;//i的权值为左右孩子的权值之和
	}

3、完整的创建哈夫曼树代码

void CreateHuffmanTree(HuffmanTree& HT, int n)//构造哈夫曼树，n为带权值的叶子结点个数
{
	/*初始化*/
	if (n <= 1)
		return;
	int m = 2 * n - 1;//m为哈夫曼树中总结点的个数
	HT = new HTnode[m + 1];//0号单元未用，所以需要开辟m+1个单元，HT[m]表示根结点
	for (int i = 1;i <= m;++i)//将1-m号单元的双亲，左右孩子的下标都初始化为0
	{
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	for (int i = 1;i <= n;++i)
	{
		cin >> HT[i].weight;//输入前n个单元中叶子结点的权值
	}
	/*初始化工作结束，下面开始创建哈夫曼树*/
	for (int i = n + 1;i <= m;++i)
	{//通过n-1次的选择、删除、合并来创建哈夫曼树
		Select(HT, i - 1, s1, s2);//选择两个其双亲域为0且权值最小的结点
		HT[s1].parent = i;HT[s2].parent = i;//得到新结点i,将s1\s2的双亲域由0改为i
		HT[i].lchild = s1;HT[i].rchild = s2;//s1、s2分别作为i的左右孩子
		HT[i].weight = HT[s1].weight + HT[s2].weight;//i的权值为左右孩子的权值之和
	}
}

三、哈夫曼编码

1、哈夫曼编码的提出

在远程通讯中，要将待传字符转换成由二进制的字符串

2、哈夫曼编码的构造——哈夫曼树的应用

1、基本思想：概率大的字母用短码，小的用长码，构造哈夫曼树，概率越大，路径越短。
2、哈夫曼编码：在哈夫曼的每个分支上标上0或1
——结点的左分支标0，右分支标1
——把从根到每个叶子的路径上的标号连接起来，构成一个二进制串，该二进制串就成为该叶子代表的哈夫曼编码

哈夫曼编码的实例

哈夫曼译码的实例
译码：对编码后的二进制编码，从哈夫曼的根结点出发，若当前读入0，则走向左孩子，否则走向右孩子，到达某一叶子便译出相应的字符编码，然后重新从根结点出发继续译码，直到结束。

根据哈夫曼树求哈夫曼编码的算法：
1、在构造哈夫曼树之后，求哈夫曼编码的主要思想是：

1、依次以叶子为出发点，向上回溯至根结点为止
2、回溯时走走左分支生成代码0，走右分支生成代码1
3、由于每个哈夫曼编码是变长编码，因此使用一个指针数组来存放每个字符编码串的首地址。

//-----哈夫曼编码表的存储表示----
typedef char** HuffmanCode;
//动态分配数组存储哈夫曼编码表

2、各字符的哈夫曼编码存储在由HuffmanCode定义的动态分配的数组HC中，为了实现方便，数组的0号单元不使用，从1号单元开始使用，所以数组HC的大小为n+1,即编码表HC包括n+1.

算法步骤： 根据哈夫曼树求哈夫曼编码

算法描述：

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{//从叶子到根逆向求每个字符的哈夫曼编码，储存在编码表HC中
	HC = new char* [n + 1];//分配n个字符编码的头指针矢量
	cd = new char[n];//分配临时存放编码的动态数组空间
	cd[n - 1] = '\0';//编码结束符
	for (int i = 1;i <= n;++i)//逐个字符求哈夫曼编码
	{
		start = n - 1;//start开始时指向最后，即编码结束符的位置
		c = i;f = HT[i].parent;//f指向结点c的双亲结点
		while (f != 0)//从叶子结点开始向上回溯，直到根结点
		{
			--start;//回溯一次，start向前指一个位置
			if (HT[f].lchild == c)
				cd[start] = '0';//结点c是f的左孩子，则生成代码0
			else
				cd[start] = '1';//结点c是f的右孩子，则生成代码1
			c = f;f = HT[f].parent;//继续向上回溯
		}//求出第i个字符的编码
		HC[i] = new char[n - start];//为敌i个字符编码分配空间
		strcpy(HC[i], &cd[start]);//将求得的编码从临时空间cd复制到HC当前行中
	}
	delete cd;//释放临时空间
}

补充哈夫曼树的译码：输入一串以哈夫曼编码方式编码的字符串，从根结点出发走向叶子结点，找到叶子结点，后输出该结点的字符然后继续读取编码串，直至读完。

算法描述：

//哈夫曼树的译码
void DeHuffumanTree(HuffmanTree HT)
{
	char s[100];
	gets(s);
	i = m;//m为根结点
	j = 0;
	while (s[j] != '\0')//遍历编码串
	{
		if (s[j] == '0')
			i = HT[i]->lchild;//走向左孩子
		else
			i = HT[i]->rchild;//走向右孩子
		if (HT[i]->lchild == NULL)//看该结点是否是叶子结点
		{
			printf("%c", HT[i]->data);//是的话，输出根结点
			i = m;//回到根结点重新开始
		}
		j++;//无论是否找到叶子结点都读取下一个编码串字符
	}
}