同学们好,今天介绍哈弗曼树的定义和构成方法。先看几个基本概念, 路径和路径长度。在一棵树中,从一个节点往下可以达到的子节点之间的通路称为路径,通路中分支的树木称为路径长度。若规定根节点的层数为一,则从根节点到第 l 层节点的路径长度为 l。 减一 看下面这棵树,节点 a 的路径长度为一,节点 b 的路径长度为二,节点 c 和节点 d 路径长度都是三。 下一个概念,节点的全以及代全路径长度。如果给数中的节点赋予一个有着某种含义的数值,则这个数值称为该点的全节点 a、 b、 c、 d 的全分别为七、五、二和四。节点 的代全路径长度定义为从根节点到该节点之间的路径长度与该节点的全的乘积。在这棵树中,节点 a 的路径长度为一,全为七,他的代全路径长度等于一乘以七, 节点 b 代全路径长度等于二乘以五,节点 c 等于三乘以二,节点 d 等于三乘以四。最后介绍一下竖的代全路径长度。竖的代全路径长度是所有叶子节点的代全路径长度之和。 在下图中,这棵树的代全路径长度等于节点 a 的代全路径长度七乘以一,加上节点 b 的代全路径长度五乘以二,再加上节点 c 的二乘以三,再加上节点 d 的四乘以三。由此可以得到 哈弗曼树的概念。给出 n 个叶子节点,每个节点都对应着一个全植,构建一棵二叉树,如果该树的带全路径长度最小,这样的二叉树成为最优二叉树,也叫做哈弗曼树。来看一下哈弗曼树的构成。 有六个节点,他们的全职分别是一、七、三、四、九和八。首先选择两个全职最小的节点 a 和 c。 全职是一和三,将他们删除,组成一个新的二茬数。用树枝连起来 计算他们的核作为他们的根,再将根加入到节点对列。如果这个数恰好是下一步两个最小数其中之一,那么这个数直接往上生长。如果计算出的全值 比较大,不是下一步两个最小数其中之一,那么就并列生长。继续从五个数中选择两个较小的,选择了四和四向上生长,用树枝连起来他们的和是八。 将八加入对列,再选择两个最小的数,七和八,包括刚才的八向上生长, 用数值连起来计算他们的和十五。将十五加入对列,选择两个最小的数九和八。注意,刚刚生成的十五不再是最小的两个数之一。并列生长, 将九和八用数值连起来计算他们的和十七,将十七加入对列,最后还剩两个数,十五和十七别无选择。 用树枝连起来计算他们的和三十二。到现在为止,哈佛曼术构建完毕。哈佛曼术有以下几个特点, 第一, n 个叶子结点生成的哈佛曼树有二 n 减一个结点。这是因为每次将两颗全枝最小的二叉树合并成一颗新的二叉树时,需要增加一个结点作为新二叉树的根结点。 第二,全职大的节点离根近,全职小的节点离根远。第三,生成的二叉数不为 一,两棵全植最小。倒插树哪棵作为左子树,哪棵作为右子树?哈弗曼算法并没有要求,但是最小的代全路径长度是唯一的。 第四,没有度,唯一的节点。由于每次都是将两颗全枝最小的二茬树合并成一棵新二茬树,所以没有度唯一的节点。好了,哈弗曼树我们就讲到这里,谢谢大家。
粉丝1684获赞7060

