haffman哈夫曼编码的实现

<span style="font-size:18px;">/*

  1.在一棵二叉树中，我们定义从A节点到B节点所经过的分支序列为从A节点到B节点的路径；
    定义从A节点到B节点所经过的分支个数为从A节点到B节点的路径长度。
	定义从二叉树的根节点到二叉树中全部叶节点的路径长度之和为该二叉树的路径长度。
  2.假设二叉树中的叶节点都带有权值，则能够把这个定义推广。设二叉树有n歌带权值的叶节点，定义从二叉树的
  根节点到二叉树中全部叶节点的路径长度与相应叶节点权值的乘积之和为该二叉树的带权路径长度。
  WPL=(wi*li)(i从1到n)
  3.我们把具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树
  4.哈夫曼树构造算法：
     (1):由给定的n个权值{w1,w2,w3,...,wn}构造n棵仅仅有根节点的二叉树，从而得到一个二叉树森林F={T1,T2,T3,....,TN}。
	 (2):在二叉树森林F中选取根节点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，
	     新的二叉手的根节点权值为左右子树根节点权值之和。
	 (3):从二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树增加到二叉树森林F中。
	 (4):反复步骤(2)(3)。当二叉树森林F中仅仅剩下一颗二叉树时。这棵二叉树就是所构造的哈夫曼树

  5.哈夫曼树能够用于解决最优化问题。比如电文的编码问题
*/

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MaxN 10//初始设定的最大结点个数
#define MaxValue 10000//初始设定的权值最大值
#define MaxBit 4//初始设定的最大编码位数
typedef struct{

	int weight;//权值
	int flag;//标记，是否已经增加到哈夫曼树中
	int parent;//双亲节点下标
	int leftChild;//左孩子下标
	int rightChile;//右孩子下标
}HaffNode;//哈夫曼树的结点构体

typedef struct{

	int bit[MaxN];//数组
	int start;//编码的起始下标
	int weight;//字符的权值
}Code;//哈夫曼编码的结构


//建立哈夫曼树
void Haffman(int weight[],int n,HaffNode haffTree[]){
//建立叶结点个数为n，权值数组为weight的哈夫曼树haffTree
	int i,j,m1,m2,x1,x2;
	//哈夫曼树的haffTree的初始化，n个叶节点的二叉树共同拥有2n-1个结点
	for(i=0;i<2*n-1;i++){
	
		if(i<n){
		
			haffTree[i].weight=weight[i];
		}else{
		
			haffTree[i].weight=0;
		}

		haffTree[i].parent=-1;
		haffTree[i].flag=0;
		haffTree[i].leftChild=-1;
		haffTree[i].rightChile=-1;

	}

	//构造哈夫曼树haffTree的n-1个非叶节点
	for(i=0;i<n-1;i++){
	
		m1=m2=MaxValue;
		x1=x2;
		for(j=0;j<n+i;j++){//找出权值最小和次小的子树
			if(haffTree[j].weight<m1&&haffTree[j].flag==0){
			//x1最小的下标，x2次小的下标，m1最小的权值，m2次小的权值
				//flag==0表示还没有增加到哈夫曼树
				m2=m1;
				x2=x1;
				m1=haffTree[j].weight;
				x1=j;
			}else if(haffTree[j].weight<m2&&haffTree[j].flag==0){
			
				m2=haffTree[j].weight;
				x2=j;
			}
		}
		//将找出的两棵权值最小和次小的子树合并为一棵
		haffTree[x1].parent=n+i;
        haffTree[x2].parent=n+i;
		haffTree[x1].flag=1;
		haffTree[x2].flag=1;
		haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
		haffTree[n+i].leftChild=x1;
		haffTree[n+i].rightChile=x2;
	}
}



void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]){

	//由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
	Code *cd=(Code *)malloc(sizeof(Code));
	int i,j,child,parent;
	//求n个叶结点的哈夫曼编码
	for(i=0;i<n;i++){
		cd->start=n-1;//不等长编码的最后一位为n-1
		cd->weight=haffTree[i].weight;//取得编码相应的权值
		child=i;
		parent=haffTree[child].parent;
		//由叶节点向上直到根结点
        while(parent!=-1){
			if(haffTree[parent].leftChild==child){
			
				cd->bit[cd->start]=0;//左孩子分支编码0
			}else{
			
				cd->bit[cd->start]=1;//右孩子分支编码1
			}
			cd->start--;
			child=parent;
			parent=haffTree[child].parent;
		}
		for(j=cd->start+1;j<n;j++){
		
			haffCode[i].bit[j]=cd->bit[j];//保存每一个叶节点的编码
		}
		haffCode[i].start=cd->start+1;//保存叶结点编码的起始位
		haffCode[i].weight=cd->weight;//保存编码相应的权值
	}
}




void main(){

	int i,j,n=4;
	int weight[]={1,3,5,7};
	HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n-1));
	Code *myHaffCode=(Code *)malloc(sizeof(Code)*n);
	if(n>MaxN){
	
		printf("给出的n越界。改动MaxN!!!\n");
		exit(1);
	}

	Haffman(weight,n,myHaffTree);
	HaffmanCode(myHaffTree,n,myHaffCode);
	//输出每一个叶节点的哈夫曼编码
	for(i=0;i<n;i++){
	
		printf("Weight=%d  Code=",myHaffCode[i].weight);
		for(j=myHaffCode[i].start;j<n;j++){
		
			printf("%d",myHaffCode[i].bit[j]);
		}
		printf("\n");
	}

}