[C/C++] 构造最优二叉树－赫夫曼(哈夫曼、Huffman)树算法实现

2024-02-26 07:38
文章标签 算法 二叉树 c++ 实现 构造 最优 哈夫曼 huffman 夫曼

本文主要是介绍[C/C++] 构造最优二叉树－赫夫曼(哈夫曼、Huffman)树算法实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、基本概念

1、赫夫曼（Huffman）树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。在许多应用中，常常赋给树中结点一个有某种意义的实数，称此实数为该结点的权。从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度(WPL)，树中所有叶子结点的带权路径长度之和称为该树的带权路径长度.

 

2、两结点间的路径：从一结点到另一结点所经过的结点序列;路径长度：从根结点到相应结点路径上的分支数目;树的路径长度：从根到每一结点的路径长度之和。

3、深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。在结点数目相同的二叉树中完全二叉树是路径长度最短的二叉树。

4、WPL最小的二叉树是最优二叉树(Huffman 树)。

5、赫夫曼（Huffman）树的特征

① 当叶子上的权值均相同时，完全二叉树一定是最优二叉树。否则完全二叉树不一定是最优二叉树。

② 在最优二叉树中，权值越大的叶子离根越近。

③ 最优二叉树的形态不唯一，但WPL最小。 

   

如上图中，只有(d)才是赫夫曼树。其中，圆围中的数值代表权值。

二、算法思想

  (1)  以权值分别为W1,W2．．．Ｗｎ的ｎ各结点，构成n棵二叉树T1,T2,．．．Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点；

  (2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi）

  (3) 从F中删除这两棵二叉树，同时将新二叉树加入到F中;

  (4) 重复(2)、(3)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman树。

 

三、C语言描述

(1)我们用如下结构来存储赫夫曼树：

       用大小为2n-1的一维数组来存储哈夫曼树中的结点，其存储结构为：

[cpp] view plain copy
  1. #define n 100               //叶结点数目  
  2. #define m 2*n-1             //树中结点总数  
  3. typedef struct  
  4. {  
  5.     float weight;             //权值，设权值均大于零  
  6.     int lchild,rchild,parent;  //左右孩子及双亲指针  
  7. } HTNode;  
  8.  typedef HTNode HuffmanTree[m]; //哈夫曼树是一维数组  
 

      因为C语言数组的下界为0，用-1表示空指针。树中结点的lchild、rchild和parent不等于-1时，分别表示该结点的左、右孩子和双亲结点在数组中的下标。

设置parent域有两个作用：一是使查找某结点的双亲变得简单；二是可通过判定parent的值是否为-1来区分根与非根结点。

(2)哈夫曼算法的简要描述

在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：

①初始化 将T[0…m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。

②输入 读入n个叶子的权值存于数组的前n个分量(即T[0…n-1])中。它们是初始森林中n个孤立的根结点上的权值。

③合并 对森林中的树共进行n-1次合并，所产生的新结点依次放入数组T的第i个分量中(n≤i≤m-1)。每次合并分两步：

1) 在当前森林T[0…i-1]的所有结点中，选取权值最小和次小的两个根结点T [p1]和T[p2]作为合并对象，这里0≤p1，p2≤i-1。

        2) 将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。

具体操作：

将T[p1]和T[p2]的parent置为i；

将T[i]的lchild和rchild分别置为p1和p2；

新结点T[i]的权值置为T[p1]和T[p2]的权值之和。

合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。

(3)赫夫曼算法的数组法构造

[cpp] view plain copy
  1. void CreateHuffmanTree(HuffmanTree T)  
  2. {  
  3.     int i,p1,p2;                        //构造哈夫曼树，T[m-1]为其根结点  
  4.     InitHuffmanTree(T);       //T初始化  
  5.     InputWeight(T);               //输入叶子权值至T[0．．n-1]的weight域  
  6.     for(i=n;i<m;i++)  
  7.     {    
  8.          SelectMin(T,i-1,&p1,&p2);//共进行n-1次合并，新结点依次存于T[i]中  
  9.                  //在T[0…i-1]中选择两个权最小的根结点，其序号分别为p1和p2  
  10.         T[p1].parent=T[p2].parent=i;  
  11.         T[i].1child=p1;              //最小权的根结点是新结点的左孩子  
  12.         T[i].rchild=p2;               //次小权的根结点是新结点的右孩子  
  13.         T[i].weight=T[p1].weight+T[p2].weight;  
  14.     }//for  
  15. }//CreateHuffman  
 

四、C语言实现