今天的视频很有趣,我相信你一定能够听懂。各位同学,大家好,今天我们来看一个关于哈弗曼数的知识点以及题目。 设有一份电文中共有 abcdef 这六个字符,他们的出现频率如下表所示。现通过构造哈弗曼数为这些字符编码,最终要求两个编码最长的字符。 题中给到了每个制服的出现频率。这道题的解题思路分两步,先根据给出的制服频率构建哈弗慢速, 然后得出每个字符的编码,最后他们的长度一目了然。那我们来看哈弗曼数的构建。我们 先将制服频率由大到小进行排序,然后我们将末尾最小的两个数组成二差数的直接点。 那么什么又是二差数呢?二差数就是最多有两个指节点的数,且指节点分左右, 于是我们将零点零五和零点零六组成二差数的节点。注意保持右节点始终要比左节点大, 让他俩之和作为他们的负节点,并依据值的大小排在之前的序列里。然后再寻找新的序列里最小的两个值,再组成二差数。于是我们看到零点一三和零点一一是最小的两个值,我们将其 组成一个二差数,这个时候我们得到一个零点二四的负阶点,我们将其排列到之前的序列里。这个时候新的序列中零点二三和零点一九是这个序列里最小的两个值,我们再将其组成一个二差数, 于是我们得到一个零点四二的负节点,在新的序列里排首位。于是我们又将末位的两个节点组成一个二叉数, 得到零点五八的负节点排在最前面。此时我们的序列里只剩两个元素,于是我们将它组成一个新的二叉数, 并且按照右节点大于左节点的规则交换他们的位置。最后我们得到一个完整的二叉数, 这个二叉数就是我们要求的哈弗曼数,也称为最优二叉数。 到这里我们就完成了第一部分的构建内容。接下来我们将制服标注到对应的概率数据上去,然后将哈弗曼数左右结点分别看作二进制的零和一, 按照左零右一的规则进行标注。接下来我们对要球的直接点进行编码。 首先我们看 a 字符从二叉数的顶点向下经过零和零两条路径到达, 因此字符 a 的编码是。字符 b 位于较远的节点, 从顶点向下分别会经过一一、零零这几个节点。因此制服 b 的编码是一一零零。 依次可以求得字符 c 的编码是零一,字符 d 的编码是一一一,字符 f 的编码是一一零一。 因此根据题目的要求,编码长度最长的两个字符是 b 和 f。 本题应当选择 c 答案。 今天的两个知识点分别是哈弗曼数的构造和哈弗曼数的编码。没有看懂的同学请保存或收藏,务必多看几遍, 听懂的同学请点个赞!后面继续跟着我一起学习。关注我,你们身边一个懂计算机的朋友!

嗯,大家好,今天我们来讲一下一个哈弗曼数的一个构造,然后他最后成型是一个这样的一个东西。然后我们就是主要来讲一下这个解题的一个过程,然后我们的主要过程就是第一步啊,第一步就是说一个排序,把这些按递增的一个序列,就是从小到大排序。第二步就是 找到这个序列里面的前两个最小的就是三跟五,这就是八到七八、八十一、十四、二三、二九。然后这里的这里我们就呃 开始继续往下面做呃,七八八七八、八、十一、十四、二三跟二九,我们这是第二次,第二次,因为这是第一次嘛,这是第一次,第二次的话就相当于是七跟八构成的是一个十五, 然后连序列去掉七跟八,把十五插入到其中就是八十一、十四、十五、二三跟二九。然后第三步第三次 我们就把八跟十一取出来,八跟十一取出来就是构成一个十九,这里的八,这里的八跟我们这里的八是对应起来的,这里的八就是对应的是一个三根 啊,然后就是把十九插入到其中八根弦去掉就是十四、十五、五十四、十五、十九、二三跟二九。 第四步第四次就相当于是十四跟十五嘛,十四跟十五就是二十九, 二十九插入到其中,十四、十五去掉十九、二三、二九跟二九。然后第五次就是呃,十九跟二三, 就是一个四十二,然后四十二他就是二九,二九跟四二。然后第六次就是二九跟二九跟一个五十八,对,然后就是 呃多少来着五十八、二九、二九,去掉就是四二跟五八嘛,然后第七次就是四二五、八跟一百, 然后把这些就是这几个,这,这从上面到下面这几个拼起来。什么叫拼起来呢?你看,呃,我们第一, 四呢?三跟五,这第一次,第一次三跟五,我们构成了一个八,然后呢?然后我们把八插回去了,就是说七跟八构成了什么?七跟八构成了十五,七跟八构成了十五,七跟八构成了这个十五, 然后十五放回去,这个八,这个八,这个八呀,这个八跟十一,八跟十一构成了一个十九,然后十九。嗯,看这里啊, 八跟十一构成的一个十九,十九。之后我们插入再插入到其中,其中选选两个最小的十九跟二十三,十九跟二十三, 二十三构成了多少?十九跟二十三构成了 四十二, 然后呢?四十二、四十二、二九跟二九。这里有一个二九。是,呃,这里有一个二九跟二九又构成了一个多少,二九跟二九构成了一个四,呃,构成一个五十八,二九跟二九 构成了一个五十八、五十八,然后二九。 我们这里的二九是十四根十五。呃,等一下,这里的十五应该是移到这边啊,然后十四根,十五嘛,圆圆须还有个十四,十四根十五就构成了一个,这个,这两个构成了一搏。 其实这个这个就,呃,跟我们跟我们这边的,跟我们这边的是一样,跟我们这边是一样。然后整个哈弗曼树的一个构造就到这里完成,然后顺带讲一下哈弗曼边 马上这个这个树画的太丑了。哈佛半边马,哈佛半边马就是记住一个原则,就是左零右一零一零一零一, 你就是把每颗节点的左子左左分支跟右跟那个右分支标成零跟一。然后比如人家问你啊,这个七的哈弗曼编码是多少,我们就可以七,我们就就就举个举个例子啊, 叫七的哈弗曼对应就是,哎,我们一条路数下来看一下,一一一 零啊,那就是一一一零八对应的是多少的幺幺幺幺幺幺幺,然后就以此类推啊,我们就假如啊,我再举个例子,这个五的话,那不就是零零零 一,五的话就是零零零一哈弗曼,哈弗曼编码的就这样去进,就我们去找节点的哈弗曼编码是多少,就这样去找左零右一的原则,左零右一,然后就讲到这里吧。好,谢谢大家。

