频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
哈夫曼树的代码实现
2013-05-14 09:07:32           
收藏   我要投稿

定义
哈夫曼树,又称最优树,是一类带权路径长度最短的树。

树的带权路径长度,是树中所有叶子 节点的带权路径长度之和。通常记做WPL=W1*L1+W2*L2+...+Wn*Ln。

例如:

 

\\

节点ABCDE的权值分别为:1,2,4,5,6。对于图1,WPL=4*3+2*3+1*3+5*3+6*1=42。对于图2,WPL=1*3+2*3+4*2+5*2+6*2=39。以上节点还可以列出其他的树,并计算WPL,可以看出,图2的WPL值是最小的,这颗树即称为最优二叉树或哈夫曼树。

如何建立二叉树呢?
1、将所有节点看成独立的树,且左右子树都为空,没有父节点;

2、挑选两棵根节点权值最小的没有父节点的树,生成一个节点作为它们的父节点,父节点的权值等于他们的权值之和;

3、重复第2步,直到最后变成一棵树。

比如以上ABCDE节点,首先选择A和B形成的父节点(且记为A‘)权值为3,接下来从权值为3,4,5,6中选取,当然就是选3,4,也即A‘和C节点,形成父节点(且记为C’)权值为7,接下来从权值5,6,7中选取最小的两个,当然是5,6.也即是D和E,形成父节点(且记为D‘)的权值为11,最后将D’和C‘形成父节点即为最后的根节点。哈夫曼树就建成了。

如何构建哈夫曼编码?
从叶节点往根扫描,若为左子树则标记为0,为右子树则标记为1。如图2,A的编码即为:000,B的编码100,等等。

具体代码实现如下:


[cpp]
//huffmanCoding.c  
#include <stdio.h>  
#include <limits.h>  
#include <string.h>  
#include <stdlib.h>  
#define N 6  
 
typedef struct huffNode 

    unsigned int weight;   //权重  
    unsigned int lchild,rchild,parent;  //左右子节点和父节点  
}HTNode,*HuffTree; 
typedef char **HuffCode; 
 
//找出数组中无父节点且权值最小的两个节点下标,分别用s1和s2保存  
void select(const HuffTree &HT,int n,int &s1,int &s2); 
//HT:哈夫曼树,HC:哈夫曼编码,w:构造哈夫曼树节点的权值,n:构造哈夫曼树节点的个数  
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n); 
 
 
int main() 

    int i; 
    char key[N] = {'0','A','B','C','D','E'};//第0个元素保留不用  
    int w[N] = {0,1,2,4,5,6}; //第0个元素保留不用  
    HuffTree HT; 
    HuffCode HC; 
    HuffmanCode(HT,HC,w,N - 1); 
    for ( i = 1; i < N; i++ ) 
    printf("%c:%s\n",key[i],HC[i]);   
   
    printf("\n");     
    return 0; 

 
 
 
 
//找出数组中权值最小的两个节点下标,分别用s1和s2保存  
void select(const HuffTree &HT,int n,int &s1,int &s2) 

    int i; 
    s1 = s2 = 0;  
    int min1 = INT_MAX;//最小值,INT_MAX在<limits.h>中定义的  
    int min2 = INT_MAX;//次小值  
 
    for ( i = 1; i <= n; ++i ) 
    { 
    if ( HT[i].parent == 0 ) 
    {//筛选没有父节点的最小和次小权值下标  
        if ( HT[i].weight < min1 ) 
        {//如果比最小值小  
        min2 = min1; 
        s2 = s1; 
        min1 = HT[i].weight; 
        s1 = i; 
        } 
        else if ( (HT[i].weight >= min1) && (HT[i].weight < min2) ) 
        {//如果大于等于最小值,且小于次小值  
        min2 = HT[i].weight; 
        s2 = i; 
        } 
        else 
        {//如果大于次小值,则什么都不做  
        ; 
        } 
    } 
    } 

 
//HT:哈夫曼树,HC:哈夫曼编码,w:构造哈夫曼树节点的权值,n:构造哈夫曼树节点的个数  
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n) 

    int s1; 
    int s2; 
    int m = 2 * n - 1;       //容易知道n个节点构造的哈夫曼树是2n-1个节点  
    int i,c,f,j; 
    char *code;  //暂存编码的  
    HT = (HuffTree)malloc((m+1)*sizeof(HTNode));  //0单元未使用  
     
 
    for ( i = 1; i <= n; i++ ) 
        HT[i] = {w[i],0,0,0};//初始化前n个节点(构造哈夫曼树的原始节点)  
     
    for ( i = n + 1; i <= m; i++ ) 
    HT[i] = {0,0,0,0};  //初始化后n-1个节点  
 
    //构建哈夫曼树  
    for ( i = n + 1; i <= m; i++) 
    { 
    select(HT,i-1,s1,s2);//找出前i-1个节点中权值最小的节点下标  
    HT[s1].parent = i; 
    HT[s2].parent = i; 
    HT[i].lchild = s1; 
    HT[i].rchild = s2; 
    HT[i].weight = HT[s1].weight + HT[s2].weight; 
    } 
    //哈夫曼编码  
    HC = (char **)malloc((n)*sizeof(char *)); 
    //暂存编码  
    code = (char *)malloc(n*sizeof(char));//使用了第0单元  
    for ( i = 1; i <= n; i++ ) 
    { 
    for ( c = i, f = HT[c].parent, j = 0; f != 0; c = HT[c].parent, f = HT[c].parent,  j++ ) 
    {//从叶子扫描到根  
        if ( HT[f].lchild == c )  
        { 
        code[j] = '0'; 
        } 
        else if(HT[f].rchild == c) 
        { 
        code[j] = '1'; 
        } 
        else 
        {//否则什么也不做  
        ; 
        } 
    } 
    code[j] = '\0'; 
    HC[i] = (char *)malloc(strlen(code)*sizeof(char)); 
    strcpy(HC[i],code); 
    } 
     

