00:00
OK,我们接着写代码,那刚才呢,我们写了这两个方法过后呢,实际上真实的调用呢,还是要放在我们这个by salt tree里面,是不是。所以说我还要把这。把这个load里面的这两个方法呢,呃,封中到我们batter。这个脆。那下面呢,我们开始把方法放进去。OK。这里面仍然是查找要删除的,删的节点能理解吧,那就写public。Node,然后呢,Search,同样你把value给我。对不对,那我这里面做一个判断,如果说这当前我们这棵二叉排序树,它的root等于空,那这个时候就不用多说了,直接返回一个no,也就是说我们没有,那么还有一种情况呢,就是root不等于空,Root不等于空呢,我们就return。
01:02
我们就return root,点什么呢?Search,把value放进去,这是第一个方法。那接着我们封装第二个方法就是查找负节点。负节点,那public。同样我们也是返回一个node,那这写arch。Parent parent,别写错了。Parent,同样你把这个值给我对不对?那我们这边还是跟刚才一样,如果root等于no。如果root等于no,那么我们也返回一个空,就代表没有,没有找到负节点else else,如果说route不等于空,我们就调用root这个节点的search parent,把这个放进去。好,同学们,这是把刚才写的查找节点和查找副节点的方法呢,封装到了battery short tree,那现在呢,我们接着写,最核心的方法就是删除节点。
02:05
删除节点,OK,那删除节点呢,我们就开始写public void delete no,同样你把这个值给我对不对?把这个值给我的话呢,我们现在就开始做一个动作,如果我发现这个root的确是等于空,那么这个时候下面的代码就不用走了,直接返回一根,直接返回就行了,Else。Else,根据我们刚才这个思路,再删除一个节点的时候,先去需要先找到,先找到要删除的这个节点,他给弄的先把这件事情搞定,这个事情现在对我们来说已经很轻松了,因为刚才我们已然把这两个方法写出来了,这样子吧,说到直接调用search。把这个value传进去,让它返回这个查找到的节点,那这个节点我们取个名字,就跟刚才我分析的一样,我们就叫target,就目标。
03:01
Target。A target什么呢?No?他给漏的好,那现在查找这个查找要删除的节点,就有就有一种可能性没有找到。因为你你要查一个值,这个值不存在是不是有可能的,所以说我做一个判断,如果。如果没有找到要删除的这个节点,那下面的代码就不用走了,是不是,那所以说我判断一下,如果target。它等于no,说明什么问题呢?说明没有这个要删除的节点,因此直接return好,接着继续往下走。哦,这个地方还有一个小问题啊,同学们。呃,我们这边还有一个情况要考虑。就是嗯,如果说我们找到的这个target node。他没有负极点,就是说target note是找到了,但是这个target note没有负极点,这个情况是不是。
04:01
也就不需要执行。下面。也就是说不需要再执行去找target node的parent的,就是不需要再执行这一句,找到target node的负节点,这这个这这个动作就不用再找了,明明白我的意思吗?啊,我不知道大家知道我在说什么没有啊,就是这样子,如果我们发现发现target target load。Target node没有负节点。那么我问大家,如果target的note没有负节点?什么情况下是有可能发生的?就是你你在这个进行进行这个删除的时候,删除的就是我们这个。负节点。是不是删除的就是这个根节点,这种可能性是存在的。可能性是存在的,或者说,或者说我们这样认为,就是当我们这一个节点,当我们找到这个target的时候,他的他他在。
05:06
找到这个target的not过呢,我们发现root的na和right都等于空,那说明你当前这个数呢,只有一个节点,明白我的意思吧,没有负节点,或者这样说,或者这样说啊,这这个说的有点不对,应该这样写,就是如果我们我们发现发现当前这颗追听。这颗。这棵二叉树,二叉排序,排序树只有只有最后一个节点,只有一个节点。一个节点。那么我们也就。也也就把这个节点删掉就完了,那怎么写呢?如果我们发现root.left。Root left,它等于空。OK,并且root.right也等于空。
06:00
在这种情况下,是不是就意味着我们整个整个二叉排序数其实只有一个节点?而且而且很可惜的时候,你你还就查到有一个要删除的节点,那说明你要查到这个target not,它就是这个root节点,而且这个root节点呢,还只有一个了,因为你你你这个地方。没有return回去那。这个条件有满足,那说明你要删除这个节点,刚好就是root节点,而这个root节点下面左右两边还没有了。那就说明你现在当前二叉排序数只有只有一个节点,而且删除的就是这个节点,怎么办呢?那就简单了,直接自空就可以了。直接把这个入字空返回就可以了,大家理解我的意思啊。这个大家一定要理解好的,那如果说我们找到了这个target load target load,而且呢,他不是只有一个节点,那下面呢,我们就来判断,就来去找什么呢,找到。找去查找啊去查找。
07:00
去找到什么呢?Target这个地方要稍微慢点,Target no的负节点。好,现在呢,我们来调一把就no。No,我就写了啊,叫parent,这样好记忆,然后呢?Parent,把这个纸放进去。同学们,你找这个附节点,有没有找到这个?这个地方呢,我们要往下面继续去判断。继续去判断,好,现在呢,我写一句话啊,如果要删除的。节点,如果删除的节点是什么呢?它是叶子节点。有没有一种可能性,就是现在我们考虑的是。叶子节点的情况好,那如果是叶子节点呢?我们来做这样一个判断,如果什么呢?同学们看,如果你这个target node。如果你这个target not点。
08:01
对,听等于空。等于空,也就是说你这个target load呢,它是等于空的。如果等于空,并且。并且什么呢,Target node。写到这,Target node.right。啊,也等于空。这说明什么问题?这说明此时此刻,这说明此时此刻,你这一个target就是一个叶子节点。是这样子的吧。是不是就是业绩的,因为你左右两边都会。对位空了,说明他就是个叶子节点,如果是叶子节点的话呢,根据我们的思路,就应该按这条道路来走。那就先要先要判断target node是parent的左子节点还是它的右子节点。然后根据不同的情况来处理,那下面我们就来写这个东西啊,好跟上我的思路判断。判断什么呢?这个target target load是。
09:05
负节点的,负节点的什么呀?负节点的左指左子节点。还是右子节点对不对,还是有。右子节点还是右子节点?那么我们要做一个判断。我们要做一个判断。那怎么做呢?如果说如果我们发现parent。点left。就是这个你不节点的左左左子节点,它不等于空。不等于空,并且,并且parent的left。Left,呃,我看看这样写啊,left.right嗯,Value,它就等于什么呢?Value说明什么问题?各位同学,如果这个条件满足,说明。说明你的这个target loadde就是我这个parent是,就说你要删除的这个节点是他的是副节点的左子节点,是这样子的吧,如果是左子节点,根据刚才我们的思路,只要把parent的left置空就可以了。
10:18
对不对?好,那么还有一种情况,As if,注意听,还有一种情况就是parent,点它的right。不等于空。并且还满足什么呢?点right.value它等于什么呢?等于你要。删除的这个值。那说明什么呢?说明你这个要删除的这个节点,也就是他loadde是它的负节点的右子节点。这行啊,是左子节点。这个稍微有点绕,这边是什么,说明是右右子节点,我这边呢,做了飞空我才去。
11:03
处理的,那这个时候我们要做的事情就很简单,就是parent点什么呢?Right等于空。好,同学们。那关于。要删除的节点是叶子节点,这块我们就处理完毕了,那现在呢,同学们我们来试一把,看看是不是能够测试成功好,呃,现在呢,我们以哪个为例呢?以还是以这个图为例,假如我们这有个二,好,我把这个二也加进去,同学们。放进去啊,我们先便利一下,目前我们这棵二叉排序树长得什么样子,123579442没问题,现在呢,老师给大家做一个演示。现在我们来测试一下删除叶子节点。各位。那删除椰子页呢?非常简单,我们better short delete node,把这个二放进去。放进去之后呢,我们再输出一下这个中序遍历对不对,就说删除节点后。
12:06
现在呢,我们继续便利吧。继续编吧,Better tree solid tree.infe order,好,我们来运行一下,看看二有没有被干掉。同学们可以看到二呢?的确没有了,我们再尝试着去删除另外几个五九十二好,我分别删除,那现在我需要把这个先去掉,因为你你删了过后就有可能影响其他的其他的节点,对不对,所以说我一个个测点delete。现在呢,我们再来测试一下,删除。五这个叶子节点五看看有没有问题,五好运行值我们发现了,五也没有问题,删掉了,我们再删除一个九。好,把这个先删掉哈,先先先注销一下,这边呢,删除个九,九也是叶子一点发现了,九也被干掉了,没有问题吧,还有一个节点也是叶子节点就是12,我们试一下12。
13:07
试一下,12找一个batter tree.delete12。我们运行一把。这时呢,我们发现12也被干掉了,所以说到此呢,我们这一个删除叶子节点的这段代码就写完了。而且呢,我们测试也是没有问题的,没有问题的对不对,那甚至你还可以这样测试一下,比如说我们把把这个二删掉以后再删一一也是一节点的,明白吧,你可以试一下嘛,你其实我们如果这样删,先把二删掉。一也变成业绩节点,那就可以删二一五九十二都可以删,你不相信你可以试一下,来我们玩玩一下,先上二。再三五,再三九,如果我把这四个节点删掉的话呢,同学们应该看可以看到是不会出问题的,因为你二五。
14:03
92都是液体点,你看我三下。你看同学们看,没有任何问题吧,其实这个时候你在删一也是可以的了,为什么删一也可以呢?因为此时此刻,呃,这个一,你因为你把二删掉以后,这个一呢,也就变成叶子,叶子节点了,所以说如果你要把一删掉,它也是OK的,你看我删一个一,但是你要在在这后面写啊,你看我删一个1.delete我三一同学们看也不会有问题。删掉了吧,但是你不能这样干啊,说说老师我上来过就删一这个不行。如果你上来就三一的话,我们是不是还没有处理,还没有去处理,有一个叶子节点的,有一个呃指数的,或者叫子节点的这种这种节点啊,如果你这样删肯定要出大问题。你看啊,假如我直接上,呃三一,你看这地方肯定是要出问题的。一没有删掉,没有,因为它这个一他不是叶子节点。
15:02
那为什么我把二删掉,我把二删掉,再删一这个就可以,如果把二删掉,它已经变成一个一,就变成yes子,你再删也是可以的,你看这样写也是可以的,看一二都没有看到没有,好了,同学们,那关于这个删除叶子节点的代码实现呢,就先给同学们。呃,就是写到这里一会呢,我们接着下面马上接着去完成另外两种这个节点的删除。
我来说两句