00:00
各位,我们继续来讲二叉树的查找。先来看一个要求,现在呢,我们完成查找指定的节点。对,那现在的要求是这样子的,请编写程序。完成前面的前序查找、后续后续查找、中续查找这三种查找方式。那么并分别使用三种查找方式去查找hero no就是我们编号为五的这个节点,而且呢,要分析出各种查找方法分别比较了多少次,并且去验证一下自己的分析是否正确。这个呢,就是我们查找指定节点的一个要求,这样子我们还是老规矩,先对我们这一个节点查找的思路做一个分析。打开我们Excel表。现在呢,我们来分析吧。然后根据分析完成我们的代码,好吧。
01:01
好,现在的分析是。这样子。这儿写一个哈。我们现在完成的样子就是使用。使用前序。前序前序哦,中序。后续。后续的方式来干,干什么呢?检索或者要查询。查询指定的指定的这个节点。对,指定的节点。好,现在呢,我们先把这个拿到这,我们对谁来进行演示呢?我们这样抄,我们就用前面讲的这一个。来给大家进行讲解。好,我把这个。原先画的这个图呢,给大家拿过来。把它拷贝到我们的Excel表。把它拷贝到我们的Excel表。
02:00
诶,这个地方。有点卡顿对吧,有点卡顿好我粘一下,诶粘过来了。那粘过来过后呢,我们来一起分析一下吧。我们先来说前序查找。前序查找的思想。思路,而首先既然是前序操刀,那当然我们第一步首先先让。先跟当前这个节点进行比较。比如说。比如说我们第一次进来的时候呢,这个节点显然是root节点,是不是这样子的呀。这样子的吧。所以说我们是先。先判断当前。当前。当前这个节点。对节点的这个number是否相等,是否等于等于要查找的。要查找。要查找的好,那现在有这么几种可能性,第一种可能性就是如果说如果是相等。
03:05
相等,则返回当前节点没问题吧?如果是相等,那么就返回当前这个节点。那有一种可能性就是不相等呢?好,如果不等,如果不等,则判断判断当前节点是否这个节。当前节点是否当前节点的左左子节点?左。子节点,它的左子节点是否为空?是否为空?如果不为空,如果不为空,不为空。则干什么呢?则递归,递归前序查找。就可以了。是这样子的吧。那接着看,如果我们这个向向左递归,相当于说我们向左递归。
04:05
有查到了,那么我们就返回。如果没有查到呢,还需要向。右子节点继续。递归前序查找明白我意思吧,好这样子啊,如果如果左递归。这样写啊,左递归。递归前序。前去查找。找到了什么呢?找到了节点。找到了节点,则返回,则返回,否则继续判断,否则继续判断,判断什么呢?判断就是右子节点就是当前的啊,当前的这个节点,节点的右子节点是否为空,右子节点是否为空。对不对,如果不为空,如果不为空,则继续继续向右,向右递归。
05:03
干什么呢?前序查找。先去查找好,这就是他的一个思路。这是前序查找的思路,那前序查找的思路有了,我相信同学们应该很快的就能知道中续查找和后续查找的这么一个思想,来,我快速的给大家写一遍,那我在这个基础上改一改就可以了,我们来看中序查找。那么中虚查找呢?他是干什么呢?OK,他是先判断当前做。节点的左止节点是否空,如果不为空,则递归情绪打扰。所以说他做的第一件事情。来,我们把这个思路捋一捋。中需查找呢?是判断当前节点的左子节点是否有空,如果被空,则递归查找。是吧,那查找完了过后呢。如果找到,如果找到了,则返回。如果没有找到,如果没有找到就比较和比就比,就和当前节点进行比较,是这样是吧,当前节点比较,如果是,如果是,则返回当前节点。
06:12
当前节点,否则,否则干什么呢?否则继续进行。又递归。又递归的这个中枢查找。中旭。中中序查找。好中序不这个不好写,中序查找。对吧,那这我们也要把它改成中序。是这样子的吧,哎,上来就是中区啊。那嗯,如果如果没左左递归,嗯,左递归中区查找没有找到,就比较当前这个节点,那么如果是就返回当前节点,否则进行右地位查找是吧,那右地位查找如果找到了呢?各位同学好,我们看。如果又递归,有递归。
07:03
右。好,如果右递归。这个又不好写。D又。又递归。这个呃中去查找中去查找,找到找到就返回,否则呢,返回空是吧,反这个空就可以了。把这个空就行了,好,这是中序,那后续查找呢,后续查找的思路我们也来做,首先第一步他先先判断它当前节点的卓资节点是否。为空,如果不为空,则递归后续查找。是这样子的吧。递归会去上涨,否则呃,这个如果找到了,当然啊,如果找到。如果找到就返回,如果没有找到,如果没有找到就判断当前节点的什么呀,右子节点,右子节点是否为空,是否为空,如果不为空,不。
08:09
为不为空,则什么呢?则又地归。又递归这个进行进行什么呢?后续查找。是不是这样子的是吧,又丢给查找,如果找到,如果找到就返回。就返回。啊,否则干什么呢?好,否则就是第三步了。如果他没有返回呢?OK,就干什么呢,就和就和当前。当前节点进行比较。对不对进行比较,如果是,如果是则返回,则返回,否则返回什么呢?No。好,这个就是我们讲的后续查找的这么一个思路。同学们看,是这样的一个逻辑吧,你看我举个例子,以前序为例,给大家玩一把。
09:03
以前序为例给大家玩一把,比如说我们现在要查找为五的,我先让宋江先判断长当前节点no是不是等于要查找先,线上一不等于五,不等于五怎么办呢?向左边走,左边走先让又让二跟五比较。是不是二是不是又又不是啊。二不是,二不是的话呢,他就退回来,退回来过向他的。像这个宋江的右。看这里,如果左地位前要找不到,找到地方,否则继续判断当前节点右右子节点是否不会空吧,因为卢俊义,那么到了卢俊义过后呢,又让卢俊义跟吴比较,也不是,紧接着又向卢俊义的左边,因为每个节点都存在。一个向左向右的递归调用,所以说他找到卢俊义,不是的话,他会先上卢俊义。这个左左子节点,也就说左指数进行这么一个呃,递归的前序查找,那么这个时候他很幸运找到了,找到就返回,那么找到返回,那么卢俊义还有没有必要向卢俊义右边的左右子树经行查找呢?没有必要了,就返回了。
10:15
所以说如果是前序查找,我们一共会比较几次呢?这是一次,这是两次,这是三次,这是四次,对不对?谦虚大脑,其实有四次就OK了。同学们,那这个就是刚才老师给大家分析的所谓的这一个前中后续查找的一个思路,大家看看能不能理解。那讲完这个思路过后呢,下面我们就用代码给大家实现一把。好,代码实现了,我们放在下一个视频。
我来说两句