[cpp] view plain copy
  1. #include "stdio.h"  
  2. #include "stdlib.h"  
  3. #define m 100  
  4.    
  5. struct ptree              //定义二叉树结点类型  
  6. {  
  7. int w;                   //定义结点权值  
  8. struct ptree *lchild;     //定义左子结点指针  
  9. struct ptree *rchild;     //定义右子结点指针  
  10. };  
  11.    
  12. struct pforest              //定义链表结点类型  
  13. {  
  14. struct pforest *link;  
  15. struct ptree *root;  
  16. };  
  17.    
  18. int WPL=0;                  //初始化WTL为0  
  19. struct ptree *hafm();  
  20. void travel();  
  21. struct pforest *inforest(struct pforest *f,struct ptree *t);  
  22.    
  23. void travel(struct ptree *head,int n)                       
  24. {  
  25. //为验证harfm算法的正确性进行的遍历  
  26. struct ptree *p;  
  27. p=head;  
  28. if(p!=NULL)  
  29.  {  
  30.        if((p->lchild)==NULL && (p->rchild)==NULL) //如果是叶子结点  
  31.       {  
  32.               printf("%d ",p->w);  
  33.               printf("the hops of the node is: %d/n",n);  
  34.        WPL=WPL+n*(p->w);    //计算权值  
  35.          }//if  
  36. travel(p->lchild,n+1);  
  37. travel(p->rchild,n+1);  
  38. }//if  
  39. }//travel  
  40.    
  41. struct ptree *hafm(int n, int w[m])  
  42. {  
  43. struct pforest *p1,*p2,*f;  
  44. struct ptree *ti,*t,*t1,*t2;  
  45. int i;  
  46. f=(pforest *)malloc(sizeof(pforest));  
  47. f->link=NULL;  
  48. for(i=1;i<=n;i++)          //产生n棵只有根结点的二叉树  
  49.   {  
  50.        ti=(ptree*)malloc(sizeof(ptree));//开辟新的结点空间  
  51.     ti->w=w[i];               //给结点赋权值  
  52.     ti->lchild=NULL;  
  53.     ti->rchild=NULL;  
  54.     f=inforest(f, ti);  
  55.        //按权值从小到大的顺序将结点从上到下地挂在一颗树上        
  56.   }//for  
  57. while(((f->link)->link)!=NULL)//至少有二棵二叉树  
  58.   {  
  59.   p1=f->link;  
  60.   p2=p1->link;  
  61.   f->link=p2->link;           //取出前两棵树  
  62.   t1=p1->root;  
  63.   t2=p2->root;  
  64.   free(p1);                 //释放p1  
  65.   free(p2);                 //释放p2  
  66.   t=(ptree *)malloc(sizeof(ptree));//开辟新的结点空间  
  67.   t->w = (t1->w)+(t2->w);         //权相加  
  68.   t->lchild=t1;  
  69.   t->rchild=t2;             //产生新二叉树  
  70.   f=inforest(f,t);  
  71.   }//while  
  72.   p1=f->link;  
  73.   t=p1->root;  
  74.   free(f);  
  75.  return(t);                  //返回t  
  76.  }  
  77.    
  78. pforest *inforest(struct pforest *f,struct ptree *t)  
  79. {  
  80. //按权值从小到大的顺序将结点从上到下地挂在一颗树上        
  81. struct pforest *p, *q, *r;  
  82. struct ptree *ti;  
  83. r=(pforest *)malloc(sizeof(pforest)); //开辟新的结点空间  
  84. r->root=t;  
  85. q=f;  
  86. p=f->link;                
  87. while (p!=NULL)            //寻找插入位置  
  88.  {  
  89.    ti=p->root;  
  90.    if(t->w > ti->w)          //如果t的权值大于ti的权值  
  91.      {  
  92.          q=p;  
  93.       p=p->link;             //p向后寻找  
  94.      }//if  
  95.    else  
  96.       p=NULL;                  //强迫退出循环  
  97.   }//while  
  98. r->link=q->link;  
  99. q->link=r;                 //r接在q的后面  
  100. return(f);                 //返回f  
  101. }  
  102.    
  103. void InPut(int &n,int w[m])  
  104. {  
  105. printf("please input the sum of node/n"); //提示输入结点数  
  106. scanf("%d",&n);      //输入结点数  
  107. printf ("please input weight of every node/n"); //提示输入每个结点的权值  
  108. for(int i=1;i<=n;i++)  
  109. scanf("%d",&w[i]);  //输入每个结点权值  
  110. }  
  111.    
  112. int main( )  
  113. {  
  114. struct ptree *head;  
  115. int n,w[m];  
  116. InPut(n,w);  
  117. head=hafm(n,w);   
  118. travel(head,0);  
  119. printf("The length of the best path is WPL=%d", WPL);//输出最佳路径权值之和  
  120. return 1;  
  121. }  
 

五、最优二叉树的应用

哈夫曼树的应用很广，哈夫曼编码就是哈夫曼树在电讯通信中的应用之一。它采用不等长编码，让出现次数多的字符用短码，且任一编码不能是另一编码的前缀（我们称之为前缀编码，或非前缀码）。设有n种字符，每种字符出现的次数为Wi，其编码长度为Li (i=1,2,．．．n)，则整个电文总长度为∑ Wi Li ，要得到最短的电文，即使得∑ Wi Li最小。也就是以字符出现的次数为权值，构造一棵Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。用构造Huffman树编出来的码，称为Huffman编码。

为了获得传送电文的最短长度，可将字符出现的次数（频率）作为权值赋予该结点，构造一棵WPL最小的哈夫曼树，由此得到的二进制前缀编码就是最优前缀编码，也称哈夫曼编码。可以验证，用这样的编码传送电文可使总长最短。

 

       我们在修改程序时，只要将原来的travel改成如下即可实现赫夫曼编码，当然，译码原理也相同：

