采用链式存储结构构造哈夫曼树

作者：颜清国

/************************************************************************
*
* 文件名：HFtree.c
*
* 文件描述：本程序给出哈夫曼树的链式构造法和哈夫曼的编码
*           在turboc 2.0 调试通过,在其他编译环境下请把
*           gotoxy和getch两个函数重写
*
* 创建人： 颜清国   2006年5月4日
* 说明：
*            采用链式存储结构构造哈夫曼树，可以很方便的将树的各种操作加
*            到哈夫曼树上来，包括其编码
************************************************************************/

#include "stdio.h"
#include "stdlib.h"
#include "conio.h"

#define LEN sizeof(HFtree) /*HFtree结构体大小*/

/*哈夫曼树结构体*/
typedef struct tagHFtree
{
 char data;            /*结点数据,以后用到*/
 double weight;         /*结点的权重*/
 struct tagHFtree* parent; /*双亲结点*/
 struct tagHFtree* lchild; /*左孩子*/
 struct tagHFtree* rchild; /*右孩子*/
 struct tagHFtree* next;    /*指向下一个结点*/
}HFtree;

/*哈夫曼编码结构体*/
struct tagHFcode
{
char data;           /*结点数据*/
double weight;       /*结点的权重*/    
int code[20];            /*存放编码*/
int top;             /*编码的位数*/
};

/***********************************************
创建哈夫曼树核心部分
************************************************/
void Create(HFtree**head)
{
 HFtree*lp,*temp,*lchild,*rchild;
 while((*head)->next->next!=NULL)
 {
  lchild=rchild=(*head);   /*每次从头开始查找，这里(*head)的weight没用，*/
                                         /*刚好用来放左右孩子*/          
               temp=(*head)->next;    /*最初的的weight*/
  lchild->weight=rchild->weight=3.14e+38;  /*重新找时每次将左右孩子的weight置为最大*/
  lp=(HFtree*)malloc(LEN);
               lp->parent=NULL;
  while(temp!=NULL)            /*查找最小的作为左孩子*/
  {
   if(lchild->weight > temp->weight)
   {
    lchild=temp;
   }
   temp=temp->next;
  }
  temp=(*head)->next;          /*重新定位到(*head)->next*/
  while(temp!=NULL)            /*查找次小的作为右孩子*/
  {                 /*注意这里不要用temp->weight!=lchild->weigh*/
   if(rchild->weight > temp->weight && temp!=lchild)
   {
    rchild=temp;
   }
   temp=temp->next;
  }
  
  lp->lchild=lchild;                        /*对LP及其左右孩子附值*/
  lp->rchild=rchild;                       
  lchild->parent = rchild->parent =lp;
  lp->weight=lchild->weight + rchild->weight;  /*将左右孩子的权值相加*/
  lp->next=(*head)->next;                /*将LP插到表头*/
  (*head)->next=lp;                      /*每次让(*head)->next指向新加进来的结点*/
  temp=lp;                               /*将lp和temp两个指针重新定位，用来遍历链表*/
  lp=lp->next;
  while(lp!=NULL)                        /*将左右孩子从待创建的链表系列中删除*/
  {
   if(lp==lchild || lp==rchild)
   {
    temp->next=lp->next;
    lp->next=NULL;
   }
   else
    temp=lp;
   lp=temp->next;
   
  }
 }
}


/***********************************************
创建哈夫曼树
************************************************/
void CreateHFtree(double nodewei[],int n,HFtree**head)
{
 int i=0;
 HFtree*lp=(HFtree*)malloc(LEN),*rear;
 (*head)=(HFtree*)malloc(LEN);
       (*head)->parent=NULL;
 (*head)->next=rear=lp;                                 /*head头结点，保证指向剩余的结点链*/
 lp->parent=lp->lchild=lp->rchild=lp->next=NULL;
 while(iweight=nodewei[i++];
  rear->next=lp;                          /*第一次REAR指向自身*/
  rear=lp;
  lp=(HFtree*)malloc(LEN);
  lp->parent=lp->lchild=lp->rchild=lp->next=NULL;
 }
 free(lp);                                    /*释放最后一个结点*/
 Create(head);                               /*创建一棵树，树的头结点为(*HEAD)->next*/
}

