00:00
好,我们来测试一下刚才写的这三种便利方式,我们先来看一下前序便利。谦虚便利,OK,那首先呢,我们怎么写呢,对不对,首先我在这提示一句话。我们写个叫做前序,前序便利方式,OK。大家好,然后呢,现在我们要做的事情特别的简单。对,我们只需要用bary。翠点什么呀?Order search把我们的五号传进去,那么这时候它会返回一个结果是吧,比如说这是我们的,呃,这个load,那这个load为了好看呢,我把这个名字稍微的改一下,我改成result。检索出来过后的这个load,大家看这个理解哈,那现在我们就来判断到底有没有找到,如果result no。
01:02
对不对,他怎么样,如果它不等于空,说明我找到了,我就提示一句话,我提示怎样一句话呢,我格式化一下。对不对,我说找到找到了,那么找到这个信息为什么呢?OK,信息为no等于D,名字等于。二白S,那怎么取啊,就是result。No。No,把它的no取出来就可以了,Get。Get它的编号,然后呢,再把它的名字也取出来。Get他的名,其实我们知道五号呢,是关胜,他应该能找到,那要十呢,我们就提示另外一句话,说什么呢?没有找到编号为多少的啊,没有找到这个number等于多少的这个英雄。
02:02
是不是英雄?好,那同样我们把这个编号给大家给它打出来,当这个是五,我们就固定写一个五就完了,好吧,固定写一个五就完了,好同学们现在呢,我们来格式化一下。格式化一下这些代码来看一下。哥说。我们运行一把,看看前序便利这个能否找到我们运行。好,运行过后呢,我们发现前序变量方式的确找到了五名字是关胜正确的,我们换一个不存在的,比如说15 15这个编号呢,没有存在,所以说我便利过后呢,他应该提示什么呀,没有找到编号为五的英雄,好呃,那么现在我想呢,给同学们来分析一下前序便利的次数。情绪便利的次数。是多少呢?我们来数一数。还是以这个为例。首先呢,谦虚,便利。
03:01
便利为五哈,他先让宋江跟他比较。显然不是。二比较,相当于不是两次了。卢俊义,三次了。关胜,四次,一共是四次,同学们好,我们来在这打印,看看它到底是不是四次,找到我们的前序遍历的代码,同学们我在这写一下。看清楚了啊,我这写一下system。走我这输出前序进行全序便利进入,进入前序便利OK。各位同学在写这句话的时候呢,一定要在比较的这个前面写明白我的意思吧,因为我们说真实的比较总是在this number等于number这句话,也就是说不管你是进行了多少次DV,它真正比较是不是肯定是在这个地方比较的,能理解吧,所以你输出这句话呢,应该在比较的这一句前面输,说他应该输出几次呢?各位刚才我们已经。
04:05
玩过了,他应该输出四次。好,我们运行一把。我们已经我们可以看到他输出几次。啊,对,这个地方我们要把它换成五。好,同学们可以看一下,看一下啊。看一下前序遍历找到了,诶,我是不是在写错地方了呀。情绪便利。我们看看是在哪写的呀。Play out,进入情绪便利进入,进入情绪便利。他为什么没有输出来呢?好,情绪便利我这样子啊。Number我们看一下往上找。
05:00
我进入情绪便利对吧。Pre order,好,这个地方是掉的pre order,我们进到这里面去看为什么没有输出。哎呀哎呀,这地方哪能这样子啊,这个地方咱们写错了啊,这个不知道为什么写成这个样子了P。Pre order啊,把它改一下就可以了,来,我们再来玩一把。好,我们可以看到进入前绪病,一次两次,三次,四次。分析是正确的。啊,这版我们刚才写成post的都是以P打头的啊,没有注意到这个问题,Pre order search正确的,好,我们再来测试它的什么呢?好,我们再来测试它的这个中序遍历。中序便利。那么中期便利呢?我们仍然按照这个思路来玩一把,复制一下。现在我们写成是中区便利看一下。那中期编辑呢,这个时候我们应该调用的是点。
06:01
Are infe5。对吧,好,那么我先把前序便利给注销,好吧,前序便利给注销,来把这个写进去。那这个时候呢,叫的是infe order search,下面这个不用改变,我们先来看,首先看有没有找到。我们运行我发现呢,中序遍历也能够找到是吧,我换一个不存在的编号。当然这个地方也要换成15了。走一个,我们发现了15没有,没有找到正确的,好,现在我重新把它换成五,我们来分析一下,如果使用中序遍历,我们一共有多少次,来走一下中学便利,先让他跟吴用比一次。跟宋江比一位。右指左指数已经变定完毕,一次两次。这个不用比。三次。也就说中区便利应该是。三次对不对,中序便利三次我们分析出来了。中序遍历是三次能理解,那么我们现在呢,仍然在中序遍历这个地方,我们输出一句话在哪里呢?在这输。
07:10
对不对,在这儿输出这么一句话。中序便利。哦,同学们啊,我这中序遍历。中,呃,这个这个这个是中序便便历中序查找啊,我们找中旭查找,中旭查找在这。对吧,中序查找在这个位置。那么我们在哪里输出呢?我们要在这个地方输出才是正确的。对不对,我们要在这输出来走一个system,输出一句话叫做进入中序查找。中序查找没问题吧,同学们。进入中期查找好,现在呢,我们来运行一把。一共有几次呢?一次两次,三次,三次正确的好,我们再来,最后来验证,后续查找。
08:03
啊,后续查找来,我们同样呢,也在这地方写一招,后续遍历查找。后续遍历查找啊,这少写了查找两个字。好,这样就没问题了,那同样为了省事呢,我把刚才的代码拿过来,是不是把上面这个先注销一把。这改一下叫后续遍历。那后续便利呢?我们先来看能不能找到。我们先来看能不能找到啊,找运行,首先我们看后续遍历呢,他说找到了。他说找到了,好,呃,他说找到了,那这个后续编辑,我这是不是也写错了啊,这重新来一下点post。Post order是吧?Post order search,这才是后续遍历,我把这个写成五。啊,因为我们我把这个粘过来没有改嘛,没有改你肯定就看到的,还是以中区便利来走的,现在把它改成了post order search来玩把。
09:04
运行制。那运行过后呢,我们发现呢,后续编辑的确找到编号为五的关胜,我们再换一个不存在的看看对不对,我们发现呢,诶。没有找到,没有找到我是因为我这没有没有改啊,实际上是没有找到15,因为你看这提示的信息还还是正确的吗。你,你再看一下这次就对了,他说没有找到编号为耻五的英雄正确,好,现在我们看看后续便利的次数,我们分析一把,看看我们到底有没有理解后续便利查找。对,查找的次数是多少次呢?打开我们这分析吧,后续遍历是先遍历左右,左右指数左边不是。到这不不用比较,这也不用比较直接比较换肾了,也就是说我们后续便利其实用的次数最少用了两次,大家发现没有。那我们来看看是不是像这的呢?打开这里我们来测试一下,这是两次。
10:02
是两次吧,同学们,我现在找到后续遍历的代码,完了往下拉。在哪里呢?在我们的post order在这。同学们,我们比较,我们判断比较的时候要在这写啊,同学们,如果你写在上面,这个有可能不准确,你看如果我写到这,我说进入后续查找,有可能跟我们想的不一定一样,我试一下啊。你看今日后续杀了多少次了?一次两次,三次四次,为什么这儿写不对呢?因为你要是在这儿写的话。你要在这写的话,其实他有好几次,他只是进来判断左右是不为空。是不是,那你也也把它算进去了,这是不划算的,所以这这就不是真实的,所以说你真实的这个比较次数应该是写在this number等于number这个语句之前,才是真实的比较次数,我不知道我说清楚没有,因为你想嘛,你你后续遍历是先走左右指数,它只要不为空,它他就先进去,只是他一判哦,左指数不为空,它就退出去了,实际上并没有发生比较明白我的意思吧,所以说你要判断它比较的次数,其实你是要把这一句话写在比较语句的。
11:19
前面这样才是正确的,因为你想你是地归亚。你对贵商的第一句话做了,但是没有比较啊,是不是这样的道理啊,所以说这个地方再输出就应该是输出两句进入后续查找。明白我的意思吧,所以要深刻的理解那运行值,我们发现呢,就是它应该,诶这个我看看啊,后续查找跟我们想的不一样是吧。我看看是不是我没掉啊,看一下啊。后续查找不对啊,我看看。后续查找的话是一次。两次,确实是两次,我们再来看。
12:00
我再来看。Post,诶对了,你那这个东西没换啊,同学们,这个你你五号不换,那没有找到,那肯定他就全部跑了一圈嘛,对不对,那我走一下,好各位朋友请看这次进入一次后续查找,进入两次后续查找,刚才为什么是五次呢?是因为你你让这个15去,那就是五次了,为啥?你先跟他比较,不是跟他比较。又不是,那你下一个应该跟谁比较了,跟林冲比较又不是再下次跟三比较,又不是再下次跟一比较,又不是一共五次嘛。是不是这个道理,但是呢,如果你是。跟五跟这个官胜找,其实你是用两次就找到关胜这个节点了,所以说刚才为什么是五次,是因为我写的是一个不存在的编号是吧,那我写成存在的编号,这个五你看上来过后,这是两次进入后续就搞定了,那我再问大家一个问题。假如我现在查的是二号,是不是我一次就搞定了?
13:03
如果写个二,是不是一次就搞定,肯定是一次,看到没有。所以说要深刻理解啊,也就是说后续查找,其实从目前来看,它的次数是。最少的。好,同学们,那关于我们这一个二叉树的查找指定的节点呢,我们就给大家讲到这里,然后我把刚才我们讲的内容给大家简单的板述一把。啊,内容并不多,但是呢,还是要好好理解,你才能知道老师在讲什么。好,刚才我们讲的就是二叉树的,呃,查找指定节点的内容是不是同学们。好,我写到这里了。那具体来说,我们这个要求呢,一共有三点。是不是三点。那三点拿出来过后,我先给同学们做了什么事情,我先做的是思路分析。是以图解的方式给大家说一下我们准备怎么干。也就是说我们前续中续后续查找的思路是什么样,是不是按照这个给大家来玩的。
14:06
是不是这样这样一个图解,好,具体来说呢,就是这讲的。这讲的这讲的是吧,同学们,我把。这个图解先给大家拿过来,紧接着我们是不是用代码实现了,那代码实现。代码代码实现。OK,那代码时间我这里就不啰嗦,直接把这边写的代码给大家板书过来就可以了,好吧,我就没有分了啊,我就没有分了各位同学。那具体来说一定要给大家看,画出来的话呢,我把它标成一个粗体,大家知道我这块讲的是哪一块就行了,来,这是后续。我把我把它标成另外一个颜色嘛,大家一看就明白了,好,我给它来一个蓝色。是不是大家一看哦,这一部分就是我们的后续查找,那么中续查找的代码呢,来同学们是不是在这啊。
15:01
我又标成这个。蓝色的字体加粗,那么我们的前序。便利查找代码是怎样的,是这一部分。这个地方。好多了啊,这是我们的。前序遍历查找。好,最后我们在调用的时候A。我们调用的时候是在哪调的呢?是在这个地方调的,同学们可以看到是吧?这调的好,这里我就不再调颜色了,同学们应该能够理解,那我给大家一个建议,你在这听完了过后呢,有可能有些同学听明白了,有些同学呢,还不是特别明白,那怎么办?把代码多敲几遍好不好,然后呢,实在不行,你试着说,哎,老师你要分析,我还是不懂,怎么办,下断点。走一圈就可以了。好吧,那你要要深刻理解,你去走一个debug会看的更清楚,因为这个东西准确来说它并不难。其实就是一个地位,我们前面讲帝归的时候,我们讲了八皇后我们也讲了哈,我们也讲了这一个小小老鼠找迷宫,其实比这个还难一些嘛,是不是,所以说这个并不难,其实就是左右指数的一个便利。
16:13
好,同学们,那关于二叉树查找指定的节点,我们就先给各位讲解到这里。
我来说两句