00:00
各位,我们根据前面的分析呢,我们就把这个代码来给予实现。首先我们先考虑删除叶子节点,大家有发现,不管你是删除什么样的节点,都需要找到要删除的节点target node和查找target loadde的副节点。是不是好,我们先把这两个方法给实现了,那打开我们的ecls,我们开始写这两个方法。那我就写到这里了,同学们,这边我们先写第一个方法。叫什么呢?查找查找要删除的这个节点。那这个节点呢,咱们这样写public就写在load里面就可以了,那你返回一个no,如果你找到就返回node,找不到呢,返回一个空search。1A2C,那你给我一个什么呢?显然你要给个给我一个value,这个大家看到我在这里写一个注释。首先我们看到Y,就是你要你希望希望删除的节点的值是不是?
01:09
那返回值呢?是如果找到返回该节点。否则返回什么呢?No,那下面老师就开始来写这个代码了。呃,首先上来功能,我们先判断。判断,当然我在调的时候,我肯定因为你已经调到这个node节点,这个肯定它是不会空的,对吧,因为你调这个search的时候,你肯定已经是在当前这个节点走了嘛,所以说你不需要在这里判断空,那假如我们写如果你的value,它就等于this.value说明什么问题?如果这个条件满足的话,说明找到。找到就是该顶。就是该节点没问题吧,那就直接return这个Z,那么就写完第一步,那接着往下走,如果不是当前这个节点怎么办呢?
02:01
不是当前这个节点,好,我们就要分这么几个情况了,As if。注听要是一步,如果说你这个要查找的,查找的这个value它小于z.value说明什么问题。说明你现在应当向左指数查找。啊,就是说如果查找的值。如果查找的值干什么呢?小于小于当前节点,那就应该向哪里呢?向左指数,左指数递归查找。是这样子嘛,因为你你的这个值说白了就是你现在你现在要查找,查找的这个值呢,比我这个值要小。比如说我现在是七,你要查的是五,那是不是应该在我当前这个节点的着子数据找,因为你是二叉排序数嘛,这个很简单,那现在呢,我们就来往左指数找,就this点什么呢?Left,左指数是left嘛,我的left。
03:04
第二,什么呢?Search。把这个值放进去,然后返回就可以了,但你这样做是有风险的,同学们这样写呢,看起来好像没问题,其实是有风险,因为有有一种可能性,就是你当前这个节点的桌子节点为空。因此呢,要判断。判断什么呀,如果。注意就说如果左指数或者叫左子节点。左子节点,子节点为空,为空就不能再找了,而且一定。就返回空了,因为你你当前这个要查找节点比我当前这个要小,而且你,而且我当前这个节点桌子,桌子节点还没空了,那这个时候就意味着没有没有了,找不到是吧,就说this,如果我们this.left它等于空。This left,它等于空,说明这是找不到了,那么这时我们就直接return一个no就完事了。
04:02
是不是这个道理,同学们?是这样子的吧,好,那接着我们继续往下写,还有一种可能性。所以如果这个时候呢,查找的值它不小于当前这个节点。对不对,它不小于查找,查找的值它不小于,不小于就是有可能大于或者是等于,那么就应该向它的右子数去递归查找,同样的道理,先要判断它幼子数是否为空,如果它的幼子数已然为空了,那。那就说明不用再找了,直接return一个no,这个就完事了,否则return this.right.value。这就是我们这一个查找删除节点的一个方法,那接着呢,我们继续来写它的另外一个方法,什么方法呢?就是查找。A,我们写出查找什么呢?查找要删除节点的父节点。
05:07
负节点是不是因为刚才我们讲过,你在整个这个流流程过程中,你需要知道要删除这个节点的负节点,你才能够根据不同的情况搞定它。是不是这方应该写一个查找要删除节点节点的负节点呢这个方法,那么我们写一把public,我写一个no,我写一个no,那这个请求search什么呢?Parent。那同样你把这个value也要传给我VE。那这个时候我们怎么去查找这个呢?好,我先把这一帮写一下,这个是要查找的值要。查找要找的,要找的这个节点的值,OK?节点的。节点的值,那么返回的是什么呢?返回的是要删除的节点的负节点啊,如果没有,如果没有就返回no。
06:13
主要是返回它的负节点。那现在的代码咱们怎么写呢?稍微有点麻烦,但动动脑筋哈,动动脑筋,什么情况下就代表你当前这个节点?就是什么情况下表示你当前这个节点,就是要查要删除的这个节点,复节点呢?大家看我写一段代码,大家看能不能看懂,如果this.ne。它不等于空。并且注意听,并且this.left.Y6等于你要查找的这个词,注意听哈,稍微这有点麻烦,那么我先把它包起来。这种情况。满足的话,注意听这种情况满足的话或者。
07:00
或者什么情况满足呢?再接着写this.right它不等于空,也就你当前这个节点的右子节点也不空,并且呢,this.right.value它等于什么呢?Value。好,各位同学。当这种情况满足的时候,各位同学想一想,此时此刻是不是就意味着你当前这个节点就是要删除这个节点的负节点?那么由为什么这样判断一个不等于空呢?因为。你不等于空,说明你你这个节点下面才有才有子节点嘛,而且你不等于空,我才能判断我子节点的值是否是你要删除的这个值是不是这个条件大家应该能应该能看懂。好吧,应该能看懂,好这句话呢,咱们就写到这儿,好,这边应该还少了一个括号。括号这一面太长了,我们换一行这样写,大家看就看的比较清晰了。也就是说,如果当前节点。
08:05
如果当前节点就是要删除的节点的负负负节点就返回。就返回一定要有个条件判断哦,那如果说不是怎么办呢?好,下面呢,我们继续写代码S。如果不是,如果不是的话,下面的代码是要这样写了,如果,注意听如果查找的这个值小于当前,注意听当节点的这个值。就说你要查找的这个值呢,比我当前这个节点值还小,并且注意听,并且当前节点的左子节点。子节点。不为空,不为空,这这有很多条件的限制,大家一定要认真理解啊,大家,大家知道我想干什么事吗?
09:05
我要递归的向左边去找。这个要删除节点的负节点。明白,那我就写一个条件,也就是说如果你的这个value。Value。对,要查的是小于我这个当前的值。并且还要有个条件,并且this.left它不等于空,说明什么问题呢?就说你现在要找的这个值比我当前这个值要小,是不是,我应该按理说应该到我的这个左指数去查找,但是你查找之前是要判断我当前这个节点左指数是不是为空。或者叫左子节点是不是为空,在这个条件满足的情况下,OK,我们就可以干什么呢?向左,向当前节点的左左子节左指数继续递归查找,那就是left.search parent,把这个value放进去。
10:01
这个他看看理不理解,就是向左指数,左指数递归查找。那么还有一种可能性就是l if了,Else if。S。If,否则的话呢,我们再来写一个条件,如果你这个value值,注意听它大于等于z.value。并且this right。this.right干什么呢?它不等于空。那。这个时候就代表我们这个值就只能在当前这个节点的右子数,为什么我这写个等号?因为我房子有可能他这有相同的字,对不对,但是尽量要避免。尽量要避免啊,一般来说,我们在加这种二叉排序数的时候呢,不不要去放有相同的值对不对,但是我们刚才还记不记得,我在添加的时候,在添加这个节点的时候,我们是这样添加的,就是如果小于的话呢,我们是放在左指数的,Else,我们是放在右指数,那就意味着也如果说你真的加了一个有相同值,它也只能在右指数,明白我的意思吧,我这块是有个对应关系的,再说一遍啊,我们在实际实际使用的时候时候呢,要要去尽量的避免有相同这个词。
11:22
好在这种情况呢,大家知道我就应该this.right点。Parent value就写完了,这个其实就是向右。向右注意听向右指数递归查找能理解。那么还有一种情况,就是你这两种情况都不存在。什么呢,就是说。你有可能这个条件满足,但是他不满足左边不为空,或者是这个条件满足,但是呢,他不再满足它的右子数。不为空,在这种情况下,说明我们找不到了。
12:00
大家理解我的意思吗?就说有可能是你这条件,这就这种条件都不满足,那只有一种可能性,那就是没有,就是没有负节点,因为你一个节点有没有负节点,这个这个是有可能是没有负节点的,所以说我就一个空。就说没有负节点,这就是没有找到负节点。负极点哦,最简单的,你比如说我们举个例子,你要删除的七,它就没有负极点。其实没有附件,它就是它已经是根节点了,它肯定就没有附节点,这是有可能的,好那么这一段代码呢,就是我们写的找到它的附节点的这边代代码,也就是说现在呢,我们已经完成最基本的。查找要删除的节点和查找要删除节点的负节点,这个事儿就搞定了。大家看看这段代码有没有不理解的地方?有没有不理解的地方,其实挺简单的,对不对,挺简单的,好,那关于这两个核心的方法呢,我们先给大家写到这里,下面呢,我们继续写。
我来说两句