/*************************************************
由先序遍历求出哈夫曼树求出哈夫曼编码
**************************************************/
void HFcoding(HFtree*root,HFtree*temp,struct tagHFcode HFcode[],int*leaftop)
{
if(root!=NULL)
{
 if(root->lchild==NULL && root->rchild==NULL)    /*是叶子结点，求得编码*/
 {
  temp=root;
  HFcode[(*leaftop)].top=0;
  HFcode[(*leaftop)].weight=root->weight;
  HFcode[(*leaftop)].data=root->data;
  while(temp->parent!=NULL)
  {
   if(temp->parent->lchild==temp)                  
   HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;
   else
   HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;
   HFcode[(*leaftop)].top++;
   temp=temp->parent;
  }
  (*leaftop)++;
 }
 HFcoding(root->lchild,temp,HFcode,leaftop);
 HFcoding(root->rchild,temp,HFcode,leaftop);
}
}

/***********************************************
输出求得的哈夫曼编码
************************************************/
void OutCoding(struct tagHFcode HFcode[],int leaftop)
{
 int i=0,j=0;
          for(;i          {
                 printf("%.1f :",HFcode[i].weight);
                 j=HFcode[i].top-1;
                 while(j>=0 )
                 {
                  printf("%d",HFcode[i].code[j]);
                  j--;
                 }
                 printf("\n");
          }

}
/********************************************
用括号表示法输出树
**********************************************/
void OutTree(HFtree *root)
{
 if(root != NULL)
 {
  printf("%.1f",root->weight);       /*先输出根结点*/
  if(root->lchild != NULL || root->rchild != NULL)
  {
   printf("(");
   OutTree(root->lchild);        /*处理左子树*/
   if(root->rchild != NULL)
   {
    printf(",");
   }
   OutTree(root->rchild);         /*处理右子树*/
   printf(")");
  }
 }
}

/*****************************************************************
用树形表示法输出树
******************************************************************/
void DispTree(HFtree *root,int x,int y,int n)     /*n用来控制第一层树的高度*/
{
int i=0;
if(root !=NULL)
 {
   gotoxy(x,y);                               /*到相应结点输出*/
   printf("%.1f",root->weight);
   if(root->lchild != NULL)                  /*处理左子树，这里只有第一次N为可变的，*/
   {
      i=1;                                   /*为的是能够输出整棵树，而不会被覆盖，*/
      while(ilchild,x-n,y+n,2);       /*递归处理左子树*/
    }
    if(root->rchild != NULL)
   {
      i=1;
      while(irchild,x+n,y+n,2);       /*递归处理右子树*/
    }
  }
}

/*****************************************************************
主函数入口
******************************************************************/
void main()
{
       double nodewei[20];
       struct tagHFcode HFcode[20];
       int leaftop=0,i=0;
       HFtree*temp=NULL;
 HFtree*head;
       textbackground(1);
       textcolor(2);
       clrscr();
       printf("the HFtree and HFcoding demo\r\n");
       printf("Input the leafnode weight:");
       scanf("%lf",&nodewei[i]);
       while(nodewei[i++]!=0.0)/*接收数据，以0结尾*/
               scanf("%lf",&nodewei[i]);
       CreateHFtree(nodewei,i-1,&head);  /*根据接收的数据创建*/
       printf("HFtree:");
 OutTree(head->next);              /*输出哈夫曼树括号表示法*/
       HFcoding(head->next,temp,HFcode,&leaftop);  /*根据哈夫曼树，求出哈夫曼编码*/
       printf("\nthe HFcoding is:\n");
       OutCoding(HFcode,leaftop);        /*输出哈夫曼编码*/
       DispTree(head->next,30,10,6);     /*用树形表示法输出树*/
       getch();
}