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");
	}

}