00:00
各位,刚才呢,我们给大家讲了一下什么是赫夫曼数,简单的讲就是WPL最小的这种二叉素呢,它就是赫夫曼树,那下面呢,我们来看一个题,这个题的要求是这样子的,说给了你一个数列。这四个这个数列呢,一共有这么七个树,要求转成一棵赫夫曼树。把这个功能给实现了,那首先呢,我们还是老规矩,我们先不写代码。我们先把这个思路分析一下。我们先看一下构建赫夫曼数的一个步骤是什么样子的,大家先来看,跟着老师思路动一动啊。首先第一步先从小到大把这个数数列进行一个排序,那么每一个数据呢,就看成是一个节点,而每一个节点呢,就可以看成是一个最简单的二叉树,也就是说有一个节点。那么这个节点呢,它的左子节点和它的右子节点分别为空,那么这个时候呢,就是一颗最简单的二叉树,能理解好,那么现在第二步取出根节点全值最小的两棵二叉树,因为你刚才已经排序了,其实说白了就是最从这个序列的前最前面取出第一个和第二个,因为你是从小到大,从小到大排的嘛,好排完呃,取出来过后呢,组成一个新的二杀术。
01:20
那么新的二叉树这个根节点的全值就是前面两棵二叉树根节点的全值之和,明白我的意思吧,好,把它加起来吗?然后再将这颗新的二尔法树以根节点的全值大小进行再次排序,就重新再排一次,再排一次过后呢?又从这个新排序的这个序列里面再挑出两颗最小的二叉树,再进行组合,也就是说不断的重复1234的步骤,最后什么时候结束呢?就是直到我们整个数列的所有数据都被处理过,就得到一颗赫夫曼树,就是这样一个流程,那同学们有没有?呃,理解呀。
02:01
那可能是,如果仅仅是从文字来讲呢,大家还是不太清晰它到底是怎么做的,下面呢,老师给大家画一个图。画完这个图过后,你就真的理解他的一个创建的步骤了,然后我们再用代码实现就完事好不好?同学们,现在呢,我们打开Excel表。我们来写一下,就是如何创建。对如何创建E构建啊构建。构建一棵什么呢?赫赫夫曼树。的一个步骤。问题吧,啊,那么这个步骤呢,刚才老师我我已经在这简单的说了一下,他的步骤分为四步骤,我先把这个步骤呢给同学们拿到这块来,一会儿我们把它整理一下。好,第一步该干什么呀,先排序。第二个排序过,取出根节点最小的两棵二叉树。第三步,构建成一个新的二叉树,这个新的二叉树的它的根节点是选出的两颗最小二叉树的根节点之和。第三步。
03:09
再去排序再选啊,这是呃,下面第四步了,就是再将这个新的二叉数呢,以跟进的全值再排序,排序过后再。再从排序过后的数列里面再挑,再选两颗最小的二叉树,再进行组合,以此类推,最后呢,什么时候结束,同学们?就是数列中所有的数据都处理过,就得到一颗赫夫曼树,好,现在呢,我就以这个数列给大家进行一个演示,好的。那同学们看。我往这边挪一下啊,各位同学,假如现在呢,我这有一个数组啊,或者叫数列,它先排序,排序过后变成什么了,变成一。三。六。七。八。
04:00
13。还有个什么29。大家看我这写对了没有啊,136。七八十三和29好,没问题。那排序过后呢,我们现在就开始按照它的步骤来走,首先取出根节点全组最小的两颗二次数显然是一和三好,现在呢。我挑出一和三。这个没有问题吧,一和三好,这是第一个一。好,再再选一个节点二啊,再加一个节点三。那这两个呢,各位这两个这两个呢,他们构建成一个新的二叉树,它的新的二叉树的根节点的全值就是一和三的和。好,我们把它标起来。好这个这样子就处理完了第一步,那这个新的这个二叉树的根节点的全值是四,它处于这个数序,这个原先这个数列里面的第几位呢,又在第一位了,所以说他后面呢,还会有六七八十三和二十二十九。
05:10
好,这这个时候我们再调出四和六是不是好,我这画个线啊。呃,画一根线的代表是我们的下一步的操作,这样大家看的比较清晰一点。那现在呢,四和六挑出来好的没有问题,那现在呢。我这样来挑。嗯,我。我把这三个,我把这三个三个拿下来,待会我要用。好拿下来以后呢。我们让他跟六号。这个节点进行一个组合。好六,那六号组合以后形成的这个新的二叉树,它的根节点全值就是它们两个的和变成十了。这个没有问题吧,同学们。好,也就是让这个十呢指向四,它的左子节点指向四,让它的右子节点指向六,好。
06:04
六点一般来讲呢,我们可以让左子节点指向值较大的,让右子节点指向这个全值较小的,但是这个不是必须的啊,各位同学不是必须的。好的,嗯,那么十做完了过后,大家可以看到七和八就会在它的前面,是不是因为你再排序七和八要小嘛,七和八排在前面,13和29排在十这个节点的后面,这个理解吧。没问题吧,现在我们继续挑,现在应该挑哪哪两个点呢?是不是挑七和八这个理解吧,因为七和八小啊,好,七和八我们再次进行一个。进行一个组合,好往这写。那下面呢,为了省事,我就从这边挑出三个节点,我用用。好往下看,那这个时候呢,一个是七。各位,一个是七,一个节点的值是八。
07:02
那么它组合起来这个值就是15,没问题吧,那我们看看15处于。什么位置,是不是实在它的使这个节,使这个二叉树。就是根植的全,它的根节点的全值为十的这个二叉树应该排在他的前面。这个能理解吧,因为它小嘛。对吧,排在前面。排在前面呢,后面仍然是有13和29,诶13不对啊,这个13就在。时尚就在这儿了,同学们。实际上就在十和15的之间,这个能理解吗?那29呢,排在20,呃,十十十五的后边,好就变成这个样子了。是这样子,好,那这个时候同学们可以看到十和13是较小的,是他们两个组合,那我现在省点事好吧,因为我现在就不想继续往下面再拷贝了,那这边。
08:01
就有一个13这个节点看清楚了啊,13这个节点呢,它和十进这个组合就会形成一颗新的二叉树,这个新的二叉树的全值呢,就是多少呀23。好,23,那同样我们让23它的左子节点指向十,让23这个节点的右子节点指向15 23可以了。那同学们再看此时此刻,23。15和29谁的?他们关系是什么样子的?是不是15这。就应该。移到前面去。29在这个位置能理解吧。现在是不是15和23可以进行一个组合。没问题吧,因为15和23比,呃,是最小的嘛,好,现在呢,我把它拎上去。怪,这个应该很简单,好,这个地方我们就形成了一棵新的二叉树,呃,15加23等于多少?同学们是不是应该等于38呀?好,38,同样我让38这个节点呢?
09:08
指向它的左侧节点指向15,它的右侧节点,各位指向23没问题吧。现在没有什么可说的了,只有38和29了。但29呢,它较小,所以说把29排到前面去。好,那现在。最后一步了啊,那就说29。把这个29。29和38进行一个组合。那这边就是我们的29。好组合和好像是吧,那这个这边太窄了啊,这边太窄了,我我把它选一下,我它挪挪到这边来好吧。往那边挪一下,因为太窄了,好29和38进行一个组合,各位。形成一个最后的这棵二叉树,那29加上38等于多少呢?等于67。是这样子是吧,同样我们让67这个节点的左子节点指向29,让67这个节点的右子节点指向38完成。
10:09
同学们,这就是一棵什么树啊?就是我们所说的赫夫曼树,大家可以去算一下,这棵赫夫曼树,它的全职就是WPL是最小的。WPS最小的,那同学们关于我们这这个赫夫曼数,它的一个构建流程,就是用一个数列来构建一颗赫夫曼树的思路图解就给大家讲到这里,大家看能不能理解。其实特别简单,其实就是我们这说的这么12344步反驳的一个执行。反复的一个执行过程就完事了,好好同学们,那这块呢,我们先这块我们先讲到这儿,下面呢,我们准备用代码来给大家实现一把。
我来说两句