哈夫曼树（HuffmanTree）详解

朱雀 2022-04-15 07:06 353阅读 0赞

**目录**

1.哈夫曼算法

2.举例说明，感性认识哈夫曼算法，根据上面的4步得出下表

3.结点结构体类型的定义

4.select函数的编写

5.哈夫曼树的创建及编码的创建

6.解码

7. 打印哈夫曼树和哈夫曼编码

8.完整代码

9.运行截图

--------------------

### 1.哈夫曼算法 ###

>  *  1.**根据给定的****n****个权值****\{w****1****,w****2****,...,****w****n****\}****构造****n****棵二叉树的集合****F=\{T****1****,T****2****,...,T****n****\}****，其中每棵二叉树****T****i****中只有一个带权为****w****i****的根结点，其左右子树均空。**
>  *  2.**在****F****中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。**
>  *  3.**在****F****中删除这两棵树，同时将新得到的二叉树加入****F****中。**
>  *  4.**重复****2****和****3****，直到****F中只含一棵树为止。这棵树便是最优二叉树。**
>  *  **最优二叉树**是一类带权路径长度最短的树。

### 2.举例说明，感性认识哈夫曼算法，根据上面的4步得出下表 ###

![20181122205324658.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70][]

### 3.结点结构体类型的定义 ###

![20181122210318686.png][]

> typedef struct \{  
>         char ch;  
>         int weight;  
>         int parent,lchild,rchild;  
> \}HTNode,\*Huffmantree;

### 4.select函数的编写  ###

/用s1和s2返回前end个结点中最小权重和次小权重的序号
    思路：将未被安排的结点的序号赋给s1,s2，从下一位开始，
    依次更新s1和s2的值，最后将这两个权重较小的序号给s1,较大的给s2.
     
    Status select(Huffmantree HT,int end,int &s1,int &s2)
    {  
    for(i=1,count=1;i<=end;i++)
    	{
    
    	 //结点成员parent值为0表明该结点还未被安排
             //将第一个，第二个未被安排的结点序号赋给m,n
             if(HT[i].parent ==0)
    		{
    			if(count==1)
    				m=i;
    			if(count==2)
    				n=i;
    			count++;
    		}
    		if(count>2)
    			break;
    	}
    
            //令m为结点较小权值的序号，令n为较大的序号
    	if(HT[m].weight>HT[n].weight)
    	{
    		tmp=n;
    		n=m;
    		m=tmp;
    	}
    
           //i从下一个开始，一直扫描到end
    	i=(m>n?m:n)+1;
    
    	while(i<=end)
    	{
           
                    //同样寻找未被安排的结点
    		if(HT[i].parent==0)
    		{
                           //i的权重比m的小,则用m替n, i替m
    			if(HT[i].weight<HT[m].weight)
    			{
    				n=m;
    				m=i;
    			}
    
                            //i的权重介于m和n之间，则用i替n
                            //还剩一种情况，当i比n大时，不做任何改变
                            //故在此分为了两类
    			else
    			{
    				if(HT[i].weight>=HT[m].weight&&
                                            HT[i].weight<HT[n].weight)
    				n=i;
    			}
    		}
    		i++;
    	}
    
             //用s1返回最小权重序号
            //用s2返回次小权重序号
    	s1=HT[m].weight<=HT[n].weight?m:n;
    	s2=HT[m].weight>HT[n].weight?m:n;
    	return ok;
    }

### 5.哈夫曼树的创建及编码的创建 ###

>  *  **//w\[\]****存放n个字符的权值，str存放n个字符名ch，构造赫夫曼树HT，并求出n个字符的编码**
>  *  int **HuffmanCoding**(Huffmantree &HT,char\*\* &HC, int \*w, int n,char \*str)

主要思路：

**n****个叶子结点对应2n+1个总结点，对序号从1到n的结点**

>          HT\[i\].weight = w\[i-1\];  
>          HT\[i\].parent = 0;  
>          HT\[i\].lchild = HT\[i\].rchild = 0;  
>          HT\[i\].ch=str\[i-1\];

**对序号从n+1到2n+1的结点：**

>          HT\[i\].ch='\\0';   //要是不赋为空的话为给出随机字符  
>          HT\[i\].parent = 0;  
>          HT\[i\].lchild = HT\[i\].rchild = 0;

>  *  **//****构造赫夫曼树,m=2\*n-1**
>  *  **//****从HT\[1..i-1\]中选择parent为0且weight最小的两个结点，其序号为s1和s2**

