/*——————————————————————————————
*本程序关于哈夫曼树的构造的方法与原理
*编者：04 计本（2） LGW
*编写时间：06/05/24
*最后修改时间：06/05/25
*联系方式：QQ643560001 Email scholar_ii@163.com
-----------------------------------------------------------*/
#include<stdio.h>
#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值
}
}