搜索
简单介绍哈夫曼树本篇文章给大家带来的内容是哈夫曼树，简单介绍一下哈夫曼树，以及解析，希望对大家的学习有所帮助。废话不多说，马上进入正题。给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmanTree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。哈夫曼树是二叉树的一个典型应用，利用哈夫曼树，我们可以形成哈夫曼编码，进而实现对数据的压缩与解压处理。哈夫曼树，指的是对于一组具有确定权值的叶子结点的具有最小带权路径长度的二叉树。哈夫曼树当中的几个概念我们不得不说一下:(1)路劲(Path):从树中的一个结点到另一个结点之间的分支构成两个结点间的路径。(2)路径长度(PathLength):路径上的分支树。(3)树的路径长度(PathLengthofTree):从树的根结点到每个结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。(4)结点的权(WeightofNode):在一些应用中，赋予树中结点的一个有实际意义的树。(5)结点的带权路径长度(WeightPathLengthofNode):从该结点到树的根结点的路径长度与该结点的权的乘积。(6)树的带权路径长度(WPL):树中所有叶子结点的带权路径长度之和在下图所示的四棵二叉树，都有4个叶子结点，其权值分别1、2、3、4,他们的带权路径长度分别为:(a)WPL=1x2+2x2+3x2+4X2=20(b)WPL=1x1+2x2+3x3+4x3=28(c)WPL=1x3+2x3+3x2+4x1=19(d)WPL=2x1+1x2+3x3+4x3=29其中，(c)图所示的二叉树的带权路径长度最小，这棵树就是哈夫曼树。可以验证，哈夫曼树的带权路径长度最小。那么我们应该如何构建一个哈夫曼树呢?其实并不复杂：1)首先构建一个叶子节点集合，这里我用链表来表示，每个节点在插入到链表中时是按照权值由小到大顺序插入的。2)首先判断当前集合节点的个数是否大于1，如果不大于，则程序结束，集合里的节点即为创建好的哈夫曼树的根节点，如果大于1，则转至33)取出集合中前两个节点(取出后集合中已经删除掉这两个节点),由这两个节点构建一颗新树，新树的权值为这两个节点之和。权值较小的节点为新树的左孩子，较大的节点为新树的右孩子。4)将新树按权值由小到大的顺序插入到集合中，转至2。实现代码如下:mytypes.hbitree.hbitree.clinklist.hlinklist.cmain.cmakefile:以上内容简单介绍了哈夫曼树和解析，看完后是否觉得获益匪浅呢?更多精彩教程可以在华清远见官网查询，华清远见为广大学者提供免费资料以供参考学习。