数据结构之最优二叉树

??数据结构是程序设计的重要基础，它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高利用计算机解决问题的效率服务。
??数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的 逻辑结构，数据元素及元素之间关系的存储称为 存储结构(或物理结构)。数据结构按照逻辑关系的不同分为 线性结构和 非线性结构两大类，其中，非线性结构又可分为树结构和图结构。
??树结构是一种非常重要的非线性结构，该结构中的一个数据元素可以有两个或两个以上的直接后继元素，树可以用来描述客观世界中广泛存在的层次结构关系。
??二叉树是 n(n≥0)个结点的有限集合，它或者是空树(n=0)，或者是由一个根结点及两棵不相交的且分别称为左、右子树的二叉树所组成。

1、最优二叉树

??最优二叉树又称为哈夫曼树，它是一类带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。
??树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积。
??树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为
$$WPL={\Sigma }_{k=1}^n{w}_k{l}_k$$
其中，n 为带权叶子结点数目，w_k 为叶子结点的权值，l_k为叶子结点到根的路径长度。
??哈夫曼树是指权值为 w₁,w₂,···,w_n 的n个叶子结点的二又树中带权路径长度最小的二叉树。
??例如，下图所示的具有4个叶子结点的二叉树，其中以图 (b) 所示的二叉树带权路径长度最小。

??那么如何构造最优二叉树呢? 构造最优二叉树的哈夫曼算法如下。
??（1）根据给定的n个权值 {w₁,w₂,···,w_n}，构成n颗二叉树的集合F= (T₁,T₂,···,T_n}，其中，每棵树 T_i 中只有一个带权为 w_i 的根结点，其左、右子树均空。
??（2）在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
??（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。
??重复(2)、(3) 步，直到 F 中只含一棵树时为止，这棵树便是最优二叉树(哈夫曼树)。
??由此算法可知，以选中的两棵子树构成新的二叉树，哪个作为左子树，哪个作为右子树，并没有明确。所以，具有n 个叶子结点的权值为 w₁,w₂,···,w_n 的最优二叉树不唯一，但其 WPL 值是唯一确定的。
??当给定了 n 个权值后，构造出的最优二叉树中的结点数目 m 就确定了，即 m=2×n-1，所以可用一维的结构数组来存储最优二叉树，下面举例说明。

#define MAXLEAFNUM 50						/*最优二叉树中的最多叶子数目*/
typedef struct nodef{
	char ch;								/*结点表示的字符，对于非叶子结点，此域不用*/
	int weight;								/*结点的权值*/
	int parent;								/*结点的父结点的下标，为0时表示无父结点*/
	int lchild,rchild;						/*结点的左、右孩子结点的下标，为0 时表示无孩子结点*/
}HuffmanTree[2*MAXLEAFNUM];
typedef char* HuffmanCode[MAXLEAFNUM+1];

??【函数】创建最优二叉树。

void createHTree(HuffmanTree HT, char *c, int *w,int n)
/*数组 c[0..n-1]和 w[0..n-1]存放了n个字符及其概率，构造哈夫曼树HT*/
{
	int i,sl,s2;
	if (n <= 1) return;
	for(i=l; i<-n; i++){ /*根据n个权值构造n只有根结点的二叉树*/
		HT[i].ch = c[i-l]; 
		HT[i].weight = w[i-l];
		HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	}
	for(;i<2*n;++i) { /*初始化*/
		HT[i].parent=0;
		HT[i].lchild=0; 
		HT[i].rchild=0;
	}
	for(i= n+l; i<2*n; i++)
		/*从HT[l..i-1]中选择 parent 为0且weight最小的两棵树，其序号为 s1和s2*/
		select(HT,i-1,s1,s2);
		HT[sl].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[i].weight = HT[sl].weight + HT[s2].weight;
	}/*for*/
}/* createHTree*/

2、哈夫曼编码

