huffmantree.txt

数据结构——哈夫曼树的生成

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
struct BTreeNode
{ ElemType data;
struct BTreeNode* left;
struct BTreeNode* right;
};

void printBTree1(struct BTreeNode* BT)
         /*输出元素为整型的二叉树的广义表表示*/
{
  /*树为空时自然结束递归，否则执行以下操作*/
   if(BT!=NULL)
{
    /*输出根结点的值*/
      printf("%d",BT->data);
    /*输出左、右子树*/
if (BT->left!=NULL||BT->right!=NULL)
{
      printf("(");                                /*输出左括号*/
      printBTree1(BT->left);                      /*输出左子树*/
      if(BT->right!=NULL) printf(",");           /*若右子树不为空则输出逗号为分隔符*/
      printBTree1(BT->right);                     /*输出右子数*/
      printf(")");                                /*输出右括号*/
      }
     }
    }

/*根据数组a中的n个权值建立一个哈夫曼树，返回树根指针*/
 struct BTreeNode* CreateHuffman(ElemType a[],int n)
  /*根据数组a中n个权值建立一个哈夫曼树，返回树根指针*/
{
  int  i,j;
  struct BTreeNode **b,*q;
/*动态分配一个由b指向的指针树组*/
 b=malloc(n*sizeof(struct BTreeNode *));
/*初始化b指针树组，使每个指针树元素指向a树组中对应元素的结点*/
  for(i=0; i<n; i++)
  {
      b[i]=malloc(sizeof(struct BTreeNode));
      b[i]->data=a[i];b[i]->left=b[i]->right=NULL;
  }
/*进行n-1次循环建立哈夫曼树*/
  for(i=1; i<n; i++)
  {
  /*用k1表示森林中具有最小权值的树根结点的下标*/
  /*用k2表示森林中具有次最小权值的树根结点的下标*/
   int  k1=-1,k2;
  /*让k1初始指向森林中第一棵树，k2指向森林中第二棵树*/
    for(j=0;j<n;j++)
    {
		if(b[j]!=NULL && k1==-1) { k1=j;continue;}
		if(b[j]!=NULL) { k2=j;break;}
   }
  /*从当前森林中求出最小权值树和次最小权值树*/
   for(j=k2;j<n;j++)
   {
       if(b[j]!=NULL)
       {
		   if(b[j]->data<b[k1]->data) 
		   {k2=k1;k1=j;}
	       else if( b[j]->data< b[k2]->data) k2=j;
      }
  }
 /*由最小权值树和次最小权值树建立一棵新树，q指向树根结点*/
    q=malloc(sizeof(struct BTreeNode));
    q->data=b[k1]->data+b[k2]->data;
    q->left=b[k1]; q->right=b[k2];
 /*将指向新上的指针赋给b指针数组中k1位置，k2位置置为空*/
   b[k1]=q;b[k2]=NULL;
  }
 /*删除动态建立的数组b*/
   free(b);
 /*返回整个哈夫曼树的树根指针*/
return q;
}



/*根据FBT指针所指向的哈夫曼树求出带权路径长度，len初值为0*/
 ElemType WeightPathLength(struct BTreeNode* FBT,int  len)
 /*根据FBT指针所指向的哈夫曼树求出带权路径的长度，len的初值为0*/
{
 if(FBT==NULL) return 0; /*空树则返回0*/
 else{
/*访问到叶子结点时返回该结点的带权路径长度，其中参值len保存当前被访问结点的路径长度*/
if(FBT->left==NULL && FBT->right==NULL)
{return FBT->data*len;
}
/*访问到非叶子结点时进行递归调用，返回左、右子树的带权路径长度之和，向下深入一层时len值增1*/
else{
  return WeightPathLength(FBT->left,len+1)+
         WeightPathLength(FBT->right,len+1);

}
}
}


/*根据FBT所指向的哈夫曼树输出每个叶子的编码，len初值为0*/
 void HuffManCoding(struct BTreeNode* FBT,int  len)
    /*根据FBT所指向的哈夫曼树输出每个叶子的编码，len初值为0*/
{
    /*定义一个静态数组a，保存每个叶子编码，数组的长度要至少等于哈夫曼树的深度减1*/
 static int a[10];
 if(FBT!=NULL)  {
 /*访问到叶子结点时输出其保存在数组a中的0和1序列编号*/
if(FBT->left==NULL && FBT->right==NULL)
{
 int i;
 printf("结点权值为%d的编码：",FBT->data);
 for(i=0;i<len;i++)printf("%d",a[i]);
 printf("\n");
}
/*访问到非叶子结点时分别向左、右子子树递归调用，并把分枝上的0、1编码保存到数组a的对应元素中，向下深入一层时len值增1*/
 else {
  a[len]=0; HuffManCoding(FBT->left,len+1);
  a[len]=1; HuffManCoding(FBT->right,len+1);
    }
   }
  }



void main()
  {
    int  n,i;
    ElemType* a;
    struct BTreeNode* fbt;
/*输入哈夫曼树中叶子结点数*/
    printf("从键盘输入待构造的哈夫曼树中带叶子结点数n:");
    while(1) {
	scanf("%d",&n);
	if(n>1) break; else printf("重输n值:");
   }
   /*用数组a保存从键盘输入的n个叶子结点的权值*/
    a=malloc(n*sizeof(ElemType));
    printf("从键盘输入%d个整数作为权值:",n);
    for(i=0; i<n;i++)
        scanf("%d",&a[i]);
  /*根据数组a建立哈夫曼树*/
   fbt=CreateHuffman(a,n);
/*以广义表形式输出哈夫曼树*/
  printf("广义表形式的哈夫曼树：");
  printBTree1(fbt); /*用于输出元素为整型的二叉树*/
  printf("\n");
  /*输出哈夫曼树的权值，即带权路径长度*/
   printf("哈夫曼树的权:");
   printf("%d\n",WeightPathLength(fbt,0));
/*输出哈夫曼编码，即每个叶子结点所对应的0，1序列*/
   printf("树中每个叶子的哈夫曼编码：\n");
    HuffManCoding(fbt,0);
}