> ** **   select(HT,i-1,s1,s2);  
>     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;

>  *  **//****从叶子到根逆向求每个字符的赫夫曼编码**

> for(int c=i,f=HT\[i\].parent;f!=0;c=f,f=HT\[f\].parent)  
>        \{  
>            if (HT\[f\].lchild == c)   cd\[--start\]='0';  
>            else cd\[--start\]='1';  
>         \}  
>       HC\[i\] = (char\*)malloc((n-start)\*sizeof(char));  
>       strcpy(HC\[i\],&cd\[start\]);

### 6.解码 ###

>  
> 
>  *  **//将二进制编码翻译回信息原文，m是树根的编号**
>  *  int  **Decoding**(Huffmantree HT,int m,char \*buff)

> if ((\*buff)=='0')   
>                  p = HT\[p\].lchild; //进入左分支  
>           else   
>                  p = HT\[p\].rchild; //进入右分支  
>           buff++;   
>            if (!HT\[p\].lchild && !HT\[p\].rchild) \{   
>                //进入叶子结点  
>                printf("%c",HT\[p\].ch);     
>                p = m; //重新从树根出发进行译码

### 7. 打印哈夫曼树和哈夫曼编码 ###

>  *  **//****以表格的方式打印哈夫曼树**
>  *  void **ShowHuffmanTree**(Huffmantree HT,int n)
>  *  **//****以表格形式打印哈夫曼编码**
>  *  void **ShowHuffmanCode**(Huffmantree HT,char\*\* HC,int n)
>  *  **主要运用printf函数格式输出。**

### 8.完整代码 ###

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define ok 1
    
    //赫夫曼树的存储结构
    typedef struct {
        	char ch;
        	int weight;
        	int parent,lchild,rchild;
    }HTNode,*Huffmantree;  
    typedef int Status;
    
    //用s1和s2返回前end个结点中最小权重和次小权重的序号 
    Status select(Huffmantree HT,int end,int &s1,int &s2)
    {
    	int i,count;
    	int m,n,tmp;
    	if(end<2)
    		return 0;
    	for(i=1,count=1;i<=end;i++)
    	{
    		if(HT[i].parent ==0)
    		{
    			if(count==1)
    				m=i;
    			if(count==2)
    				n=i;
    			count++;
    		}
    		if(count>2)
    			break;
    	}
    	if(HT[m].weight>HT[n].weight)
    	{
    		tmp=n;
    		n=m;
    		m=tmp;
    	}
    	i=(m>n?m:n)+1;
    	while(i<=end)
    	{
    		if(HT[i].parent==0)
    		{
    			if(HT[i].weight<HT[m].weight)
    			{
    				n=m;
    				m=i;
    			}
    			else
    			{
    				if(HT[i].weight>=HT[m].weight&&HT[i].weight<HT[n].weight)
    				n=i;
    			}
    		}
    		i++;
    	}
    	s1=HT[m].weight<=HT[n].weight?m:n;
    	s2=HT[m].weight>HT[n].weight?m:n;
    	return ok;
    }
    
    
    //w[]存放n个字符的权值，str存放n个字符名ch，构造赫夫曼树HT，并求出n个字符的编码
    int HuffmanCoding(Huffmantree &HT,char** &HC, int *w, int n,char *str)
    {
    	int i,m;
         if (n<=1)  return 0;  
        	m = 2*n-1;
         HT =(Huffmantree)malloc((m+1)*sizeof(HTNode));
         for(i=1; i<=n; i++) 
    	{
             HT[i].weight = w[i-1];
             HT[i].parent = 0;
             HT[i].lchild = HT[i].rchild = 0;
             HT[i].ch=str[i-1];
        }
        for(; i<=m; ++i)//m=2*n-1
    	{
    		 HT[i].ch='\0';
             HT[i].parent = 0;
             HT[i].lchild = HT[i].rchild = 0;
    	} 
    	for(i=n+1; i<=m; i++)
    	{//构造赫夫曼树,m=2*n-1
        //从HT[1..i-1]中选择parent为0且weight最小的两个结点，其序号为s1和s2
        int s1, s2;
        select(HT,i-1,s1,s2);
        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+1)*sizeof(char*));
       char *cd;
       cd = (char *)malloc(n*sizeof(char));    
       cd[n-1] = '\0';
       for(i=1; i<=n; i++)  
       {
          int start = n-1;
          for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
          	{
               if (HT[f].lchild == c)   cd[--start]='0';
               else cd[--start]='1';
        	}
          HC[i] = (char*)malloc((n-start)*sizeof(char));
          strcpy(HC[i],&cd[start]);
          	//printf("%c的哈夫曼编码是%s\n",HT[i].ch,HC[i]);
       }
      free(cd);
     
      return ok;
    }//HuffmanCoding
    
    //将二进制编码翻译回信息原文，m是树根的编号
    int  Decoding(Huffmantree HT,int m,char *buff)
     {   
           int p = m;   
    	  while (*buff != '\0' && p != 0) {
               if ((*buff)=='0') 
                     p = HT[p].lchild; //进入左分支
    	      else 
                     p = HT[p].rchild; //进入右分支
    	      buff++; 
               if (!HT[p].lchild && !HT[p].rchild) { 
                   //进入叶子结点
                   printf("%c",HT[p].ch);   
                   p = m; //重新从树根出发进行译码
               }//if
    	}//while
    	return ok;
    }//Decoding	
    
    void ShowHuffmanTree(Huffmantree HT,int n)
    {
    	int i;
    	printf("┍┉┉┉┉┉┉┉┉┱┉┉┉┉┉┉┉┉┱┉┉┉┉┉┉┉┉┲┉┉┉┉┉┉┉┉┲┉┉┉┉┉┉┉┉┲┉┉┉┉┉┉┉┉┒\n");
    	printf("┋   ch   ┋ order  ┋ weight ┋ parent ┋ lchild ┋ rchild ┋\n");
    	for(i=1;i<=n;i++)
    			printf("┋   %c    ┋   %2d   ┋   %3d  ┋   %2d   ┋   %2d   ┋   %2d   ┋\n",
    			HT[i].ch,i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    	printf("┖┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┚\n");
     } 
     
     void ShowHuffmanCode(Huffmantree HT,char** HC,int n)
     {
     	int i;
     	printf("┍┉┉┉┉┉┉┉┉┱┉┉┉┉┉┉┉┉┲┉┉┉┉┉┉┉┉┲┉┉┉┉┉┉┉┉┲┉┉┉┉┉┉┉┉┒\n");
     	printf("┋   ch   ┋ order  ┋ weight ┋        ┋  Code  ┋\n");
     	for(i=1;i<=n;i++)
     	printf("┋   %c    ┋   %2d   ┋   %2d   ┋  ---->  %-8s┋\n",
    	 HT[i].ch,i,HT[i].weight,HC[i]);
     	printf("┖┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┺┉┉┉┉┉┉┉┉┚\n");
     }
    
    int main()
    {
    	int n,m;
    	printf("请输入叶子结点的个数：");
    	scanf("%d",&n);
    	int w[n]; 
    	printf("\n请依次输入各结点的权值：\n");
    	for(int i=0;i<n;i++)
    		scanf("%d",&w[i]); 
    	char str[n];
    	printf("\n给叶子结点起个名字：\n");
    	scanf("%s",str);
    	Huffmantree HT;char** HC;
    	printf("\n哈夫曼树构建中...\n\n"); 
    	HuffmanCoding( HT, HC, w,  n, str);
    	printf("打印哈夫曼树：\n"); 
    	ShowHuffmanTree( HT,2*n-1);
    	printf("\n打印叶子结点的哈夫曼编码：\n"); 
    	ShowHuffmanCode( HT, HC, n);
    	
    	printf("\n执行解码操作，请输入一串哈夫曼编码：\n");
    	char buff[50];
    	scanf("%s",buff);
    	printf("解码为：\n");
    	Decoding( HT, 2*n-1 ,buff);
    	printf("\n");
    	system("pause");
    	return 0;
    }
    
    /* test data
    8
    5 29 7 8 14 23 3 11
    abcdefgh
    a的哈夫曼编码是0001
    b的哈夫曼编码是10
    c的哈夫曼编码是1110
    d的哈夫曼编码是1111
    e的哈夫曼编码是110
    f的哈夫曼编码是01
    g的哈夫曼编码是0000
    h的哈夫曼编码是001
    */

### 9.运行截图 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 1][]

[20181122205324658.png]: /images/20220415/d37317e05b56489ebe350fca9c258af1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70]: /images/20220415/8806a4cee16746539edfab5e03370d65.png
[20181122210318686.png]: /images/20220415/647d53eae3744cf0b68f9de3aee86585.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 1]: /images/20220415/7ed7c79f95e14d76a15a3b73d13f740b.png