建構哈夫曼樹算法的實作可以分為兩大部分。
(1)初始化:首先動态申請2n個單元;然後循環2n-1次,從1号單元開始,依次将1至2n-1所有單元中的雙親、左孩子、右孩子的下标都初始化為0;最後再循環n次,輸入前n個單元中葉子結點的權值。完成初始化的狀态圖為圖中的(a)。
(2)建立樹:循環n-1次,通過n-1次的選擇、删除與合并來建立哈夫曼樹。選擇是從目前森林中選擇雙親為0且權值最小的兩個樹根結點s1和s2;删除是指将結點s1和s2的雙親改為非0;合并就是将sl和s2的權值和作為一個新結點的權值依次存人到數組的第n+1之後的單元中,同時記錄這個新結點左孩子的下标為s1,右孩子的下标為s2。完成此步驟的狀态圖為圖中的(b)。
完整代碼如下:
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int weight;//結點的權值
int parent,lchild,rchild;//結點的雙親,左孩子,右孩子的下标
}HTNode,*HuffmanTree;//動态配置設定數組存儲哈夫曼樹
void InitTree(HuffmanTree &H,int &n)//初始化哈夫曼樹
{
int i,a;
printf("請輸入結點個數: ");
scanf("%d",&n);//結點個數
H = (HTNode*)malloc(sizeof(HTNode)*(2*n));//申請一個2*n的空間
for(i=0;i<2*n;i++)//利用循環對申請的空間進行初始化
H[i].weight = H[i].parent = H[i].lchild = H[i].rchild = 0;
printf("分别為: ");
for(i=0;i<n;i++)//利用循環對n個結點權值指派
{
scanf("%d",&a);
H[i+1].weight = a;
}
}
void Select(HuffmanTree H,int n,int &s1,int &s2)//選擇函數 ,輸入要循環的總次數n,并傳回其權值最小的兩個數的結點序号s1和s2
{
int i,//循環次數i
a,//權值指派變量
b;//結點序号指派變量
for(i=0;i<n;i++)//循環指派
{
if(H[i+1].parent == 0)//找出第一個parent是0的結點,對變量a,b進行指派
{
a = H[i+1].weight;
b = i+1;
break;//循環終止條件
}
}
for(i=0;i<n;i++)//利用循環找出最小值
{
if(a>H[i+1].weight && H[i+1].parent == 0)// parent為0的結點的中的最小值, 指派給a和b,b為序号
{
a = H[i+1].weight;
b = i+1;
}
}
s1 = b;
for(i=0;i<n;i++)
{
if(H[i+1].parent == 0 && (i+1)!= s1)//找出第一個parent是0且不是最小權值的結點,對變量a,b進行指派
{
a = H[i+1].weight;
b = i+1;
break;
}
}
for(i=0;i<n;i++)//利用循環找出除s1的最小值
{
if(a>H[i+1].weight && H[i+1].parent == 0 && (i+1)!=s1)
{
a = H[i+1].weight;
b = i+1;
}
}
s2 = b;
}
void CreateHuffmanTree(HuffmanTree &H,int n)//哈夫曼樹的建立
{
int s1,s2;//申請變量,友善接挑選函數傳回的值
int i;
for(i=n+1;i<2*n;i++)//通過n-1次的選擇,删除,合并來建構哈夫曼樹
{
Select(H,i-1,s1,s2);//選出最小的兩個數
H[s1].parent = i;
H[s2].parent = i;//得到新結點i,從森林中删除s1,s2,并将s1,s2的雙親域由0改成i
H[i].lchild = s1;
H[i].rchild = s2;//s1和s2分别作為i的左右孩子
H[i].weight = H[s1].weight+H[s2].weight;//i的權值為左右孩子的權值之和
}
}
void CreatHuffmanCode(HuffmanTree H,int n)//哈夫曼編碼的輸出,遞歸實作
{
if(H[n].parent == 0)//遞歸終止條件
return ;
CreatHuffmanCode(H,H[n].parent);//遞歸雙親結點
if(H[H[n].parent].lchild == n)//如果n的雙親的左孩子等于n,則輸出0,否則輸出1
printf("0");
else
printf("1");
}
//書上的例子:8個結點分别為 5 29 7 8 14 23 3 11
int main()
{
int n,i;
HuffmanTree H;
InitTree(H,n);//初始化
CreateHuffmanTree(H,n);//建構哈夫曼樹
for(i=1;i<2*n;i++)//利用循環分别列印權值,雙親,左孩子,右孩子
{
printf( "%d ",H[i].weight);
printf("%d ",H[i].parent);
printf("%d ",H[i].lchild);
printf("%d\n",H[i].rchild);
}
printf("哈夫曼編碼:\n");
for(i=1;i<=n;i++) //利用循環列印各個結點的哈夫曼編碼
{
printf("%d: ",i);
CreatHuffmanCode(H,i);//哈夫曼編碼
printf("\n");
}
return 0;
}
結果圖展示:
前兩行為輸入的資料。
(完)