//huffmanCoding.c
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#define N 6

typedef struct huffNode
{
    unsigned int weight;   //权重
    unsigned int lchild,rchild,parent;  //左右子节点和父节点
}HTNode,*HuffTree;
typedef char **HuffCode;

//找出数组中无父节点且权值最小的两个节点下标,分别用s1和s2保存
void select(const HuffTree &HT,int n,int &s1,int &s2);
//HT:哈夫曼树,HC:哈夫曼编码,w:构造哈夫曼树节点的权值,n:构造哈夫曼树节点的个数
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n);


int main()
{
    int i;
    char key[N] = {'0','A','B','C','D','E'};//第0个元素保留不用
    int w[N] = {0,1,2,4,5,6}; //第0个元素保留不用
    HuffTree HT;
    HuffCode HC;
    HuffmanCode(HT,HC,w,N - 1);
    for ( i = 1; i < N; i++ )
 printf("%c:%s\n",key[i],HC[i]); 
 
    printf("\n");   
    return 0;
}

 


//找出数组中权值最小的两个节点下标,分别用s1和s2保存
void select(const HuffTree &HT,int n,int &s1,int &s2)
{
    int i;
    s1 = s2 = 0;
    int min1 = INT_MAX;//最小值,INT_MAX在<limits.h>中定义的
    int min2 = INT_MAX;//次小值

    for ( i = 1; i <= n; ++i )
    {
 if ( HT[i].parent == 0 )
 {//筛选没有父节点的最小和次小权值下标
     if ( HT[i].weight < min1 )
     {//如果比最小值小
  min2 = min1;
   s2 = s1;
  min1 = HT[i].weight;
  s1 = i;
     }
     else if ( (HT[i].weight >= min1) && (HT[i].weight < min2) )
        {//如果大于等于最小值,且小于次小值
  min2 = HT[i].weight;
   s2 = i;
     }
     else
     {//如果大于次小值,则什么都不做
  ;
     }
 }
    }
}

//HT:哈夫曼树,HC:哈夫曼编码,w:构造哈夫曼树节点的权值,n:构造哈夫曼树节点的个数
void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n)
{
    int s1;
    int s2;
    int m = 2 * n - 1;       //容易知道n个节点构造的哈夫曼树是2n-1个节点
    int i,c,f,j;
    char *code;  //暂存编码的
    HT = (HuffTree)malloc((m+1)*sizeof(HTNode));  //0单元未使用
   

    for ( i = 1; i <= n; i++ )
        HT[i] = {w[i],0,0,0};//初始化前n个节点(构造哈夫曼树的原始节点)
   
    for ( i = n + 1; i <= m; i++ )
 HT[i] = {0,0,0,0};  //初始化后n-1个节点

    //构建哈夫曼树
    for ( i = n + 1; i <= m; i++)
    {
 select(HT,i-1,s1,s2);//找出前i-1个节点中权值最小的节点下标
 HT[s1].parent = i;
 HT[s2].parent = i;
 HT[i].lchild = s1;
 HT[i].rchild = s2;
 HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    //哈夫曼编码
    HC = (char **)malloc((n)*sizeof(char *));
    //暂存编码
    code = (char *)malloc(n*sizeof(char));//使用了第0单元
    for ( i = 1; i <= n; i++ )
    {
 for ( c = i, f = HT[c].parent, j = 0; f != 0; c = HT[c].parent, f = HT[c].parent,  j++ )
 {//从叶子扫描到根
     if ( HT[f].lchild == c )
     {
  code[j] = '0';
     }
     else if(HT[f].rchild == c)
     {
  code[j] = '1';
     }
      else
     {//否则什么也不做
  ;
     }
 }
 code[j] = '\0';
    HC[i] = (char *)malloc(strlen(code)*sizeof(char));
 strcpy(HC[i],code);
    }
   
}

 

 

运行结果:

 


 

\
点击复制链接 与好友分享!回本站首页
相关TAG标签 哈夫曼 代码
上一篇:判断给定的图是否是有向无环图
下一篇:二分搜索+DFS
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站