[cpp] view plain copy
  1. #define count 15  
  2. char ch[count][count];  
  3. int counter=0;  
  4. int tag,counter2=0;  
  5. void Initch()  
  6. {  
  7.     for(int i=0;i<count;i++)  
  8.             ch[i][count-1]='/0';  
  9. }  
  10. void travel(struct ptree *head,int n,int tag)                        
  11. {  
  12. //为验证harfm算法的正确性进行的遍历  
  13. struct ptree *p;   
  14. p=head;  
  15. if(p!=NULL)  
  16.  {  
  17.     if(tag==-1)   
  18.         {  
  19.         ch[counter][counter2++]='0';  
  20.         //for(int j=counter;j<count-1;j++) strcpy(ch[j+1],ch[counter]);  
  21.         }  
  22.     if(tag==+1)   
  23.         {  
  24.         ch[counter][counter2++]='1';  
  25.         for(int j=counter;j<count-1;j++) strcpy(ch[j+1],ch[counter]);  
  26.         }  
  27.     if((p->lchild)==NULL && (p->rchild)==NULL) //如果是叶子结点  
  28.       {   
  29.         printf("%d ",p->w);  
  30.         printf("the hops of the node is: %d ",n);  
  31.         printf("Code is %s/n",ch[counter]);  
  32.         counter++;  
  33.         counter2--;  
  34.         WPL=WPL+n*(p->w);    //计算权值  
  35.       }//if  
  36. travel(p->lchild,n+1,-1);  
  37. travel(p->rchild,n+1,+1);  
  38. }//if  
  39. }//travel  

这篇关于[C/C++] 构造最优二叉树－赫夫曼(哈夫曼、Huffman)树算法实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/748111。

相关文章

Java StringBuilder 实现原理全攻略

Java StringBuilder 实现原理全攻略

《JavaStringBuilder实现原理全攻略》StringBuilder是Java提供的可变字符序列类,位于java.lang包中,专门用于高效处理字符串的拼接和修改操作,本文给大家介绍Ja... 目录一、StringBuilder 基本概述核心特性二、StringBuilder 核心实现2.1 内部
阅读更多...
Android实现图片浏览功能的示例详解(附带源码)

Android实现图片浏览功能的示例详解(附带源码)

《Android实现图片浏览功能的示例详解(附带源码)》在许多应用中,都需要展示图片并支持用户进行浏览,本文主要为大家介绍了如何通过Android实现图片浏览功能,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码
阅读更多...
SpringBoot AspectJ切面配合自定义注解实现权限校验的示例详解

SpringBoot AspectJ切面配合自定义注解实现权限校验的示例详解

《SpringBootAspectJ切面配合自定义注解实现权限校验的示例详解》本文章介绍了如何通过创建自定义的权限校验注解,配合AspectJ切面拦截注解实现权限校验,本文结合实例代码给大家介绍的非... 目录1. 创建权限校验注解2. 创建ASPectJ切面拦截注解校验权限3. 用法示例A. 参考文章本文
阅读更多...
SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
C++右移运算符的一个小坑及解决

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned
阅读更多...
Python使用FastAPI实现大文件分片上传与断点续传功能

Python使用FastAPI实现大文件分片上传与断点续传功能

《Python使用FastAPI实现大文件分片上传与断点续传功能》大文件直传常遇到超时、网络抖动失败、失败后只能重传的问题,分片上传+断点续传可以把大文件拆成若干小块逐个上传,并在中断后从已完成分片继... 目录一、接口设计二、服务端实现（FastAPI）2.1 运行环境2.2 目录结构建议2.3 serv
阅读更多...
C#实现千万数据秒级导入的代码

C#实现千万数据秒级导入的代码

《C#实现千万数据秒级导入的代码》在实际开发中excel导入很常见,现代社会中很容易遇到大数据处理业务,所以本文我就给大家分享一下千万数据秒级导入怎么实现,文中有详细的代码示例供大家参考,需要的朋友可... 目录前言一、数据存储二、处理逻辑优化前代码处理逻辑优化后的代码总结前言在实际开发中excel导入很
阅读更多...
SpringBoot+RustFS 实现文件切片极速上传的实例代码

SpringBoot+RustFS 实现文件切片极速上传的实例代码

《SpringBoot+RustFS实现文件切片极速上传的实例代码》本文介绍利用SpringBoot和RustFS构建高性能文件切片上传系统,实现大文件秒传、断点续传和分片上传等功能,具有一定的参考... 目录一、为什么选择 RustFS + SpringBoot？二、环境准备与部署2.1 安装 RustF
阅读更多...
Nginx部署HTTP/3的实现步骤

Nginx部署HTTP/3的实现步骤

《Nginx部署HTTP/3的实现步骤》本文介绍了在Nginx中部署HTTP/3的详细步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录前提条件第一步：安装必要的依赖库第二步：获取并构建 BoringSSL第三步：获取 Nginx
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2