直观理解哈弗曼数,哈弗曼编码呢,是由哈弗曼在一九五二年发明得到的,然后为了纪念他的成就呢,就把他编码当中用到的这种特殊的二叉数啊,称为哈弗曼数。我们平时用到的这个压缩和解压缩技术呢,都是基于他的研究发展而来的。 让我们来直观理解一下,哈弗曼数到底是什么样子。我们都知道呢,现在推行的是这个素质教育,所以说很多学校啊,都已经不再公布学生的成绩了,转而是用这个不及格,及格良好、优秀啊等等的标签来代替。 但是对于老师来说呢,他首先肯定还是要对这个学生的分数进行一个计算,然后再根据各个的区间呢,对学生进行一个打标签的这样的一个行为,整个的这个流程啊,就可以用这一段简单的代码来表示一下。但是呢,这个流程其实存在一个问题,就是一份 设计的比较合理的试卷呢,他其实是让学生的成绩呈现一个类似正态分布的一个样子,也就是说非常优秀的呢和不及格的学生啊,其实占比都是非常低的,大多数的学生都是处于中间的这个良好的这样一个状态。 但是呢,我们可以看到啊,刚才的这个判断流程里,当我们得到一个试卷,一个分数的时候,首先就是要对他判是不是处于不及格的这个区间,而实际上呢,不及格的这个区间占比是非常小的。举个例子来看一下,假如说我们现在有这样的一个学生成绩的分布的情况, 我们可以看到啊,在七十分以上的这个成绩呢,基本上都要经过三次的判断,但是实际上呢,这一部分的成绩的同学占比是最多的,就可以看到这样的话,这个流程整个的效率是非常低的,所以说呢,其实我们就是应该把 这个占比最高的一部分的成绩作为判断的第一个环节,也就是七十到七十九分的,然后其次呢就是这个八十到八十九分的,这样呢,其实也就是一个哈弗曼术的一个通俗的直观的理解了。好,今天的分享就是这样,这是艾瑞斯,拜拜。

什么是哈佛慢数?给定安个全职作为 n 个叶子节点构造一颗二叉数,若该数的带权路径长度达到最小,称这样的二叉数为最优二叉数, 被称为哈弗曼术、哈弗曼 tree。 哈弗曼术是带权路径长度最短的术,全职较大的节点离根较近。在计算机数据处理中,哈弗曼编码使用变长编码表队员符号,如 文件中的一个字母进行编码,其中便长编码表示通过一种评估来源符号出现几率的方法得到的。出现几率高的字母 使用较短的编码,反之,出现几率低的则使用较长的编码,这便是编码之后的字符串的平均长度期望值降低,从而达到无损压缩数据的目的。哈弗曼数又称最优二差数,是一种带全路径长度最短的二差数。所谓数的带全路径长 度,就是树中所有的叶结点的全直承上齐到根结点的路径长度。若根结点为零,层叶结点到根结点的路径长度为叶结点的层树,树的路径长度是从树根到美 节点的路径长度之和,即为 wpl 等于 wel, 一加 w 二 l, 二加 w 三 l, 三加加 wm astersklm。 n 个全职位 i 等于一二 n 构成一颗有安个叶节点的二叉数。相应的叶节点的路径长度为例, i 等于一二 n, 可以证明哈弗曼数的 wpl 是最小的。

