赫夫曼树

赫夫曼树(Huffman)，又称最优树，是一类带权路径长度最短的树。
路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。
树的路径长度：是从树根到每一个结点的路径长度之和。
树的带权路径长度：所有叶子节点的带权路径长度之和。

构造赫夫曼树的算法：
1）根据给定的n个权值{w1,w2,…,w3}构成n棵二叉树的集合F={T1,T2,…Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。
2）在F中选取两个根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为其左右树上根节点的权值之和。
3）在F中删除这两棵树，同时将新得到的二叉树加入F中。
4）重复（2）（3），直到F只含一棵树为止。这棵树便是赫夫曼树。

算法实现：

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

typedef struct{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}NTNode,*HuffmanTree;

typedef char * * HuffmanCode;
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n);
void Select(HuffmanTree &HT,int i);

int s1,s2;

int main(){
	HuffmanTree HT;
	HuffmanCode HC;
	int *w,n,i;
	printf("输入待编码的个数\n");
	scanf("%d",&n);

	w = (int*) malloc(n*sizeof(int));

	for(i = 0;i < n;i ++){
		scanf("%d",&w[i]);
	}
	HuffmanCoding(HT,HC,w,n);
	for(i = 1;i <= n;i ++){
		printf("%d(%d):%s\n",i,w[i-1],HC[i]);
	}
	return 0;
}


void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
	if(n <= 1)
		return;
	int m = 2*n-1;
	/*分配存储空间*/
	HT =(HuffmanTree)malloc((m+1) *sizeof(NTNode));
	HuffmanTree p = HT+1;

	for (int i = 1; i <= n; ++i,++p,++w)
	{
		(*p).weight = (*w);
		(*p).parent = 0;
		(*p).lchild = 0;
		(*p).rchild = 0;
	}
	for(int i = n+1; i<=m;++i){
		(*p).weight = 0;
		(*p).parent = 0;
		(*p).lchild = 0;
		(*p).rchild = 0;
	}
	for(int i = n+1;i<=m;++i){
		Select(HT,i-1);
		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;
	}

	/*从叶子到根逆向求每个字符的赫夫曼编码*/
/*	HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
	char* cd = (char *)malloc(n*sizeof(char));
	cd[n-1] = '\0';
	int start;
	for(int i = 1;i <= n;++i){
		start = n-1;
		for(int 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));
		printf("%d\n",n-start);
		strcpy(HC[i],&cd[start]);
	}
	free(cd);
*/	
	/*无栈非递归遍历赫夫曼树，求赫夫曼编码*/
	HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
	int p1 = m;
	int cdlen = 0;
	char * cd = (char *)malloc(n * sizeof(char));
	for (int i = 1; i <=m; ++i)
	{
		HT[i].weight = 0;
	}
	while(p1){
		if(HT[p1].weight == 0){
			HT[p1].weight = 1;
			if(HT[p1].lchild != 0){
				p1 = HT[p1].lchild;
				cd[cdlen++] = '0';
			}else if(HT[p1].rchild == 0 ){
				HC[p1] = (char *) malloc((cdlen+1) * sizeof(char));
				cd[cdlen] = '\0';
				strcpy(HC[p1],cd);
			}
		}else if(HT[p1].weight == 1){
			HT[p1].weight = 2;
			if(HT[p1].rchild !=0){
				p1=HT[p1].rchild;
				cd[cdlen++] = '1';
			}
		}else{
				HT[p1].weight  = 0;
				p1 = HT[p1].parent;
				--cdlen;
		}
	}
}

void Select(HuffmanTree &HT,int n){
	int i ,j;
	for(i = 1;i <= n;i++){
		if(!HT[i].parent){
			s1 = i;
			break;
		}
	}
	for( j = i+1;j<=n;j++){
		if(!HT[j].parent){
			s2 = j;
			break;
		}
	}
	for(i = 1;i <=n;i++){
		if((HT[s1].weight > HT[i].weight )&&(!HT[i].parent) &&(s2 != i)){
			s1 = i;
		}
	}
	for(j = 1; j<=n;j++){
		if( (HT[s2].weight > HT[j].weight )&&(!HT[j].parent) &&(s1 != j)){
			s2 = j;
		}
	}
	//printf("%d %d\n",s1,s2);
}