在最近的自學(xué)數(shù)據(jù)結(jié)構(gòu)的過程中,為加深樹的理解,碼了一個(gè)二叉樹編碼器,請多多指教:
#include
#define MAXBIT100
//最大子樹
#define MAXVALUE10000
//最大值
#define MAXLEAF30
//最大編碼數(shù)
#define MAXNODEMAXLEAF*2 -1
//最大節(jié)點(diǎn)數(shù)
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType;/*編碼結(jié)構(gòu)體*/
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
} HNodeType;/*結(jié)點(diǎn)結(jié)構(gòu)體*/
/*構(gòu)造哈夫曼樹*/
void HuffmanTree(HNodeType HuffNode[MAXNODE],int n)
{
/* i屁置、j：循環(huán)變量，m1仁连、m2：構(gòu)造哈夫曼樹不同過程中兩個(gè)最小權(quán)值結(jié)點(diǎn)的權(quán)值蓝角，
x1、x2：構(gòu)造哈夫曼樹不同過程中兩個(gè)最小權(quán)值結(jié)點(diǎn)在數(shù)組中的序號饭冬。*/
int i,j,m1,m2,x1,x2;
/*初始化存放哈夫曼樹數(shù)組HuffNode[]中的結(jié)點(diǎn)*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight = 0;
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].lchild =-1;
} /* end for */
/*輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值*/
for(i=0;i
{
printf("Please input weight of leaf node %d: \n",i);
scanf("%d",&HuffNode[i].weight);
} /* end for */
/*循環(huán)構(gòu)造Huffman樹*/
for(i=0;i
{
m1=m2=MAXVALUE;/* m1使鹅、m2中存放兩個(gè)無父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個(gè)結(jié)點(diǎn)*/
x1=x2=0;
/*找出所有結(jié)點(diǎn)中權(quán)值最小、無父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)昌抠，并合并之為一顆二叉樹*/
for(j=0;j
{
if(HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} /* end for */
/*設(shè)置找到的兩個(gè)子結(jié)點(diǎn)x1患朱、x2的父結(jié)點(diǎn)信息*/
HuffNode[x1].parent= n+i;
HuffNode[x2].parent= n+i;
HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;
printf("x1.weight and x2.weight in round %d: %d,%d\n",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用于測試*/
printf("\n");
} /* end for */
} /* end HuffmanTree */
int main(void)
{
HNodeType HuffNode[MAXNODE];/*定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu)體數(shù)組*/
HCodeType HuffCode[MAXLEAF],cd;/*定義一個(gè)編碼結(jié)構(gòu)體數(shù)組，同時(shí)定義一個(gè)臨時(shí)變量來存放求解編碼時(shí)的信息*/
int i,j,c,p,n;
printf("Please input n:\n");
scanf("%d",&n);
HuffmanTree(HuffNode,n);
for(i=0;i < n;i++)
{
cd.start = n-1;
c = i;
p = HuffNode[c].parent;
while(p != -1)/*父結(jié)點(diǎn)存在*/
{
if(HuffNode[p].lchild == c)
cd.bit[cd.start]= 0;
else
cd.bit[cd.start]= 1;
cd.start--;/*求編碼的低一位*/
c=p;
p=HuffNode[c].parent;/*設(shè)置下一循環(huán)條件*/
} /* end while */
/*保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位*/
for(j=cd.start+1;j
{ HuffCode[i].bit[j]= cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */
/*輸出已保存好的所有存在編碼的哈夫曼編碼*/
for(i=0;i
{
printf("%d 's Huffman code is: ",i);
for(j=HuffCode[i].start+1;j < n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("\n");
}
getchar();
return 0;
}