通俗理解哈弗曼术原理,在之前的视频里呢,我们已经直观的理解了什么是哈弗曼术,今天呢,我们来看一下哈弗曼术的原理是怎么样。首先我们将这两棵二叉树呢,简化成叶子带全植的形式,那么这个叶子的全植其实就是代表每一个这个分数段的人数所占的比例是多少。 然后我们来明确几个概念,第一个概念呢就是路径长度,路径啊就是在这个树中每两个节点之间的这个分支路径长度呢,就是这个分支的数目。比如说这棵树中啊,根节点到 a 节点,它的路径长度是三,根节点到 c 节点呢,路径长度就是二。 那么一棵树它的路径长度是怎么样的?其实就是根节点到每一个叶子节点,它的路径长度求一个总和,然后我们再把这个叶子间的全值考虑进去,就可以对每棵树求出来一个代全的路径长度。当我们给定了一系列这个代全值的 几点的时候呢,要求得的这个哈弗曼数啊,其实就是这个代权的路径长度最小的一种情况。比如说这两棵二叉数,他们俩的代权路径长度分别是三和二点二,这个其实就是在对一个分数进行判断的时候,他的这样一个判断次数和期望。 那么假如说我们有一百个分数要进行判断,就可能用第一种方法要判断三百次,用第二种方法呢是需要二百二十次。 当这个分数的数量逐渐增多的时候呢,这个效率的差异啊,就会变得明显起来。那么这个哈弗曼数究竟是怎么构造的呢?其实方法也很简单,我们将这一系列带全职的叶子节点呢,按照全职从小到大排序,然后选取前两个全职最小的两个节点, 然后构造一个新的节点,这两个节点呢,作为新节点的左叶子节点和右叶子节点,当然了左边的这个是全支较小的那个,然后这个新节点呢,他的全支大小啊,是这两个节点 全职的总和,然后用这个心结点呢去替代这两个结点,重新进行排序,然后重复这个过程。直到啊这个所有的叶子结点呢,都加入了这棵树中,我们就得到了一个卡弗曼树。好,今天的分享就是这样,这是 everys, 拜拜。

