00:00
下面我们用代码把前中后续查找给大家演示一遍。首先呢,还是老规矩,我们走,先找到hero node,我们来编写。相应的查找方法来先写第一个,我们先写前序。前序便利查找,OK,那就写public。Public,然后呢,你成功了,当然就返回这个no,实际上order什么呀,Searcher ch,那你给我传一个什么呢?显然你给我传个no就是雇员的编号是吧,找到了我就返回它,找不到我就返回一个空嘛。说到这儿呢,咱们有一个小小的注释。干什么呀,这个是编号查找的。No,这个是返回什么呢?如果找到就返回该no。是吧,如果没有找到呢,如果没有找到返回什么呢?No就可以了,非常的简单,那现在开始写了,首先呢,我们先比较看啊,先比较比较当前。
01:12
当前节点。节点,诶这样写节点。节节点是不是那很简单,If,我们用z.no。判断它是不是等于传进来的no,如果是的话呢,我们返回Z代码就写完了,那如果不是,根据刚才的分析,我们来看一下,如果它不是呢?OK,则判断当前节点的左子节是否为空,如果不为空,则进行递归前序查找,也就是说这个判断一定是要有的。如果你不判断,那假如它的浊子节点已经为空,你也去递位,那就会报空,指针异常理解,从这个地方呢,我们来判断这句话。把刚才这句话呢,OK。
02:01
洗过了。这个地方要写过来,那那怎么办呢?来if this,点它的left不等于空。是不是它不等于空,不等于空,我们进行。像继续进行,这个叫做什么前序遍历查找,把什么放进去,放进去了吧,放进去各位同学他说了,你看这面我还有分析。如果左递归前去找到就要返回,否则就判断,那你怎么体现出这句话呢?同学们,刚才你只体现出到。左左边去递归,但是怎么体现出找到了返回这样一件事情呢?这就说明我们应当去在当前这个占定义一个变量,是不是这样子的啊,同学们,所以说你应该写个hero node。Her no are yes no。比如这是我们的结,结果节点初始化为空,然后你找到了还是找到,还是没有找到,最终呢,我要得到它。
03:04
是不是要要这样子玩一把呀。好,那你怎么知道他有没有找到呢?用hero,就是那个result no,如果它不等于空。说明我们找到没有,说明我们找到了,这句话注意啊,说明我们这个右,我应该是左啊左左。左左左指数上左指数我们找到了。是不是找到了,找到。那诶找到,如果找到我就返回这个result node就完事了,代码就写完,但是有没有一种可能性,就是你向我们这一个左边进行。前序遍历查找其实也是没有找到的,那没有找到这个result no呢,仍然等于空,是不是就应该进行下一步的操作了?哪一步操作呢,就这句话。OK,就是如果左规找到返回,呃,否则继续判断。
04:05
否则继续判断。对不对,好,所以说这里面呢,还有一个逻辑。这左左递归前需要找到返回,否则继续判断。判断什么呢?判断当前节点,右侧节点是否为空,如果被空,继续向右递归。好,那我写一句话,Result this.right如果不等于空,注意啊,这句话千万别写错了。错了一个,待会儿挑起起来都很痛苦。对于什么呢,仍然是play no,好,同学们看,刚才我这个no是有问题的,应该这样调,刚才这什么我们play。Order research呢,没有指定是调哪个节点的,应该这样写的,同学们,我们这样写才对啊,this.left点。这样子写才是正确的,这个能理解吗?因为你是向左地柜,你你得用左子节点去调pre order search。
05:03
是不是所以说这个地方我写到这呢,突然就看到前面是有一点小问题的,把它。修补一下就可以了,this.right.no。这样子吧,这样才体现出向右嘛,你这个才体现出向左嘛。是不是这是向左递归,这是向右。继续前序递归啊递递归进行这个前序查找是吧,那最后这个地方查找完了过后呢,诶各位同学。这时result result node呢,有可能找到了,也有可能没有找到,那不管找没有找到,这个时候就必须返回了,是不是说这个地方呢,就必须返回no。当然这个返回呢,有可能仍然是个空,就是说相当于说你在这儿定了一个空,但是呢向左。没有找到,向右也没有找到,但是如果向左找到过一次,那就在这儿已经返回了。对不对,如果向右找到呢,我不管你找到还是没找到,最终把这个结果返回去就行了,我最后判断。
06:03
就是你这一个是不是空就可以决定是否找到,好同学们前序遍历就写完了,那么紧接着我们写下。中区便利。中序遍历查找非常的简单,那现在呢,我们写一段代码,Public public。呃,Public,我看看这个地方呢,OK,好,就是he load是吧,这个倒没关系,好我们也返回。这个here no,那我写一个in in fix什么呢?Order order search ch,好,这个S,我们还是大写一下吧。好吧,这样好一点,那这边大写的S,这边我们是不是都应该把它改成大写的S啊。是不是SEARCH1C,然后呢,同样你给我传一个no。那么我们这个时候来判断,如果是中区边地查找应该怎么玩呢?各位先判断当前节点的左子节点是否为空,如果被空,则递归进中虚查找,好,这个特别的简单,特别简单,我就第一句话啊。
07:11
把这个注释我们就不写了,拿过来就行,是不是这样子的,If this.left如果不等于空。各位同学,是不是我就直接接收到我,当然我要还是要用个变量来接收了,跟前面一样,Hero hero no are yes no,等于。是不是,那我用它来接收RS no等于什么呢?等于this.left点什么呀?In fix order传进去。是不是,那这个时候呢,我就要判断。我就写快点啊,Result node,它到底等不等空,如果不等于空,这个事情就结束了。因为我们讲我们是我们是有一个前提的,就说我们这个ID号不不重复,因为水浒英雄排行对吧,谁做了第一把交椅,你就不能把人赶下来吗?所以说我们认为呢,找到一个就返回,那要不等于空就RETURN2YES no完事了。
08:17
当然有可能你没有找到,没有找到呢,我们就走这条逻辑什么呢?对不对。啊对,现在中区查找,我们要开始和当前节点啊。比较。好。把这句话拿过来,因为你是中区便利,这个没有保障,我们就比较c.no。No是否等于你传进来的?No是不是这样子的?如果是,我们直接返回Z。那认识这一个呃,指向的对象就可以了,好,那下面继续来看,继续来看下一句话就是什么呢?就是。就是如果如果否则啊,否则向右进行递归,向右进行这个中期查找。
09:06
好,向右基于中中序查找的话呢,我们就应该还是要判断,如果z.right它不等于空,我们才能进行这个向右递归的中序查找,是这样子吧。那么你,你仍然是要用result node来接收this.right.in order。是不是同学们好,这时呢,同学们没有必要再去判断。Result node是不是一个空了,直接返回就可以了。result r1是node。为什么呢?因为你如果在中序这边找到了,那返回的就是指向的实际的经验,如果没有找到呢,它仍然保留no,这事就结束了,看到没有?好,同学们,这是我们中续遍历查找就写完了,那么下面呢,我们来写后续遍历。
10:00
遍利查找各位后续遍历查找呢,我们思路其实非常的相似,对吧,He no。然后呢,我写一个post什么呀,Post order。Outer search。好,你给我传一个no,我来处理。那么这个后续查找它是。怎么做的呢?先大家看这里,先判断当前节点左止节点是位空不位空,就向右递归,上来过后就向啊,向向左递归啊。递归查找啊向,但是我这没写,但是大家知道是递归向后后续查找是这肯定是左边嘛,因为你判断是左侧节点是不是,那就写,如果Z是点left,它不等于空。对不对,不等于空,我就肯定要接收了a hero hero no。我写个result no。Nod等于空。对于空是不是同学们好,那现在呢,我们接收等于什么呢?好的,那就this是点left,点什么呢?Post order把它进去。
11:13
是不是同学们,那现在是不是又要判断了呀,是吧?如果node这个节点它不等于空,说明什么?说明我们向左递归已经找到了,说明什么呢?说明在左指数。左指数找到。那如果找到呢,我就return r node。是不是,那是,当然还有可能是,呃,没有找到,没有找到,如果应该这样啊,如果左指数着指数没有找到则干什么呢?则向右指数。又指数递归进行什么呢?后续遍历查找,续变便利查找,没问题吧,同学们。那你向右是不是,你还是得判断一把吧,Z点什么呢。
12:04
如果它不等于空,你才可以。这样的进行操作是吧,Result node。等于我们的this.right点我好把它写进去。写进去过后呢,这个时候就。干嘛?呃,也要判断了。如果re no的。Re,一是load不等于空,那这个时候呢?我们不用犹豫,直接把这个result not返回就可以了。但是大家不要忘了啊,如果左指数右指数都没找到,如果左右。对吧,左右。左右指,诶写错了啊左右。指数都没有找到。都没有找到怎么办呢?郭同学,那么就比较,就比较当前节点,是不是就比较当前节点?
13:01
节点是不是好,那就加一句话吗?那就是。我们看刚才这个斜面啊,写到的那就是z.no它等于no的话,我们就返回这个Z。对不对,否则我们返回什么,否则仍然返回result node,因为的最初是空嘛,好同学们,我们现在呢,把这三种便利方法就给同学们写完了,大家看看能否理解,那现在呢,我们写完了以后,是不是我们真实的调用呢,也是在这个二叉树bary tree里面调用的,是不是我仍然要在这写上三个方法来调用我们刚才写的这些方法。那我写句话啊,就是叫情绪便利。对吧,情绪便利来吧,那public void。啊,贸易的。呃,这个时候就应该返回一个hero,不是没没有返回值了啊hero no。
14:02
对,那么我们先写一个情绪便利,就是pray。P,呃,Order order。好,当然你这个时候呢,要给我肯定要给我传一个no,你没有传no,我没办法判断是吧,那现在开始写了,如果我这个root。Root它不等于空,这时我就调用root里面的这个。Order search。直接返回就可以了。是不是返回。否则如果说我们这个呃,Root上来过后就是空,说明这是个空子数直接。空就完事了。好,这就是我们的前序便历,看明白了,那么我们写中序便利,那中序便历是不是跟前序便历基本上是一样的,我们写一下就可以public,然是返回he load,写个什么呢?In fix。Order search e,同样,你给我传个no,好的,我进行一个判断,如果root。
15:07
它不等于空,说明我们至少有一个节点。如果有个节点,我就什么呢?root.in把no放进去。对吧,否则。怎么样?如果它root上来过后就等于空,那没得说,直接返回一个return一个空就完事了。好代码就行了,那下面呢,还有最后一个后续遍历。对吧,后续编利,那后续编历怎么写呢?Public仍然是her load好,Order search。CH,好,同样你给我传个no。是不是下面代码如法炮制啊?如果root不等于空。如果root不等于空的话呢,我就return return this.root点。
16:03
点什么呢?Post order。Search,否则我返回一个诺,待会就行完了。好,同学们,这个就是我们这一段就是关于二叉树的。三种便利方法的代码我们就写完了,那么一会呢,我们来测试一下我们这三种方法对不对,并且要分析出来,按照他的要求,并且要分析出来什么样。这已经写的很清楚了,并且我们还要分析出来各种查找方式到底比较了多少次,也就是说我们要用图解的方式来分析,然后再来验证我们分析是否正确,才能真正的让我们理解三种。查找方式的不同。OK,那关于查找的这个验证和测试呢?我们下一个视频为大家讲解。
我来说两句