哈夫曼树的构造方法与原理

#include<stdlib.h>

#define MAXSIZE 30/*自定义哈夫曼的最大个数*/

typedef struct
{
int weight;/*结点的权值*/
int parent;/*结点的双亲*/
int lchild;/*结点的左孩子*/
int rchild;/*结点的右孩子*/
int flag;/*是否用过的标志*/
}HufmTree;

int p1,p2;/*定义全局下标数字，用于Select（）函数返回当前哈夫曼树中最小
两个未用的结点/森林的下标*/
void CreatHuffman(HufmTree tree[] ,int n );/*构造哈夫曼树函数*/
void Select(HufmTree tree[] ,int i );/*选择最小两个森林的函数*/
void DisplayTree(HufmTree tree[],int Number);/*输出哈夫曼树函数*/

void main()
{
int InputNumber;/*输入森林结点的个数*/

printf("******本程序用于演示哈夫曼树的构造结果*****\n");
HufmTree mytree[MAXSIZE];/*声名一个棵哈夫曼树*/

printf("请输入结点个数：\n");
scanf("%d",&InputNumber);

CreatHuffman( mytree,InputNumber );//构造哈夫曼树
DisplayTree(mytree,InputNumber);//输出哈夫曼树
}

/*--------------------------------------------
*函数功能：构造哈夫曼树
*函数参数：自定义构造体，结构体数组
*函数返回值：没有
--------------------------------------------*/
void CreatHuffman(HufmTree tree[] ,int n )
{
int i,m;
if(n<=1)/*森林个数小于或等于一退出*/
{
return;
}

m=2*n;/*所建哈夫曼树最后结点的最大个数-1*/

for(i=1;i<m;i++)/*初使化所在结点*/
{
  tree[i].parent=0;
  tree[i].lchild=0;
  tree[i].rchild=0;
  tree[i].weight=0;
  tree[i].flag=0;
}

printf("请输入结点的数值\n");/*输入有权值的结点*/
for(i=1;i<=n;i++)
{
scanf("%d",&tree[i].weight);
}

for(i=n+1;i<m;i++)/*增加N-1个新的结点*/
{
  Select(tree ,i-1);/*选出当前森林中的最小两个紧最小权值的结点的下标*/
  tree[p1].parent=i;/*构造新的结点，并赋值*/
  tree[p1].flag=1;
  tree[p2].parent=i;
  tree[p2].flag=1;
  tree[i].lchild=p1;
  tree[i].rchild=p2;
  tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}

/*--------------------------------------------
*函数功能：选出当前森林中的最小两个紧最小权值的结点的下标
*函数参数：参数1 自定义构造体，结构体数组。
* 参数2 当前森林结点的个数
*函数返回值：没有
--------------------------------------------*/
void Select(HufmTree tree[] ,int number )
{
int MinValue1;/*最小值*/
int MinValue2;/*第二小值*/

for(int i=1;tree[i].flag!=0;i++)/*找到前中tree[i]没有个的第一个结点*/
{ /*找到森林中的一个结点*/
}
MinValue1=tree[i].weight;/*把找到的结点当做最小的结点*/
p1=i;/*最小值结点的下标值*/

for(int j=i+1;j<=number;j++)/*与前中tree[i]中后面的结点比较*/
{
  if((tree[j].flag!=1)&&(MinValue1>tree[j].weight))/*跳过于用过的结点（用过后不是森*/
  {                                                /*林中的结点）*/
   MinValue1=tree[j].weight;/*如果后面森林的结点值比MinValue1小*/
         p1=j;                    /*P1就指向它*/
  }
}

tree[p1].flag=1;/*把tree[p1]从森林中去掉，它已经用过*/
/*也为了p1 p2 不为同一个值*/
for( i=1;tree[i].flag!=0;i++)/*找到前中tree[i]没有个的第一个结点*/
{ /*找到森林中的一个结点*/
}
MinValue2=tree[i].weight;/*把找到的结点当做最小的结点*/
p2=i;/*第二小值结点的下标值*/

for(j=i+1;j<=number;j++)
{
  if((tree[j].flag!=1)&&(MinValue2>tree[j].weight))/*跳过于用过的结点（用过后不是森*/
  {                                                /*林中的结点）*/
   MinValue2=tree[j].weight;/*如果后面森林的结点值比MinValue1小*/
   p2=j;                    /*P1就指向它*/
  }
}
}
/*--------------------------------------------
*函数功能：输出哈夫曼树
*函数参数：参数1 自定义构造体，结构体数组。
*          参数2 输入结点的个数
*函数返回值：没有
--------------------------------------------*/
void DisplayTree(HufmTree tree[],int Number)
{
for(int i=1;i<2*Number;i++)
{
  printf("%5d",tree[i].weight);
}

printf("\n");

for(i=1;i<2*Number;i++)
{
  printf("HufmTree[%2d].parent=%3d\n",i,tree[i].parent);//输出当前元素的parent值
  printf("HufmTree[%2d].weight=%3d\n",i,tree[i].weight);//输出当前元素的weight值
  printf("HufmTree[%2d].lchild=%3d\n",i,tree[i].lchild);//输出当前元素的lchild值
  printf("HufmTree[%2d].rchild=%3d\n\n",i,tree[i].rchild);//输出当前元素的rchild值
}
}