00:00
各位,我们现在呢,来写一段代码来创建我们的赫夫曼数好不好?那现在打开我们的eclipse,我们来一起写一遍。那我这新建一个包,专门写我们的哈佛万数。到鞋垫啊,写个包包。点和辅。慢。脆没问题吧,哈曼脆。那现在呢,我们写一个对,我们写一个类,注意听写个类,那这个类呢,咱们就取个名字吧,叫homan。哈佛曼去。好的,把它一个主方法给勾上。总方法勾上,那首先我们是不是先应该搞定这个节点呢?就是我们要把这个节点先创建起来。呃,同样道理呢,我们先创建节点,创建这个节点内。这个节点啊,节点内。对。呃,那节点我们怎么创建呢?Node,我们就直接写node node。
01:03
走一个那节点类,大家觉得有什么内容,首先是不是应该有value。这个没有问题吧,他明白了,这个就相当于是节点的权值。就是节点。节点全职。OK,那现在呢,这个节点呢,应该有一个指向左边的。是不是还有一个指向右边的一个指针。我这写一下啊,指向左边。左呃左指数或者叫左子节点。着此节点。之节点。那么这个呢,是指向右子节点。You。又子结顶。又次决定。他每次都会让我选择那。右。子节点。
02:01
好的,呃,那现在呢,我们是不是应该提供一个构造器啊,我就简单写一下好吧,Public什么呢?No,你在构建的时候呢,你给我传一个value进来。就把这个全值给我,那就是this value等于你传进的value。好,这就OK。那写完这个以后呢,同学们大家想一想,我们后面要输出这个节节点的信息是不是。可以。我们可以干什么呢?可以重写一下这个to string。对不对,Two string写一下two呢,我们不打这个na和right。这是他的to string to训完了过后,嗯,一个节点大概的内容就是这些了,就是待会我们要用到这个节点,就这样子的,但是有一个问题,大家有没有发现,你们有没有发现我们在这个地方会比较随大随小。大家有没有发现就是?就是说我们我们会进行排序,排序完了过后呢,你你比如说打个比方,我们第一次是拿到这么一个数组,这个每一个数组的元素就是一个node。
03:12
但这个漏洞呢,它需要排序,它要从小到大排。那从小到大排呢?我们往往会把这一个类实现它的一个comparable接口,理解这意思吧。我要用这个comp接口,所以说我这里呢,我写一句话,大家看看能不能理解啊,这是Java的一个基础,就是呃,为了让为了让我们这个node。漏的这个对象支持。支持什么呢?支持排序,比如说后面我们有用这个connection。Connections,像这样的集合进行排序。集合排序,呃,支持这个排序的话,那么往往我们需要让这个node这个类呢,它实现一个comparable接口,明白吧,所以说让什么呢,让no。
04:04
No,干什么呀?实现comparable这个接口。好,我就把它实现了。同学们。这是Java基础的东西,我就不说那么多了,Comparable。接口那里面放的是什么呢?就是node。对,当我这样这个一写完,我就必须实现一个方法,这个方法呢,就是同学们知道compare to,那这compare to怎么写呢?好,我这样写,我写个叫this value减去什么呢?O。O点八。这句话就是代表对犬子进行比较。好,大家注意啊,如果我这样写,如果我让this value写在前面,把o.value写在后面,这个表示的是将来是从小到大排。啊,这是表示从小到大进行排序,这点是我们Java基础的内容。
05:02
如果同学们这块不会呢,自己去看一下comparable,就是这个接口是怎么回事,好吧,也并不难,如果你想让它从大到小排,没关系,你们在前面加一个负。就可以了。取负就可以了,好吧,那我这呢,不想我我就是想从小到大,所以说我就不在前面取负数了。这点大家清楚,好,这边写完了以后呢,下面我们就可以在这把把这一个。把这个。数组先创建起来,数组同学们刚才已经看到了,我们的数组呢,就以刚才我们分析的。这个数组为例,比如说这个数组。OK。大家看这个数组是我们刚才分析的数组,就是它。那拿到这个数组以后,我们要去创建赫夫曼数,我专门写一个方法啊,就是创建赫夫曼数的方法。那我就开始写了,Public static void。
06:03
那这个方法的名字我们就叫create,什么呢?Half man tree,那你给我传一个什么呢?你把数组传给我,我给你返回。这棵赫夫曼树就完事了。好,首先第一件事情,我们这个数组本身它不,它并不支持这个排序,所以说我先把这个数组里面的每一个元素取出来,构建成load,然后装在一个list里面,大家知道我在说什么吧,就我们第一步要做的事情。第一步我们先啊。第一步。第一步,为了为了操作方便。操作方便。我们先做这样几件事情,第一件干什么呢?我们便利奥这个数组听清楚了啊,第一件便利便利的时候呢,我们第二件事情将将。
07:01
O的每个元素,哎,注意听这啊,O的每个元素。构建成一个no。这大家知道这这意思吗?构建一个load,第三步将它放入到将这个node。放入到二历史中。R list中,那有些同学老师你为什么要这么做呢?因为or list,如果我把这些语言素放在list里面去过后呢,我便于管理,待会我要对这个呃里面排序,我直接用集合操作就可以了,明白我的意思吧,那我开始做这个事情了啊,那首先呢,我们先创建一个r list。啊,我叫notes,等于什么呢?各位同学六、are list里面放的就是node。这个大家看能看懂啊。那当然这个时候呢,我们需要引点引爆。引进去就可以了,那这个做完了过后,我们就开始遍历这个数组,那遍历的时候呢,我们每次取出来是一个value,这个大家看能不能解。
08:10
好,这块呢,我们可以格式化一下。那每遍历出来一个value,我就将其创建成一个数组,呃,放创建成一个漏的。这个对象把它放进去,那就是note第ADD什么呢?六一个大家看这个人看不懂啊,能不能看懂load,然后把value放进去就可以了。懂吧,也就是说经过这个便利以后呢,我的每一个元素就变成一个no,并且放在了。奥瑞利斯中。好,这个就说完了,说完以后。按照我们刚才。做的这个流程是不是先要。排序啊。是先要排序好,那我就不啰嗦啊,我就先排序。排序排序呢,我们是。从小到大,这个从小到大取决于你这个地方是怎么写的。
09:04
刚才我讲了,如果用this value减o.value代代表从小到大,反过来就是从大到小,那我怎么排序呢?我直接使用一个集合。Connections。C。点它这里面有个方法叫short。刚好可以放list进去,那这就叫notes。明白意思吧,就是。排序出行。排序水,刚才我们讲了,你之所以这个呃,能够把这个note放进去,是因为你的这个你note。放的是,呃,里面放的是node,而node呢,它实现这个接,如果你把这个接口拿掉,这张是不支持的啊。好,我们排完了,过后我们先来玩一把,看看是不是跟我们想的一样。好,为了让大家看的比较清晰,我弄我一步步的走,好吧。好,同学们,我现在呢,给大家调用一下create。哈曼,把二放进去,好,同学们,我们先运行一下,看看情况跟我们想的是否一样来运行,我们发现拍完了过后的确是1367。
10:13
83。29。是这样子的,你给的顺序是十三七八三二九六一,但是经过处理过后,人家已经变是是有序的,这个没问题吧。也就是说,从小到大,这个事情就做完了。那下一步你该干什么了,是不是取出?根节点全是最小的两棵二叉树啊。对不对,这个怎么取,同学们。怎么取,按顺序取吗?你已经是集合了,也就是说你现在已经排序了,是不是我先取出第一个,好,我们先写出啊。第一步,取出。好。第一步取出什么呢?取出全值最小的这一个啊,二叉树节点。
11:01
但这个节点其实就是一棵最简单的二叉树,你这个节点就认为是个二叉树啊。二叉树,因为我们讲过一个节点,也可以看成是一个最简单的二叉树,这个能知吗?能知道吗?好,那现在写了啊,No。因为我取出来最小的呢,将来会构建,构建的时候会变成我们新的二叉树的。呃,左边这个直接点是这意思吧,所以我写个na。等于什么呢?用not.get几呢?零就完事了。没,没问题吧,同学们好。那第二步我们是不是应该再取一个,再取出次小的这个节点。取出次小,呃呃,第二小的吧。取出这个第二小的,第二小的。这个节点也是一个二次数,那这个呢,一样,我们写个no,应该是right,等于什么呢?not.get几啊,GET1能理解吧。
12:04
就一个零一个一,咱们就写完了,取出来过后,是不是第三步我们就应该构建,构建一构建什么,这构建一颗新的。二。差数。那怎么去构建一个新的二叉树呢?好,说白了就是这么去写就可以了,就是no。No,然后呢,我们写个PI等于什么呢?各位同学是不是等于六一个no的,然后呢,这边是left点。我们的value。然后是right。点我们的value。是不样子,同学们也就是说你,呃,这个地方我们看看是有什么。问题啊。大家看这边有什么问题6NO。呃,他这么只有一个字。好,我们看看这个问题啊,那应该是加才对。
13:02
是不是加才对呀,就是你把左边的就是左边这个值,呃的呃,左边左指数的。呃,它的全值和右指数的权值加起来形成。我们负节点的全值是这样子吗?同学们,那这个地方呢,要挂起来了,你得把它挂上,就是parent的点,它的什么left就等于我们left这个节点。是这样子吧。其实你你这也可以写成这个left node,这样也可以。啊,这样写应该更好一点,是不是left loadde,这个是right loadde,是不是这样子更好一点,那当然下面呢,我们也写成left node,这边写成right load,好吧,那这边就left指向我们left load。是不是这样更清晰一点,然后parent的什么呀。Parent的right。这个指针指向它的right这个node。
14:02
这个代码就写完了。好,代码写完以后呢,不要忘了一件事情,你你得把原先这一个na node和right node干掉。这个能能理解什么意思吗?因为你想你现在已经。你现在这两个已经用过了,肯定要把它删掉,说我们第三步下面这一步删除掉。从什么呢?从我们中中啊,List中,注意听list中删除。删除。删除处理过的这个二叉树。是不是?那怎么删除呢?Very easy就直接使用我们notes.remove就可以了,Remove谁一个是node?对不对,一个是漏字点right remove,我们的right load完事。那么把这两个删除过后,你不要忘了,还得把这个parent再加进去,因为它是个新的,要加到我们这个录制去,好第下面这一步。
15:08
下面这一步呢,我们要做的事情是将。将什么呢?将这个parent加入到我们的note。因为你你删了两个,你你这个新构建的二叉树又成为我们的成员了,是这意思吧,那这个也很简单,老点干什么呀,我们的爱。把这个加进去就可以了。哪个呢,Parent。各位加进去,加进去过后是不是我们这个事儿就成了,然后你你把相对说你现在第一件事情已经已经做完了,各位朋友,也也就是说到此为止,你的第一件事情就已经做完了,我们来看看是不是这样子的,来朋友们我们捋捋好,现在呢,我说一下啊,第一次处理后,我们看看目前我们这个node是一个什么样子的,当然我要排下序了啊,还要重新排下序,你不排序看不到这个效果对不对。
16:01
好,我这帮我肯定又要排下去才能看到效果啊。好,现在算了,这我就先不排序,大家看一下就行了。出好,各位同学,我们来运行一下,这是还没有处理之前,这是第一次处理过后,我们看结果运行一把。好,同学们可以看,第一次没有处理之前是136含顺序来到29,大家看,当我处理完了过后,六七八十三,29。然后后面有个四,这个四是怎么来的呢?441和三处理过后的今年,那为什么他在最后而没在最前呢?因为你在这个地方做了一次,你就没有处理了。是不是,所以说我们现在呢,要循环处理,怎么循环处理,同学们是不是我们这个处理过程。我们这个处理过程是个循环的过程。我们处理的过程是一个循环的过程,那也就是说在我们这分析的第四步,将这个新的二叉树再次排序,然后再重复12345A1234这个步骤。
17:05
直到所有数据处理完毕,那我问大家什么时候是处理完毕?什么时候是不是这样子的,只要我们因为你在不停的remove remove remove,我问大家到最后处理完毕过后,我们这个note。这个list里面有几个节点。其实只有最后一个节点,因为你不停的加U3加三加三,最后就形成了这样一个东西,也就说在你最后这个or里面只有67这个节点,能理解吗?因为你不停的处理嘛,所以说我们这个处理的过程呢,应当是这样子的while循环,只要。只要我们的这一个。note.size它大于一,我们就可以处理。直到它等于它等于一的时候,这个条件不成立,我们就退出了。大家能理解吗?这个while循环啊,Y循环。
18:01
好。然后这边呢,我们把它格式化一下,待会就写完,写完过后同学们你最终返回的是这个赫夫曼数的头就行了,好最后返回最后这个节点,也就是赫夫曼赫夫赫夫曼数。的这个这个root节点。是不是root节点,因为你想嘛,最后就变成这样一个玩意儿了,那怎么返回呢?其实非常简单,就是return我们notes.get0就可以了,因为零就是最后一个,当然你也拿不到别的了,只有最后这一个好,返回过后我们这边就不要是VO了。我们应该是接收到它的一个节点,是这样子吧,说错最后漏。代码就行了。也就是下面呢,这段代码就是整个对赫夫曼树创建的一个过程,那现在我们就创建完了,那创建完了你怎么证明你这一颗赫夫曼树创建创建成功了呢?各位同学是不是我们应该测试一下。
19:06
是不是应该测试一把,对不对,那测试一把,最简单的方式就是我们用前序遍历,遍历一遍看看对不对就可以了,来,现在呢,我写一写一个,呃,便利的方式,好吧,我省点事,直接在这写。好吧,我在哪里呢?我就在这个no里面,我写一个。写一个什么呢?前序便利,前面我们已经学过这个东西是吧,前序。情绪便利。便利,OK,嗯,这个很简单,我们前面讲过,我就直接写了啊同学们那就不多说了,Public void什么呢?Pre order是不是讲过这个前序便利,那前序便利你怎么前序便利呢?好,我上来过后先输出这个节点。是不是输出这个节点,如果这个节点的左边左指数它不等于空干什么,我们就去他的左指数继续进行一个前序编历,那么写完。
20:09
OK,如果它的右边。它不等于右边的这个节点,子节点不等于空,我们就进行右边的一个继续,呃,这个前序遍历,那么就写完了。是不是好,那现在我在我在这个地方再写一个方法来调查一下,好吧,这就写完了,在这里我们写一个什么呢?呃,编写一个情绪便利。便利的方法。好,那咱们就这样写,Public static void。Order OK,那play order呢?这个时候咱们要写这个方法其实特别简单,你只需要干什么呢?你只需要给我传一个赫夫曼数的根节点就可以了。是这样子吧,你把根节点给我,你把根节点如果我判断,如果根节点它你传进来不等于空,就说你的确是有一棵树的,那么我直接就用root点它的order就完事了。
21:13
否则呢,我提示一句话,说该赫夫曼树是空诉。是不是或者说这棵树是空树也可以,就是树是空树无法便利,是空树不能变立大么就写完了。好,呃,现在呢,我们来玩一把啊,我就。好P,现在呢,我把这个节点拿到no,它返回的呀,就是这棵二叉树的根节点。是这样子吧,我们这是不是写的这个方法,我把这个做一个注释。好,这个是需要创建成和。赫夫曼树的,赫夫曼树的这个宿主。而返回的是什么呢?返回的是创建好后,诶创建好后的这个后夫曼数的。
22:09
Root基地。是这样子吧,同学们注册几点好,现在呢,我们拿到这个地方我就测试,怎么测试呢?非常简单,我就play out,然后把入的传进去,好,同学们,我们先不要去输出,我们先自己算算。这个前序便利应该是什么样的情况?打开这个地方,我们来推一推。我们来推推,那他这个情绪便利的话呢,应该是这样子的。应该是29。啊应这应该把666,那这个就是67页给输出来了,这个还有点复杂啊,这这这太多了,这个内容啊,那第一个就是67了。是67吧,67完了过后,他的这边这边没有就是29。对不对,29完了过后走这边38。
23:01
呃。38,嗯,这个太多了啊,我就要不我就我就不去不去走一份了,太太长了,我们看一下就行了,只要把前面两个差不多对就就OK了,应该最前面肯定是67对吧,最后变到这边来,应该是13嘛,大概是这样子的,因为他是先左左边完了过后再去打自己,应该最前面是67,最后是13,差不多就可以看出来是不对的,好吧,我们运行一下。好看一下啊,六十七十三应应该是对的,你看啊,这个顺序67,第二个是29,看对不对。第二个是确实,呃,29 29完了过后呢,往下面打,往下面打的时候,呃,前驱便利,所以说。啊,前序编的是六十七二十九。呃,那就这个就应该是38了是吧,第三个是38对不对。38对的下一个是15对的再下一个是七。
24:00
再下一个是七正确,再下一个是八,因为七完了过后就打这边八,八完了过后38,一打完就是23,八后面是23。正确23下面23下面是十十下面是四对吧,四打完是一十四一对不对。十十十一正确,最后是三三就是这个节点了。对吧,这个节点完了打六三过了463过了16,六六完了过后,六完了过后是13正确啊完完全正确,跟我们跟我们输出这个是完全一样的啊,同学们好,到此为止,同学们,我们这一颗不要这个了啊,我们这一颗赫福曼树就创建结束了。大家看看能不能理解。把代码呢,也不是特别的难,对吧,看虽然说老师写了很多,但是呢也不是特别难,我再说一遍,如果各位同学,如果我们把这个数。啊,我们要,因为我们要创建这个后夫曼数,就是按这个流程来的,如果你你这个顺序变了,那你这边代码要做相应的调整,好吧,这个调整我就不去再说了,那调整的话,那你应该取的时候,这一门就不能取零,这边也不能取一,这个零应该是取的我们。
25:14
这个数,这个列表里面的倒数第一个,这个一取的是我们列表里面倒数第二个,明白这意思吧。好,同学们,那关于赫夫曼数的代码呢,实现我们就聊到这里,现在我把代码,我把刚才讲的内容啊,给大家板述一下啊,板述一下刚才我们讲什么东西了呢,各位朋友。刚才呢,我们讲的是赫夫曼树。是这样子吧,先把赫夫曼数的内容给大家板板一下。走第一个怎么讲呢,这块内容呢,首先我们对赫夫曼数做了一个基本的介绍,能理解。做了两点。多两点说什么是赫夫曼数?啊,说白了就是树的带权路径的WP要达到最小。
26:01
那么我们就称之为。二最优二叉树,当然这个,呃,我们说的是二叉树啊,赫夫曼树,我们指的都是这种二叉树啊,那还有几个叫法,除了赫夫曼,还有哈夫曼,或者是这种赫赫夫曼也是可以的。好,这是基本介绍,那基本介绍讲完了过后呢,各位同学我们就给大家。说了一下赫夫曼数的几个重要的概念。是这样子的吧,我们捋捋思路,我们讲了哪些重要的概念呢?首先给各位同学说了一下路径和长度的概念。路路径和路径长度概念什么叫路径?就是从一个节点往下可以达到他的子孙,孩子或者孙子的一个通路,称之为路径。什么叫路径长度呢?好,路径长度。这写的有。啊,通路中分支的数目就称之为路径长度。对吧,好,这是我们说的第一点。那这个说完了过后呢,我们又讲了节点的权和带路径的长度。
27:07
决定的权我就不说了,带权路径的程度指的是什么呢?就是这个意思,带权路径的程度。就是节,应该说是节点的带权路径的长度,指的是从根节点到该节点的路径长度与该节点的全的乘积。好,这个刚才也讲过啊,后面呢,为了再把这个讲清楚一点呢,我们又说提出了这一个数。就是什么是数的带权路径。和WPL是什么?那么数的带权路径是它的所有的叶子节点的带全路径的长度之和。这个就叫数的带权路径,那么也记为WPL,这个WP2最小的呢,这个二叉树就是最优,最优二叉树。啊,最右二三数,也就是我们的和服曼数,好,为了把这个说清楚,我这里呢又给了几张图。
28:03
让大家体会,就说哪种,就说你给的这些节点其实有很多组合形式,但这个就不是赫夫曼数,这个是,这个也不是。也就是说这个是对不对,因为这个人是最小的。这个最小的,好的,我把这个呢给大家拿到这里。再说啊,一定要知道是所有叶子节点的,那也就是说你在构建的时候呢,它的节点都在叶子节点。对不对,好,那这个说完了以后呢,同学们,我们就说一下赫夫曼数它的一个创建的一个思路是怎么样子的,是这样子吧,同学们说给一个给了一个数列,怎么去把它创建起来。那么首我在这里呢,为了让他听明白,我们就整了一个实际的案例给大家讲的,那这个案例呢,其实就在这一步一步的讲出来的,是这样子吧,好,我把这个呢给大家写到这里来。好,思路就这样整理起来的。
29:00
呃,构成赫夫曼数的一个步骤一共有这么四步,这四步呢,就是一个反,就是反复的一个过程,或者叫一个循环的过程。这点大家要清楚,最后呢有个图解,这个图解我就不画那么多了,同学们我就把最后。把最后这个图给大家拿过来就行了,因为你太多了,我也我也没办法一个个截就把这颗给他拿拿过来好吧,也就是说你自己要去测试的话呢,你要以这你要你要构建成这个数才是赫夫曼数,就是上面。这个数组对应的赫夫曼数长的就是这个样子的,好,最后呢,我们用代码把刚才讲的这个思路予以实现。是不是这样子的代码。代码实现了一把,最后我把代码呢给各位同学板书到我们的笔记中。代码就是这段代码。OK。好同学们,我把这个呢给大家放在进来完事了,好同学们,那关于赫夫曼数的这块的内容就给大家讲到这里,那么下面呢,要给大家讲的就是我们的赫夫曼编码,一般来讲大学里边。
30:11
讲到这个后半数也就不讲了。呃,但是客服曼编码呢,其实在开发也是经常会使用到的,所以说我们对客服曼编码也要做一定的了解,到时呢,我们把这个程序就是把这个不是了解啊,不是简单了解,我们把赫夫曼编码用代码给大家实现,这样呢,大家。就在学习的深度上有一定的保证,面试官问到赫夫曼编码的时候呢,你也知道诶,咱们怎么用赫夫曼编码来完成我们数据的压缩和解压。至少你对。压压缩文件和减压文件,有一个就是有个什么,有一个底层,底层这个层面的一个认识,他到底是怎么玩的,对不对,有一个了解了,有一个认识,好,那这块我们先给大家介绍到这里。
我来说两句