同学们好,今天我们来讲数据结构与算法课程第六章数和二岔数中的哈弗曼编码算法。上节课我们介绍了哈弗曼编码的方法, 在此基础上,今天我们来讨论算法实现。首先回顾一下哈弗曼编码的构造方法。当我们已经根据不同字符的使用频率构造了一颗哈弗曼术,存储于静态三叉链表中的时候, 由哈弗曼树构造哈弗曼编码需要从叶子出发,从下向上走一遍,从叶子到根的路径,每经过一条路径上的分支,就判定求得一位哈弗曼编码值。每个叶子节点的哈弗曼编码 应该是由后向前逐位生成的,当前节点为父亲的左孩子,则当前求取的编码位为零。当前节点为双亲的右孩子,则当前编码位为一。 当由叶子一直走到了根的时候,就逆向完成了一个叶子节点哈弗曼编码的构造。下面我们来看这样的一个例子,这个例子有五个叶子节点哈弗曼数,他的静态三叉链表在左边, 五个叶子的结点分别对应着下标一到五的位置。我们来看全值为七的这个叶子结点,他的下标是一。双亲是七,而七的左孩子是一,因此当前编码位是零。七的双亲是九,而九的左孩子是七, 因此当前编码位还是零。九号节点已经是根了。因此我们知道全职为七的这个叶子节点的哈弗曼编码是零。零。 来看全职为三的叶子节点,其下标是二。二的双亲为六,而六的左孩子是二,因此当前编码位是零。 六的双亲是七,而七的幼孩子是六,因此当前编码位是一, 七的双亲是九而九的左孩子是七。当前编码位是零,九号节点是根,因此全职为三的这个叶子节点的哈弗曼编码是零幺零。再来看全职为五的这个叶子节点,其下标为三,三的双亲为六而 六的幼孩子是三,因此当前编码位是一,六的双亲是七而七的幼孩子是六。当前编码位是一, 七的双亲是九而九的左孩子是七。当前编码妹是零,九号节点是根。因此权之为五的这个叶子节点的哈弗曼编码就是零幺幺, 以此类推,全职为九的叶子节点哈弗满编码是幺零,全职为十二的叶子节点的哈弗特别码是幺幺。至此,我们就求取了每个叶子节点的哈弗满编码。 在认真书里总结上述哈弗万编码求取过程的基础上,我们讨论算法实现的问题。首先讨论 存储结构,算法中求取的每个叶子节点的哈弗曼编码,最后要存储在一种字符数组中。针对每一个叶子节点的哈弗曼编码是由后向前足位求取的这一情况, 在算法中我们另外设置一个自负串,用来暂时存储求取的每一位哈弗曼编码。 当一个叶子节点的哈弗曼编码求取完成之后,我们再把它完整的复制到那个哈弗曼编码字符数组中来看。这个 cd 就是攒存编码的字符串。最后一位设为字符串的结束标志。 在由后向前逐位求取叶子节点的哈弗曼编码时,我们设置一个死大下标指示器,在 求取编码的过程中,时代始终指向的是当前 cd 自负串中已经生成的哈弗曼编码的最前面一位。 当一个叶子节点的哈弗曼编码求取完成,我们就将其复制到下面的这个哈弗曼字符数组中,然后 cd 再去求取下一个叶子节点的哈弗曼编码,求取完一个编码再复制到下面的数组中, 这样就可以完成所有叶子节点的哈弗曼编码的求取。至此,我们给出算法的存储结构定义。由于每个哈弗曼编码的长度不等,因此按编码的实际长度动态申请空间单,要 使用一个指针数组存放每一个编码数组的头指针,所以首先定义这个指针型数组,图中的 hc 就是该指针型数组变量,然后定义 cd 这个自负串。还有四大, 接下来讨论算法。我们来看构造哈弗曼编码的算法函数,其参数传递的是静态三叉链表存储的哈弗曼数以及刚才定义的字福串。指针数组 还有叶子节点的个数 n。 算法开始,首先根据叶子节点个数 n 定义 cd 自负串的长度,这个长度足够用。然后给 cd 自负串的最后 后一位设为自护串结束标志。接下来进入循环,逐个求取叶子节点的哈弗满编码。循环控制变量 i 从一到 n 变化, 对应的是在静态三帕链表中下标为一到 n 的这 n 个叶子节点循环体内。首先给 stha 至出值 n 减一指示的是 cd 自负串的最后一位, 因为前面已经讲到,斯大在整个算法过程中始终指向的是当前 cd 中已经生成的哈弗曼编码的最前面那一位。 c 指针用于指向当前叶子节点, p 指针始终指向 c 的双亲。下面进入循环 求取当前叶子节点的每一位哈弗满编码。当 p 不为零的时候,表示还没有走到根节点,此时要来判定 p 和 c 的关系。 如果 c 是 p 的左孩子,则求取的当前编码位是零,放入 cd 数组中,此大减一所指的这个位置,也就是当前已经生成的哈弗曼编码位的在前面一位。 若 c 不是屁的左孩子,则屁的右孩子求取的当前编码位是一 同样放入 cd 宿主中四大减一所指的位置。当前编码妹求得之后,要把 c 移动到 p, p 再次指向 c 的双, 以便循环求取下一位哈弗曼编码,这个循环一直到 p 等于零,即 c 已经走到了根结点为止。当前叶子结点的哈弗曼编码求取完成。 接下来来申请存放哈弗曼编码的字符数组空间,空间大小由 n 减死大决定, 这是当前叶子也点哈弗万编码的实际长度,申请的空间由 hci 指针指示。 然后我们把 cd 字符串中以四大为开始位置的哈弗曼编码复制拷费到 hci 指针所指的新申请的字符数组空间内。此时一个叶子节点的哈弗曼编码 求取完成。算法进入下一次循环。循环变量爱增值一,继续求取下一个叶子节点的哈弗曼编码。待整个循环结束, n 个叶子节点的哈弗曼编码求取完成之后,我们把 cd 数组释放掉,算法结束。这就是我们要学习的哈弗曼编码算法。 好,关于哈弗曼编码算法今天就介绍到这里,同学们回去可以自己设计一颗哈弗曼术, 走一下这个程序,看看 cd 自付串的求取变化过程,以及最终存放叶子节点哈弗曼编码的自付串数组的申请,以及复制拷贝编码的结果。好,今天的课程就讲到这里,谢谢大家。

