00:00
各位,我们下面呢,用一个应用实例来讲解顺序存储二匝数的一个实现,大家看这里需求,需求非常的简单,给你一个数组,1234567,就跟刚才我们看的数组一样,要求以二叉数前序便利的方式进行便利,那么便利过后这个结果呢,应该是1245367,待会儿我们要验证一下,好,现在呢,我们就不说废话,我们直接上代码了,好吧,这个比较简单,我就直接写在这里,我写一个类。这个类呢,我们就取个名字叫二位数组的。Binary tree。DEMO,那就是说以数组的方式来存储我们的这个二叉数,并且完成编定。明白我意思吧,把主方法勾上。把主方法勾上,OK。那怎么写呢?首先我要把这个数组定义下来,等于各位,这个呢,就是一二。
01:00
34567。格式化。好,前面我们忘写了括号。就写完了,那写完以后呢,现在呢,我们来写一个类啊,我们编写一个r binary tree啊实现什么呢?实现这个顺序。顺序存储。呃,存储这个二叉树。二尔塔的一个便利啊便利,那现在咱怎么写呢,写个glass。先写一个class,就叫a binary tree。对吧,那我为了保持一致,干脆我们就叫AL跟它一样啊,跟它一样,那首先你这个数里面肯定有有一个数组吧,那么就写一个数组int。这个同学们啊,这个就是存储存储数据的。
02:00
存储数据的这个数组相当于是存储我们二叉树节点的那一个数组,明白吧,存储数据节点。哦的是一个数组,很好理解。那么我们在这做的时候,肯定有一个构造器吧,构造器让别人把这个数组传给我们,这个能理解吗?就是相当于说待会你要把这个数组传给我,然后我完成遍历就可以了。是不是好,现在呢,我们来编写方法。编写一个方法,OK,方法完成,完成什么呢?完成顺序就是完成这个顺序完成。这样写啊,顺序存储。存储,存储二叉数。二叉。数的一个情绪便利。前序遍历能理解,因为你现在传进来这个数组呢,已经是按照这个顺序存储的,现在我们就完成他的一个前序遍历,那我开始写代码了,Public VO什么呢?Pre order。
03:11
是不是前序便利,然后呢,你要给我传的是什么呢?显然是index,这个index就是类似于刚才我们所说的这个N。这个N当然我写成N也可以对吧,但是我这还是写着index,我说一下。那这里面这个index表示什么意思?同学们,这个index就是表示它是数组的那个下标。就是数组的下标,数组的OK数组。数组的下标。能理解,就是刚才类似于我们刚才分析的这个N,因为待会我要用到这个特点,好吧,叫index更更准确一点。好的,那现在呢,我们就来判断判断,如果注意听见啊,如果数组为空,为空或者什么呢,或者index它。
04:01
数组为空,就是数组你传进来什么都没有,或者我们这个数组什么呢R。Or点认等于零。等于零,那就是你虽然有个数字,但是里面一个数据都没有,我们就不要便利了,所以是吧,为了安全,因为你在便利的时候,它不停便利,它会它会有这么一个情况,所以说我们先判断,如果为空或者什么呢?r.NS它等于了等于了零,好,那么我们就不要再玩了,就提示一句话就可以。来,我把这句话打出来。那句话叫什么呢?这句话叫做宿主为空。数组为空干什么呢,不能。不能。按照按照二叉树的,二叉树的前序便利,因为你都空了,怎么便利呢?那这个时候我们就不要走,那如果没有问题的话呢,我就把这个当前的节点打出来,因为你是前序便利,是不是先把它打出来,然后向左边再向右边啊,是不是那就打印了啊R。
05:05
Index,也就输出相当于说输出当前。当前的这个,呃,这个数组。嗯,元素啊,就输出。输出当前这个元素,因为我们前序便利呢,总是先输出自己,再向左和向右嘛,对不对。就输出这个元素,那输出完了过后呢,我们就要判断了啊,现在呢,我们要向左。向左递归,递归便利,是不是因为我们前前你首先要明白什叫什么叫前序变利,前序变历是先把自己打出来,先向左再向右,是不是这个道理啊,那现在我要判判断了,你按理说我们加一个pray就是。按理说我们这样写就可以了,但是你看这样写有没有问题啊,不,因为他左边的大家看它边的这个直接点是2N2乘以N加一,也就说其实我们这把这个带过去就可以了。
06:09
Index就可以了,但是你这样写呢,有一个问题,假设这个index越界怎么办呢?是不是,所以说这里面我们要有一个条件加进去就OK了,怎么样呢?就是如果我们这个index乘以二再加一个一,它怎么样呢?它如果小于了r.OK这时我们才可以。向左地柜,如果说你这个都大于人家了,那肯定不行。是不是你大于别的那就不行,至少它小于嘛,比如它最大也就是二点减一,你才能这样去吧,所以如果它小于二点认十的情况下,可以向左递归,同样的话,同样我们还是存在一个向右递归,因为左递归。便利过后向右递归,向右递归便利试一试吧,同学们,那同样的道理,我们也要加一个条件,向右递归呢,它也要满足index乘以二加上一个二。
07:11
也要小于R点认识。是不是仍然要满足你不能越界吧,你不能越界,在这种情况下呢,我们仍然可以去调用好,这时呢,就应该是二乘以index。啊,二乘以index再加一个二就可以了。是不是,当然indexx写在前面也是可以的,这就写完了,就写完了,那写完以后呢,我们来便历把,现在其实就已经可以便历了,实这样是吧,那如果便利的话呢,首先我们创建一个。Are binary tree。这样的一个对象,Tree放进去,把数组给它扔进去了吧,好,然后呢,我们生成这么一个。二二十二岁的对象,然后我们可以遍利便利的时候,是不是这样变利就可以了?二瑞。
08:03
But tree点。Pray,那传什么进去呢?各位同学想想传什么进去是不是按照我们这个数的一个结构来讲,我们应该是从它的根节点,那么根节点的下标其实是零,能理解吧,所以说这时呢应该是输入零,那如果按照前序便利,它应该输出什么呢?我们来看一下是不是应该这样输出的先是。一比如说一先出来,一出来过后呢,像他的。这个右边。呃右边呃呃左边左边左边就把二输出来了,二输出来过后再把这个四输出来。射出出来过后呢,在这个点上往他的。呃,这个。右子数那就是五五完了过后呢,这个已经输出了,像他的,嗯,右子数这边走,右子数先把这个三输出来。
09:01
三输出来后呢,又往它的左指数,左指数下面这个六没有了,就直接把六输出来,六输出来过后呢,回到这个三这个节点的右指数啊,新式左数,现在右子数了七,那就应该是1245367。好,我们是1245367,看看是不是啊一。二。是。五。三。六七这个呢,跟我们刚才分析的这个顺序看看是不是一样的。刚才我们分的1245367正确,也就前序便利呢,应该是这个顺序才表明我们的代码是写的正确的,否则代码就需要调整来运行一下。那运行完了后呢,我们看一下结果是1245367 1245367,跟我们想的啊分析的一样的,1245367,完全这些啊再看一下。再运行一下啊,别写别写错了,1245367正确,1245367正确的好,那这样写的太麻烦了,因为你每次传一个零进去显得不是很方便,所以说我们一般呢,会重载这个方法。
10:10
我们重载一下,重载哪一个呢?Pre order这个方法想的简洁一点,你看我这样写啊,Public贸易的。Order or DR,然后怎么重载呢?我们在这里面直接调用pre,把这个传个零,诶这样呢就感觉更干净一点,对吧?一般代码里面都会显得简洁,这时我们在调的时候就不要传这个零了。直接说我要进行全区编利,至于你你从哪找,那你把代码写到这里面就完事了,是吧,我们再运行一下看效果对不对。是不是还是1245367是吗?同学们好,各位,那么关于我们这一个顺序存储二叉树的一个讲解呢?呃,大致就是说到这儿。那么我还要多说一点,顺序存储二杀数,好像看起来说叶老师没有感觉到它有什么用啊,其实它是很有用的。
11:05
啊,它是很有用的,就是顺序存储的应用案例本身现在应该讲。应该给大家讲,就说顺序存储二叉树呢,他在八大排序算法中有个叫堆排序的,就会用到顺序存储二叉树的这个特点。但是呢,因为这个堆排序它是属于二叉树的一个实际应用,所以说我们把堆排序呢,放在数结构实际应用这个章解为给大家讲解,能理解我的意思吧,所以这块呢,我们先不着急,但是呢,大家不要觉得顺序存储二招数没有用,它这其实很有用啊,很有用。第二个呢,还要给大家说一下,我这里给各位同学写了是。呃,顺序存储二叉树的前序遍历,前序遍历,那么我要求同学们按照老师这种方法模拟一下,把他的中续和后续遍历写出来,难不难?其实一点都不难。
12:00
是不是你就照着老师这个代码稍微改吧一下就行了,我这已经写的差不多了都。这个条件不用改,你就是把这个顺序调一调就可以了,理解吗?我这个就不去讲了啊,你要说这个还做不出来,有点不好意思了,因为前面我在讲竖的前序,中序和后序,其实讲的比较细致的,那这块呢,我就不啰嗦了,把这个任务交给你们。好的,我把刚才讲的顺序存储二套数呢内容给各位同学板述一下,来走一走。好的,嗯,那么这块就属于顺序存储二叉树,我把讲解的内容给各位朋友板述一下。来吧,顺序乘数顺序存储二套数怎么讲的呢?首先我们先。给它的概念,给他做了一个介绍和一个图,是不是来走一个。先给同学们说了一下顺序存储二叉树的概念。然后呢,对他做了一个基本的说明。
13:01
是不是同学们那这块呢。OK。这块我们有一张图给大家看一下。嗯,顺序顺序存储呢,要求是其实就说数组可以转成数数呢也可以转成数组啊,这就是他的一种转换,那转换的话呢,这有一张图,我把这个图给同学们拿过来。是我们画的这个图,这个图呢,比较形象的说明了这两者存储的关系,说白了就是你的数呢,按这样存,但是我我就按什么呢,按照这个顺序,1234567顺序给你存储,但是存储完了过呢,我却要求以这个前序,呃,以数的方式来进行遍历,对吧?好,这是刚才体检大家的一个要求。这个要求说出来,功能大家比较明确我们要做什么事了。好,他的,呃,要求以这种方式来存放,OK,看看对方应该怎么写的啊,要求完了下边。
14:01
OK。顺序存储要求在便利的时候,对吧,仍然以这样一个形式来便利,好,这是两点要求。那么把这个说完了以后呢,我们就给同学们说了一下顺序存储二叉树的特点,尤其是这第二个,第三个,第四个特点一定要记住,否则的话你写不出来。否则话写不出来,好,这是顺序存储二叉数的特点,有五个,我给大家阐述到这里。是吧,顺序存储二叉树的特点给大家板述到这里,一共有五点吧,一共有五点,前面呢有四点。板数到这里对不对,后面呢,还有一个就是这个N呢,我们实际上是从零开始编号的,一定要记住。也是说你二叉树的根节点编号其实是零。这点要明确。当我们把这个概念说完了以后呢,为了加深对他的理解,是不是我们写了一个二叉树的案例?是吧?顺序,呃,对这个顺序尔塔数的一个便利。
15:04
就在这里,那具体来说呢,代码我就拿过来了,代码实现。代码实现。那代码实现。我把这个标成一个粗体,然后把代代码呢给各位朋友板书到笔记中去,大家有个印象,好放这就可以。OK,这是我们的一个表格放进去,那么这个说完了以后呢,我这有个作业啊,要给大家布置一下作业,这个作业呢是这样子给同学们聊的,就是我这呢,只是写了一个。呃,情绪便利,我要求同学们呢,能够在课后去完成。这个顺序存储二次函数的中序和后续遍历。难不难呢?也不难,其实代码已经写的差不多了,最后呢,我还说了一点顺序存储,存储二叉数的一个应用场景是什么呢?对排序它的应用实例,但这个应用实力呢,我现在暂时不讲,是因为。
16:00
对,排序它其实是数结构的一种实际应用,所以说我们把这个章节呢,挪在实际应用的这个大章节去讲解。好,这是给同学们聊清楚了啊,聊清楚了。好的,那同学们关于我们这一个顺序存储二叉树的内容呢,就先给同学们先介绍到这里。大家。课后把这一个呃,中续和后续遍历给写出来完成。
我来说两句