数据结构考研重难点解析：哈夫曼树 
2019考研交流群
内蒙古中公考研：nmkaoyan >>>【专硕】38个专业硕士历年考研国家线走势 >>>2018考研国家线、34所自划线高校考研分数线及历年分数线 数据结构考研重难点解析：哈夫曼树 数据结构是计算机专业考研重点内容，大部分院校都是考到了数据结构，其中哈夫曼树是其中的重点难点内容，经常会考到我们的综合应用题，今天内蒙古中公考研小编为大家整理了“数据结构考研重难点解析：哈夫曼树”的相关信息，希望能够帮助到大家。 哈夫曼树是一棵较优二叉树，其定义是：给定n个权值作为n个叶子节点，构造一棵二叉树，若树的带权路径长度达到较小，这样的树就达到较优二叉树，也就是哈夫曼树，示例图如图1-1所示： 
图1-1 示例1 一、基本概念 在正式开始学习哈夫曼树前，先了解一下哈夫曼树的一些基本概念，并以上面的哈夫曼树示例图1为例。 路径：树中一个结点到另一个结点之间的分支序列构成两个结点间的路径。 路径长度：路径中分支的数目，从根结点到第L层结点的路径长度为L-1。例如结点100到结点80的路径长度为1，结点50到结点30的路径长度为2。 结点的权：树中结点的数值，例如100，50等，这些数值对于结点来说具有某种含义。 结点带权路径长度：根结点到该结点之间的路径长度与该结点的权的乘积。 如结点20的路径长度为3，该结点的带权路径长度为：3*20 = 60。 树的带权路径长度：所有叶子结点的带权路径长度之和，记为WPL。例如示例图1的WPL = 1*100 + 2*80 +3*20 +3*10 = 350。 二、带权路径长度比较 前面说到，哈夫曼树是较优二叉树，因为符合哈夫曼树特点的树的带权路径长度一定是较小的，所以说，我们将哈夫曼树和普通的二叉树的带权路径长度做个比较，仍以上图为例，上图的哈夫曼树是结点10，20，50，100组成的二叉树，WPL是350，用这四个结点组成普通的二叉树，如图1-2所示： 
图1-2 示例2 不难计算，该二叉树的WPL = 2*10 + 2*20 + 2*50 + 2*100 = 360，明显比哈夫曼树大，当然二叉树的组成结果不唯一，但WPL一定比哈夫曼树大。所以说哈夫曼树是较优二叉树。 三、哈夫曼树的构造 现在假定有n个权值，设为w1、w2、…、wn，将这n个权值看成是有n棵树的森林，根据较小带权路径长度的原则，我们可以按照下面步骤来将森林构造成哈夫曼树： 1.在森林中选出根结点的权值较小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和; 2.从森林中删除选取的两棵树，并将新树加入森林; 3.重复1、2步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。 以森林 (16，20，23，24，50) 为例，其构造步骤如下： ① 合并权值为16和20的树，构成权值为36的新树，森林变为(36，23，24，50); ② 合并较小的两棵树23和24，组成新的树47，这时森林变为(36，47，50); ③ 合并36和47的树作为权值83的新树，并和50结合组成根节点权值为133的哈夫曼树。 较终结果图如图1-3所示： 
图1-3 示例3 四、哈夫曼编码 哈夫曼编码是一种无前缀编码，它使用一种特别的方法为信号源中的每个符号设定二进制码，并且在解码时不会混淆。其主要应用在数据压缩，加密解密等场合。可以与哈夫曼树进行结合生成。 从哈夫曼树的根节点开始，左子树分配0，右字数分配1，一直递归下去，然后就可以得到符号的码值了。假设我有A,B,C,D,E五个字符，出现的频率(即权值)分别为16,20,23,24,50。拿这五个字符的频率构造一棵哈夫曼树，如图1-4所示： 
图1-4 示例4 这样结点对应的编码为：A: 100，B:101，C:110，D:111，E:0。 以上是内蒙古中公考研小编整理的“数据结构考研重难点解析：哈夫曼树”相关内容，相信大家看完后能理解什么是假设和如何找假设，但是找假设是需要通过不断地做题积累，才能真正的掌握，所以大家平时一定要记得多做一些题。 推荐阅读： 2020考研：暑期写作复习指南 2020考研：会计备考暑期复习规划 2020考研：管综暑期复习规划 2020考研：2020年管理类联考大纲解读 更多研究生考试信息尽在内蒙古中公考研网。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/51206.html