??若对每个字符编制相同长度的二进制码，则称为等长编码。例如，英文字符集中的 26个字符可采用5 位二进制位串表示，按等长编码格式构造一个字符编码表。发送方按照编码表对信息原文进行编码后送出电文，接收方对接收到的二进制代码按每 5位一组进行分割，通过字符的编码表即可得到对应字符，实现译码。
??等长编码方案的实现方法比较简单，但对通信中的原文进行编码后，所得电文的码串过长不利于提高通信效率，因此希望缩短码串的总长度。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，那么传送的电文码串总长度则可减少。
??如果要设计长度不等的编码，必须满足下面的条件：任一字符的编码都不是另一个字符的编码的前缀，这种编码也称为前缀码。对给定的字符集 D={d₁,d₂,···,d_n} 及字符的使用频率W={w₁,w₂,···,w_n}，构造其最优前缀码的方法为： 以d₁,d₂,···,d_n 作为叶子结点，w₁,w₂,···,w_n 作为叶子结点的权值，构造出一棵最优二叉树，然后将树中每个结点的左分支标上 0，右分支标上1，则每个叶子结点代表的字符的编码就是从根到叶子的路径上的0、1组成的串。
??例如，设有字符集{a,b,c,d,e}及对应的权值集合{0.30,0.25,0.15,0.22,0.08}，按照构造最优二叉树的哈夫曼方法：先取字符 c和e所对应的结点构造一棵二叉树（根结点的权值为c和e的权值之和），然后与 d 对应的结点分别作为左、右子树构造二叉树，之后选a 和b所对应的结点作为左、右子树构造二叉树，最后得到的最优二叉树 (哈夫曼树)如下图所示。其中，字符a的编码为 00，字符b、c、d、e的编码分别为 01、100、11、101。

??译码时就从树根开始，若编码序列中当前编码为 0，则进入当前结点的左子树；为1 则进入右子树，到达叶子时一个字符就翻译出来了，然后再从树根开始重复上述过程，直到编码序列结束。例如，若编码序列101110000100 对应的字符编码采用上图所示的树进行构造，则可翻译出字符序列"edaac"。
??【函数】根据给定的哈夫曼树，从每个叶子结点出发追溯到树根，逆向找出最优二叉树中叶子结点的编码。

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC,int n)
/*n个叶子结点在哈夫曼树HT中的下标为 1~n，第i(l≤i≤n)个叶子的编码存放HC[i]中*/
{
	char *cd; 
	int i, start, c, f;
	if(n <= 1) return;
	cd =(char *)malloc(n*sizeof(char));
	cd[n-1]='\0';
	for(i= l; i<= n; 计+){
		start = n-l;
		for(c = i,f= HT[i],parent; f!=0; c=f,f=HT[f].parent)
			if (HT[f].lchild == c) cd[--start] = '0';
			else cd[--start]='1';
		HC[i] =(char*)malloc((n-start)*sizeof(char));
		strcpy(HC[il,&cd[start]);
	}/*for*/
	free(cd);
}/*HuffmanCoding*/

??利用哈夫曼树译码的过程为：从根结点出发，按二进制位串中的0和1确定是进入左分支还是右分支，当到达叶子结点时译出一个字符。若位串未结束，则回到根结点继续上述译码过程，直到位串结束。
??【函数】用最优二又树进行译码

void Decoding(HuffmanTree HT,int n,char *buf) 
/*利用具有n个叶子结点的最优二叉树(存储在数组 HT 中) 进行译码，叶子的下标为 1~n*/
/*buff 指向二进制位串编码序列*/
{
	int p=2*n-1;
	while (*buff){
		if((*buff) == '0') p = HT[p].lchild;		/*进入左分支*/
		else p = HT[p].rchild;						/*进入右分支*/
		if(HT[p].lchild==0 && HT[p].rchild==0){		/*到达一个叶子结点*/
			printf("%c", HT[p].ch);
			p=2*n-1;								/*回到树根*/
		}/*if*/
		buff++;
	}/*while*/
}/*Decoding*/