00:00
呃,我们刚才讲了一下二叉树的,嗯,三种便利方式,那下面呢,我们来看一下二叉树的查找。那二叉树查找呢,我们先来看,呃,这个查找的方式有哪几种,你的便利有。三种方式,那么我们查找呢,也有三种方式。你比如说我们现在要求大家用三种查找方式来查找hero number等于五的节点,哪一个节点呢?就是那个关胜。那这个时候我们怎么去进行这个查找呢。好,那现在呢,我们把这个代码来写一写。好,现在我们来完成这个对节点的查找,OK,同样道理,我们在这呢,你来写一下我们这个思路。好,现在我们来完成它的三种方式的查找。第三步使用使用三种。
01:02
啊。三种方式完成查找。查找好,我们现在呢,先用第一种方式,就是用前序。情绪方式来查找。那所以前序方式来查找,就是说我们先判断一下你当前这个节点。是不是围绕的节点?如果不是,我就往左数去查找,如果左边这个数没有。我就向右边这个数递归查找。那当然最后也有可能没有找到,没有找到,那返回就是一个空节点,好,我先说一下这个情况啊,首先呢,我们是比较当前的这个节点。OK,然后然后比向左,如果不是对吧,那如果是那肯定就退出了嘛,假设我们这个英雄编号不是唯一的,呃,都是都是唯一的,就说123,大家不要有重复,那如果有重复我们再说重复的事。
02:08
啊,如果不不是就向左向左递归查找。OK,如果左边又没找到怎么办呢?诶,如果左边还没有,如果左边左左子数左子数没有。就像什么呢,右边查找。右边。右边这个指数递归查找。那当然要么就找到了,要么就没有找到嘛,那中区便利的其跟他的唯一区别就是说,呃,这个查找的时候,这个比较当前节点是要放在中间这个位置来进行查找,能理解好,现在呢,我们打开这个代码,我们打开这个代码还是呃这样子啊,前序后续我就把这个便利这个地方刚好就给它写在一块,这样子大家以后好好看,我就写到这了。
03:05
前序,前序查找。OK,那我们写个方法。Order,情绪便利的search。那你要查找的时候,你要给我是不是得得把这个编号给我一下,对吧,你要查找哪一个人,那么我就用编号搜一下,那么最后这个地方它应该返回一个什么呀,同学们。是不是它会返回一个hero load呀?就说你这个节点要给我返回来,当然有可能没有,那就空了。那现在呢,我们上来过后,我们先进行一个比较,就是如果。如果说你这个z.node或者这样说吧,你这个要找的node等于。我当前这个节点的node no就是编号,那说明我们就找到了,是不是,那找到我应该怎么办呀,我是不是就return这个类似。
04:07
但有些有些同学可能会说了,说老师假设我们有重复的怎么办?重复的跟我们原先那个二分查找其实类似,就在这找到过后,那你再往它左边进递归,直到找不到而已找直到有一个跟他不一样。啊,这个呢,也很好处理。那么如果这个没有找到。就说这地方它不相等怎么办,就是根据刚才说的是向左递归。做递归查找。那像左地柜查找这个时候怎么处理呢?一般来讲我们会这么去处理,先写一个。先定一个node result no初始化为空。大家注意看这个思路,我先初始化为一个no。因为我不知道你找不找得到,我先初始化为空,下面呢,我就进行这个查找,你既然向左边递归查找是不是,你先要判断你当前这个左边它是不是等于空啊。
05:05
如果不等于空,是不是才可以向左边递归查找?如果等于空是不是,那就没有了吧?这点大家一定不要忘了啊,很多人写这个情绪,查找的时候找不出来。那现在呢,我们这边就很简单了,找order把这个no继续传进去就可以了。这编号传进去。那现在呢,这个这个这个地方,这个地方是不是会返回一个结果啊同学们。是不是我可以用这个result。No吧,接一下。他是不是这样子,为什么我要接一下呢?因为我要看你向左边找有没有找到。如果你找到了我,我就return了,如果没找到,我才继续向右边找吗?是这个逻辑吧,好,所以说下面呢,我要做一个判断,如果说你这个node它。它不等于空。
06:01
是不是相当于说我这个事情向左边就就搞定了,那就return我们这个no。否则。我们应该怎么办?向右边查找。向右边,向右边递归查找能理解,你向右边递归查找的时候呢,跟前面这个逻辑也是如法炮制,首先你要知道右边这个节点有说它不等于空,你才可以继续查找。然后呢,这边我们仍然用node去接收一下。This。爹。Right,并写错了点pre order把no放进去,最后这个地方拿到,拿到以后呢,就没有什么可说的,就return这个result node,当然有同学说了,说老师要是右边也没有查到怎么办呢?那那就是个闹吗?你右边查找到了,还是右边没有查找到,那这个就是最终结果了,是不是有可能确实返回就是空,那也没办法,就是没有,如果右边查到了,那就是右边,如果是左边查到就是右边返回的,好同学们,那我们这个前序便利的方法就写完了。
07:13
那同样道理,我们把这个前绪便利的这个方法呢,也在我们by tree里面用一下,因为我们的根节点是放在。这个better tree这个对象里面的,对吧,那同样道理,我们还在这个位置来写。好,我们叫前序查找。程序查找,诶查。查找那D把这个方法往这一贴,同样你呃,你在程序查找的时候呢,呃,肯定你得给我传一个编号过来,对吧,你不传我没有办法去查找,呃,OK。查找,那是不是我这边也也一样会返回一个her no是不是,诶her no很简单,那现在呢,这个地方就简单了,如果root。
08:00
这个root,如果它它不等于空,是不是我才去查找呀。因为你入的本身是个空数那。那没法没法查找嘛,所以说这边就写一句话,就说当前数二叉树为空,不能查找。当前二叉树为空,不能查找。那就那就不玩了,那下面这个地方呢,不一样啊,这个地方那哦对不能查找,那就这样子吧,我们也不再不要在这提示了,如果它呃为空的,就直接返回一个return一个ignore就行了。啊,Lo就行了。这种这种空和你查找的空不一样,这种空代表你这个二叉树本身没法查找返回的空,还有一种空是代表找了但是没有找到,那这地方调用怎么调用呢?就是root点。Order search,然后把no放进去,放进去过后我们这边有一个return,但你不写可以,因为它刚好是最后这个结果,好,情绪查找我们就写完了,待会我要找同学说一下前序查找一共花了几次啊?
09:02
我现在呢,在这调一下这个方法找到另方法,我们来调次查找。好,同学们,现在呢,我把这个先注销。我们来玩一把。现在我我来进行一个查找啊,走,我搜一下这个节点V。Result mode。No no,我用这个bary tree点。A pre order,比如说我要查找五号,查找五号过后呢,我输出这个结果,如果说这个node。它不等于空,不等于空说明找到了我把信息输出来。就说找到。找到编号为。啊或者编号。编号等于0%字说出来。对吧,名字内蒙。Name等于FS把它输出来编号,当然就是你这个结果里面的这个值,那这个结果里面这个值,这个值呢,就是你的这个no,那么你的名字就是这个结果这个节点带回来的这个内。
10:13
那如果没有的话呢,就说一句话就说找不到啊,没有这样的编号没有找到。好,同学们,代码就写完了,写完过后,我想请同学们思考一下我这种情绪便利。我这种情绪便利一共比较了几次,大家先看一下这个图。我们来看看前虚便利,我首先比较的是宋江。不是,这算一次了。吴用又比较一次两次,然后呢,卢俊义又比较一次,关胜比较一次,所以说我这个前学编辑大家记住了,他一共比较了四次是吧,比较了四次,待会我们再做一个,看哪一种便利方式它更好,也就是说便利方式不同,对我们这个。
11:02
就是说你不同的编辑方式对这个查找次数次数实际上是有影响的。那么我们来执行看看这个结果对不对,首先我们执行一下,我们发现呢,现在应该是找到了。对找到了,那现在呢,我把这个编号换一个,比如说我51。对51,那51过后呢,我们发现没有找到,这是正确的,好我们通过这个案例,我们可以看到前序遍历呢,一共找一共走了四次啊针对这个题,针对该题。该题然后前序便利。情绪便利共。啊,共几次呢,共四次。好,下面我们来给大家写这个中序遍历。中序遍历的查找。好,也很简单,我们来写个中序遍历。中学。中序方式来查找那一样的逻辑啊,它这个逻辑呢,是先比较。
12:04
先向左查找上来过后先不比较当前这个字。他先。左递归查找,如果佐助数没有,再比较当前这个节点。啊,然后再再比较比较当前节点。啊,如果如果还不是,如果仍然不是。就就向右边递轨查找,那待会儿我们看针对这个操作啊,中续便利会多少次。好,我们先来看一下,如果是中区便利,它先比较无用。肯定不是。然后比较这个宋江也不是,然后中西边利,他该比较谁了。朱关胜呢,这个其实他一共比较了三次。所以你看这个不同的方式,它确实不一样,对吧,那现在呢,我们把这个中序遍历也给大家快速的写一下老规矩,找到这个位置。
13:03
啊,这样就比较好看了,那现在呢,我们写吧,中学便利。中序遍历查找。啊,这些都是基本功,后面呢我们都都会用到的fix。然后诶,这个词写一下啊,In fix order search e,然后呢,在这里。OK,你得给我传进来一个编号,你没有编号我没有办法去查找,老规矩。呃,上来过后就要判断了,这段代码我就不再一步步写了啊同学们,因为我们前面诶这个写写的位置写错了啊,不好意思,应该先写到。我们这个这个位置来对吧,诶应该是往这写,先写里边,然后被调用者先写,调用的人后写嘛。那中期便利呢,我们先比较先向。向左递归查找。那老规矩,你首先要去判断。
14:01
当前这个左指数它不为空,你才去向左递归,那这个道理很简单,就是。点我们的这个infe。把我们这,诶不要老写这个啊,Order search,把no传进去,当然你这边仍然要接收到一个结果,你不不接收到结果我不知道,所以说上面呢,我仍然定义一个result no初始化给它一个空啊,我这把类型给它定一下,叫hero load做一个空。然后这边我们用这个结果来搜一下。对吧,诶这么为什么错了呀。是不是这一段返回值你写错了是吧?诶,非常好,大家看出来那就是hero no。这就没问题了,紧接着呢,我们要判断,如果你这个结果它不等于空。说明你向左数查找的时候是找得到的。
15:02
那么我就不能说直接把这个结果返回。那紧接着呢,你这个做完以后,如果没有找到,我们就向右递归查找。诶不不对,比较当前了,应该比较当前了,对吧,要比较当前这个节点了,比较当前这个节点呢,很很简单,就是如果你的这个no就等于Z10.no。啊就等于啊,就等于你这个当前节点的no说明找到找到这个就简单,就直接return this。也也就不走了,那紧接着呢,如果中间这个还不是,对不对,向右递归递归查找。递轨查找,那向右递归查找,你也不要忘了,一定要判断它的右节点是否为空。如果右见脸。不为空,我们就用这个result no来接收向右递归查找的这个结果,对,right.in fix把no传进去。
16:03
这样子,最后不管你结果怎么样,都要把这个node返回。好,这个是中序遍历的一段代码,那下面呢,我们仍然在这。在一个二叉树里面,把这个写一下啊,中序遍历查找。中序便利操作,OK d in fix order search。那同样,你给我传一个no进来,我给你返回一个hero。那代代码跟前跟跟跟刚才一样,如果root它不等于空,我们才去查找,否则直接返回一个空对吧,直接返回一个,那就没有。然后在这边呢,我们root.in order传进去。这边你可以写个return,也可以不写,我习惯上呢把这个带上。啊,愿意不带到不带的话,他呃带不带都可以,但是我习惯带上好中序便利,我们来调一下,找到我们的主方法。
17:07
找到主方法,我们用中序遍历来玩一把。好,我用中序遍历写一下。复制一下,那这边我们就改成中序遍历了点。Are in fix。把这个no传进去,比如说也是五号。那也是五号的话呢,我们在这个地方来输出啊,找到了还是没有找到。好。我们来看看这个结,我们看看它一共遍历多少次,我们刚才分析的是三次,我现在来看看是不是三次,怎么在哪打一下呢,在我们这个。Hero node里面的哪个位置呢?这我们看看是不是一共输出了三次呢,走一个。好,我输出歪歪歪。大家觉得我这样输出会输出几次啊?会输出几次啊。
18:02
啊,输出一次,那怎么可能。几次啊,刚才我们说的是他一共比较几次三次,那大家觉得这样会输出三次吗?这个地方会输出四次啊,那为什么呢?我们先看看是不是四次啊走一个。我们发现他把这个结果确实找到了,但是他输出了四次,这就不对了呀,那刚才说韩老师你不说的一共有三次吗?而且的确是三次,你看嘛,他先比较。无用。吴用不是再跟宋江比不是吧,然后他不会先跟卢俊义比,他跟关胜比对不对?那应该是三次就搞定,那么为什么你在这个方法里边打印的这个YYY却是四次呢?有同学能告诉老师原因吗?原因是什么呀?原因是这样子的,你真正比较并不是在这儿发生的。
19:03
你真正比较是不是在这个位置才发生的,也就是说人家可能只是进到这个函数了,大家并没有发生比较的动作呀。是不是你这样写你是不合理的,就好像你进了大门,但是我没看电影,你要说你我进到我我进到电影院,我没进到那个电影放映厅,你不能让我交交门票嘛,是不是,所以说他真正只进来,比如说他进来了,但是这个也不是,这个也不是,这不是直接返回一个空,那也不能算人家比较了嘛,是不是。所以说你如果把这句话写到这儿。才是真正的比较的次数,是不是这个道理啊?是能理解吗?那这个地方它会输出几次呢。来,我们执行一下。我们咨询一下。是不是这次就三次了呀?能能理解这个地方吧,如果没有理解的,大家想一想啊,想一想,的确是比较了三次的,比较了三次好同学们,那关于这个我们所说的这个中续便历呢,老师就讲完了,我们再讲最后一个后续便历,要注意后续便利,要小心一点后续便历。
20:09
查找。后续遍历查找这个思路呢,那他是这样子的,先到左边递归。然后啊,如果没有,如果没有就到右边。向右边地柜查找。到右边地位查找,哎,然最后如果还没有,如果还没有找到,没有找没有。那么就比较当前的节点,那我问大家。后续便利一共比较几次?来,我们看一下。后续便利是不是先比较他呀。后续编辑是先比较这个左边。左边完了过后这边。哎,后续变力是不是先比较这边吧,左边再比右边。
21:00
右边这个是吗。因为他他跟谁不一样。是不是直接跟我比了呀。因为你因为你这个这个节点左边是关生,就直接比,也就它实际上两次就搞定。那大家有没有发现,就说你不同的这个电力方式,对这个。比较的次数是有影响的。对,这点我希望同学们至少要知道,说为什么我们要把前中后都来演示一遍,就是它的确有影响。好,那现在呢,我们把这个后续遍历也写一遍,找到我们后续遍历的这个位置。Post,好老规矩啊,同学们,我们写吧。后续遍历查找。那我就写一个post order search erc,同样你把一个no传进来啊,这现在这些代码都比较简单,待会呢,可能需要大家动动脑筋哈,呃,那现在我就直接这样写了,先向。
22:00
左边查找,注意。诶,就写到这了啊,这个地方是左边就是post search,把这个穿进去,传进去过后,这边会有一个结果,把这个结果拿下。字写错了。啊对对对,这个怎么会写到这儿去了post。把这个no放进去,然后同样我们这边有个结果节点,先给大家做一个初始化的动作,对,Hero load等于空。好,同样在这里呢,我们就把它接一下啊。接一下那我要做判断了啊,同样原因也是这里没有把这个类型写对。好,如果说。如果说这个result。它不等于空,说明我们找到这个节点了。那就直接return这个I reno。没有任何问题,然后呃,如果他没有的话,就往左边递归,呃右边递归,右边递归就是this.right它如果不等于空。
23:09
如果不等于空的话呢,我们同样接收一下又递归返回的这个结果。对post,然后呢,同样把no传进去。好的,那同样还要判断呢,这个时候要有判断呢。这个为什么要判断?因为你下面还有一次比较呢,所以说这个判断,如果这个result no仍然不等啊,不等于空,它不等于空,我们就不要比较当前这个值了,就直接return。Note。否则还要做一个比较。那最后就看最后这个跟当前值相不相同,this.no no等于,如果等于你传进的no好,说明这个就成功,就返回一个this。那么这样代码呢,有问题。你看这边代码也错了,因为你有一种可能性,就是说这个也不满足,这个不满足你最后还要写个result。
24:07
哦,这样代码才是正确的。啊,一定要有这个东西啊,不然你这个代码是跑不起来的,好,后续便利,我们同样在这个batter tree里面也写一把。Post order search。然后我们这边干什么呢,同样返回一个这个load。一样的道理啊,跟刚才一样,Root,如果这个route不等于空。我们就去进行这个便利。啊,代码也很简单,root.post。把诶这个no没有传进来,对不对,把no传下。No传下走一个no走int这边呢,我们把no传进去,说了这个可以不带return,因为它刚好是最后一句。否则返回一个空,我们写这种写法也可以的,好,我们调一下。
25:03
掉下,同样找到我们的主方法。同样找到主方法,我把这个复制一份,我们现在调用,后续遍历。后续便利的话呢,我们来看一下这个次数啊。呃,这个代码就调换一下。点post,我们写个五,同样我们把这个次数打一下。在哪里打印呢?老规矩,找到这个post order search,我们在比较这个位置前面打,不然的话。这个。比较次数就统计的不对了,我在里面写一个什么呢?写一个这个,比如说TT。这边应该输出两次TPT才说明我们用的是真正的后续便利,那现在呢,我们来找到主方法进行一次简单的调用运行。好,我们看一下一共输出了几次呢?我们发现的确输出了两次,就找到了关胜。
26:00
好,同学们,那关于这个我们所说的二叉数的。查找指定节点。我们就讲到这里,截取一段时。
我来说两句