好,我们理解呢,如何判定哈弗曼书?那么我们通过一个实力,我们说主要去求他的什么值呢? wpr 值为最小的,那么设计当中里面我们在求的时候呢,我们通过一个实际的案例,比如有这样的一个例子, 有七个带前节点,他的前值分别为这些数值,让我们以他们为叶子节点的前值来构造一颗哈弗曼数 来构造。怎么构造呢?我们一般是要求按照每个节点的左指数的根节点的前指小一或等由右指数根节点的前指的这样的次序来进行构造,并计算他的路径长度,也是 wp 好,那么如何来构建这样的一个哈弗曼术呢?我们一般的思路只从最小 小的根子来进算,刚才我们不是总结了他的规定吗?什么规定?小的要放离根眼还是近呢?离根要远眼就要放到最后面去喽,那么要放到最后面去,我们就先找他最小的, 最终求出来的结果是这样,我先把结果打出来,然后我们再来分析,以后你就要会分析了,那么这一些前职当中里面最小的肯定是哪一个呢?二,我怎么四?那么我就把这两个人构建, 把这两个的构建啊,这两个的构建,那么构成了这个七七的时候呢,再找这里面重新来构建他整个的一个思路,就是像这种思路,依次类推啊,依次类推呀,啊,依次类推好,那么得这个单能理解吗?就是一个一个网的,比如说二跟他 四,他构建一个六,六啊,这个二跟的四跟,呃,二跟的四,这数写错了,二跟到六应该。呃,二跟到四这里应该是几啊?应该是六啊?应该是六。好,六,这里面还有一个是几呢?这个应该是几呢?五,这数写反了,所以这个五又没有了吗?然后这个七还在不在? 呃,主跟到这里应该是六,哈,六当中里面有一个是什么?有一个是五,那我们就把这个五样拿过来喽, 我要拿过来啊,好,这个五跟到六的构建,然后这个时候五跟到六构建呢,以后呢?得到一个是什么?十一,十一的时候呢?仔细观察,特别要注意这个问题地方,那么要说这个没有了,你就把它画掉,七是不是也没有了? 五跟到六没有了,哎,这个地方五跟五没有了哈。五,呃,这个六是新增, 五是这里的,那这两个是没有拉到,这三个没有拉的好,那么我得罪了一个。十一,十一的时候你就要注意了,你千万不要说十一再长哪一个呢?哪七也行,哪八也行, 这两个都行,那么这两个都行的时候我们就重新来构建。这个地方应该是七,这里应该是八,我们重新把它构建,你写七八过来,这个图应该是错了,按一个是错了啊,之前改的时候没改到 啊,在以七跟到八,你看这个地方就对了。七跟到八加起来是多少?十五这样来构建呢 啊,所以这个七跟他八,他就没有了,好构建呢?十五,十六,这两个都比我这个职要小,那我就直接把这两个合并起来,合并起来呢,构成了二十六,二十六又跟这里面的小的哪一个呢?十六,那就把十六过来。那么一般左边的是更小,右边的直呢?是要更大, 右边的脚跟大,所以要把石榴放到左边,每一个都是这样啊,你看他的龟裂,这就是我们构建哈弗曼树的一般的龟裂,你一定要记住这个规裂,来 啊,然后再得到四十二,四十二,四十二里面还有个三十,再把三十得出来,这个就是我们构建的什么哈弗曼术。那么有了这个哈弗曼术,这一期求他每一个叶子节点的前职会求吗?这个,这个都是叶子,叶子的,你都按照的规则蕊家进行得到 雷佳竞得的啊,这就是我们所说构建的哈弗曼术,就这样来构建好,那么有了这个哈弗曼术的构建他的思路,我们最终的作用是要来构建他的哈弗曼编码,那么等一下我们再来讲哈弗曼编码。


已知二叉数的五个页结点全值分别给出,求其最小的代权路径长度。 w p l 值是什么?根据右下角的哈弗曼数构造方法,我们首先构造一颗哈弗曼数出来,接下来就方便去计算它的 w p l 值了, 选择全值最小的两个,我们根据全值小的在左,全值大的在右,从而呢构造一颗形态唯一的二叉数,那这里面是十十二,他们构成二叉数的根结点是二十二,在二十、二十六、 二十一、三十当中,再选两个最小的,应该是十六和二十一,那就在这十六、二十一,他们的根结点全值是三十七, 那这两个我就不要了,在二十二、三十七和三十中间,我再选两个最小的,那二十和 三十,二十二和三十,他们的根结点全值是五十二,最后呢就是五十二和三十七,他们构成一棵二茶树,根结点的全值应该是 八十九。 w p l 值怎么算呢? w p l 等于我们看十和十二, 全值是十和十二的,节点看不到跟节点的路径长度是三乘以三,加上全值是三十的,全值是十六的,全值是二十一的。 这三个节点到根节点的路径分别是长度为二,我们整个求下来是两百,正确答案呢应该是二 b 这个选项。 再来看一道题,是有关哈弗曼编码,哈弗曼编码的前提呢,是要将按照频次作为全职我们算出来的这棵哈弗曼树, 按照左分支标零,右分支标一这种方式给他进行相应的编码。那首先构造哈佛曼术结果是什么给出,大家不再赘述他的过程了, 这个是根节点全值三十六左子数,这是二十一页结点处十,右子数全值十一页结点处一个五,一个全值六。 三十六。柚子树的根节点全值是十五左子数,根节点七,他的左子数全值三,柚子数全值四十五的柚子数 全值是八。按照我们给出的这几个全值,他们都在页结点上,那按照分支我们就可以进行编码了,这里边问的是编码的加权平均长度,那我就将每一个 页结点,也就是说我们的字符,它的编码长度给它求出来,整个求一个和再求平均值就好了。应该是 全职是三,全职是四,全职是五,全职是六的这几个节点,他们的编码长度是三,再加上全职是八,全职是十的这两个字符,他们的编码长度是二,整个的和。我再求一个平均值, 按照咱们的全值是三加四、加五、加六加八加 加十,这个求下来,我们能得到一个相应的结果,应该是二点五。咱们正确答案呢是 b 选项二 b 有关最小代权路径长度以及 编码的加权平均长度,前提都是要构造一棵哈佛曼树,而哈佛曼树如何构造它的算法你学会了吗?


这讲开始呢,我们学习哈弗曼编码算法,我们知道字符、数字以及任何信息在计算机内都是以二进制形式存放的,也就是零一序列,那么编码方式就是字符在计算机内部的存放格式。 哈弗曼编码是科学家哈弗曼在一九五二年发表的一种编码方法。我们首先会简单介绍一下信息编码问题。任何一种编码方式要解决的基本问题 就是在保证准确性的前提下,用尽可能少的零一序列对字符进行编码。编码位数较少,也就意味着编码的效率较高。 那么哈佛曼编码正是为了追求这样的目标而设计的。他的基本思想是根据字符在文本中的出现频率来决定字符的编码位数。 出现频率较高的字符,用较短的编码,出现频率较低的字符,用较长的编码以其得到更少的平均编码位数。编码将字符映射到二进制序列。当然我们人类是看不懂二进制序列的,所以计算机处理过的数据要经过解码, 将二进制序列还原成原始的字符信息。比如说大写字母 a, 它的 ask 编码就是零一 零零零零零一,这个二进制数转换成十六进制就是四十一,那 b 的阿斯 k 编码对应的十六进制就是四十二。信息压缩也可以理解成一种编码技术, 压缩分无损压缩和有损压缩,那么有损压缩会丢失一些不重要的信息,比如说 图像、音频、视频等,为了节省空间,常采用有损压缩技术。那解码得到的信息与原始信息有一定的差别,而对于字符、数字等信息的处理, 通常要求无损压缩,也就是要求能够准确无误的从零一序列中解码,得到完整的原始字符。我们将要学习的哈弗曼编码也可以看成是一种信息的无损压缩方法。我们都熟悉的 ask 码就是一种编码方式, 他是用一个字节的二进制数来表示一个具体的字符,可以对英文字母、阿拉伯数字以及一些常用的控制字符进行编码,比如刚刚我们给出的 a 和 b 的阿斯 k 码。但是对于其他语言来说,像阿斯 k 编码这种单字节的编码 方式是远远不够的。汉字编码标准 gb 二三一二 gbk 都是针对简体汉字的编码,使用双字节编码,支持上万个汉字编码。比如说 gbk 编码方案,对汉字算和法的编码分别是十六进制的 cbe 三、 b 七、 a 八。还有其他一些编码方案,比如说 unicord, 将全世界所有的符号都纳入其中,因为采用固定的编码长度表示每个字符,那么对存属和传输来说 都很消耗资源。 utf 八编码可以根据不同的符号自动选择编码长度,比如说英文字母可以只用一个字节就够了,因此而使编码效率得到提高。
