00:00
最后一个呢,我们要来分析一下了啊。最后一个是这样子的。就是删除有两个子节点的。要删除一个有两个,我们先说这个思路。先说一个思路。什么思路呢?就是说怎么来把这个有两个子节点的这个节点干掉,我们举一个例子。我们还以这个七为例。先把这个思路捋一捋。好,我们来说删除有两个的,比如说现在我删除的是七这个节点。好,我现在说一下,删除有两个。两个子节点的这个节点。比如这里的七。好,现在假如我们要删除这样一个节点,我们应该怎么删呢?好,第一步。第一步,首先首先找到。
01:01
找到这个七。所在的。就是这个这个七它是target,它要它要被删除七这个元素。元素。它这个元素的什么呢?它的幼子数的。幼子数的最小值。他是不是要找到这个七所在的这个左指数的最小值,然呃右指数啊,右子数的最小值,因为最小值其实就是。左指数的最大值了,最大值好,这是第一步你要做的事儿。第二步。你要干什么事呢?就删除这个最小值。不着急啊,删除这个最小值,因为你反你这个找到这个最小值的时候,这个值实际上你是可以得到的。你可不可以得到,可以得到。
02:00
可以得到这个最小值,然后你又删除这个最小值,相当于说你把这个干掉了。没有了。我们把这个做一个小叉没有了啊。如果没有的话,然后第三一步。将。将这个。将这个七。其实这个七就是你的target。Target。Target的值修改成。最小值。那你修改成这个最小值以后。同学们,你这个七是不是就变成了九?请问。如果你把它改成一个九,那同学们可以看到它仍然是一颗。这个有序的,这就是二叉排序数。那么这边难不难呢?看起来趋势挺难的。啊,但好就好在。好就好在前面我们删除的方法。
03:02
已经写完了。就是第九步那个查找的方法就已经写完了。啊,那么现在呢,我们来做一下啊,首先我们写一个方法。我们来找一个方法找到这儿。我们就在这儿直接写。呃,我们是在哪里面写呢,在这写。就在这个search里面,我们写一个方法。写一个方法干什么呢?就是删除。某个。指数的。最小值的节点。病。并返回最小值。这个有问题吗?没有好写一个啊,我就写了啊,定力。我们删除的是哪个指数呢?又指数的。右指数的啊,右指数,那这个我就想delete这个right。Tree。
04:01
啊,删除右边这个这个这个数的最小值命。好,那你这个地方呢,呃,要给我一个什么东西呢,是不是要给我一个节点呢。因为你你要上这个指数,你要给我节点嘛,我才能干掉它。好的,那现在呢,我用一个,呃,临时的一个目标啊,目标节点来搜一下。VR,比如说我有个target。我就从这里开始干的吧,好,然后呢,我就一个no,那你怎么找到这个右子数的最小值呢?哎,同学们,你们你们应该知道,在这个右子数,只要往左边不停的找,找到最后那个为空的是不是就是这个数的最小值。是不是好,这个思路就清晰了,好使不用递归都用不上,对吧,使用这个什么呢?使用一个外循环。是不是不用递归啊,向外循环找到。
05:01
循环找到这个数就是这个幼子数的。右右。又指数的最小值,这个好不好找呢?其实非常好找,只要你这个target。他的next。它不等于空。啊不,他给的点next嘛,诶这个对说的right right啊嗯,因为它next往往左边走,只要它不等于空。啊,只要它不等于空,我们就怎么办?同学们是不是target就不停的往左边跑啊?能理解吗?那好。左边最小吗?是找右边指数最小值,是不是往左边找啊,我没写错吧。我先我我知道我还没切,到时候你不着急,我肯定要传的是一个右,就是找到那个target过后,把那个target的那个右指数那个跟那个节点给他就行了嘛。
06:03
诶对不着急啊,这个写完了过后,是不是我要把这个值保留一下呀。因为我这个纸到时我要用嘛。我为什么要用,我还要替换它,是不是说我把这个纸拿到。这这个就是最小值了,能理解吧。Value这个最小值是不是就是你这个target里面的这个value。是吗?然后我们要做一件事情,干掉这个。干掉这个target。好,干掉他,是不是我们写了个今天漏的已经写完了。这个need。Not,诶,这个地方叮叮咚咚怎么没有了呢?在哪儿写的?哦,我们这写的有啊。Delete node。哦,不好意思啊,这个地方咱们不要写,不用写到这儿。就说这个地方完全没有必要写到我们这一个节点里面。是直接写在哪个里面,写到这个数里面就可以了,是这意思吧。
07:02
呃,刚才我们犯了一个错误啊,应该写到这个里面,为什么?因为你这个是针对这个数来做的是吧,所以你这边应该这样子做就对了,刚才我们写的位置不对,这个就是删除什么。我们就要删除这个最小值的对应的点,最小值对应的这个节点。啊节点,那么这个节点咱们怎么删呢?你刚好已经有了,把这个最小值放进去就可以了。是不是?好,放进去完了后是不是要把这个最小值返回去。返回,返回的话是一个int值。In的词的话呢,这边就有一个迷。好的,整个整完了以后,同学们,我们只需要在哪里加一段代码就可以搞定了呢。在这儿。怎么做?这个地方target是不是已经拿到了。好,你要做的就是找到最小值并删除,直接调我们刚才那个方法叫做delete tree,把这个谁判给他,是不是target.right给他。
08:08
是不是这个他给的左右指数就给人家了呀,就给他完了过后你是不是得到了一个值啊。是不是得到一个值。这个值是不是你这这个方法是不是把人家干掉过后,还把这个最小值返回来了,然后你在做一件事情,什么事情,把target load.value置换成这个。Value。诶,这为什么错了。哦,哪个地方写成只读了。V4。那这个地方是吧。不是,这是这个target no target load是。好的,我们这边也要有问题了,因为我们当时没有考虑到要去修改。这么改成R就可以了。看这边应该就没有报错了吧。没有报错了啊,咱们写完了,写完过后我们来测一下,看看OK不OK,这个不好说是吧。
09:03
这个东西因为代码太多了,而且全是递归啊循环的,我们试一把吧,刚才这个一是不是我们直接就干掉这个七号好不好。七号是不是就是我们这个。这个值啊,好,我们运行一下。运行好,我们运行过后看这个结果。看到了没有?干掉了。干掉了,那其实这个干掉这个七,这个结果呢,其实你们也可以测试干掉十,这个结果也是一样的,比如说我把这个改成删掉这个十。删掉这个十。OK,同学们,我们再进行一下,看这个对不对呢。哎,我们发现是吧,也也没有错是不是。说明这段代码是没有问题的。大家看,这就是一个。这个数啊,虽然这个代码我们在上一个节点的时候稍稍微遇到了一点困难,但总体来说还算比较顺利,毕竟这个代码是咱们现场敲代码还是。
10:03
有有一点就是难度的,就说你要是第一次写对吧,可能写着写着也容易蒙圈,好这是我们这个。二叉树的一个这么情况,我们来把它代码整理一下,后面还有一点内容啊,最后一点几句话就说完了。那刚才我们讲的是什么东西呢?刚才给大家讲的是一个二叉排序数的。呃,一个内容。首先我们给大家看了二叉排序数的需求。对,我们先说了一下二叉排序数的,呃,一个这是大的啊,这是大的二叉排序数,我们先说了一下一个需求。对,看一个需求。那么这个地方我们要求对这个一个数组来进行排序,我们可以形成一个二叉排序数。这是第一个,然后这个说完了以后呢,我们给二叉排序数,呃,说说这个它的一个好处,这个就不说了,然后呢,我们说了二叉排序数的一个基本介绍,就什么是一个二叉排序数呢。
11:09
在这个比里面,咱们就写的比较清晰。对吧,然后这个二叉排序数,他这个示意图也给大家拿过来。这是二叉排序数的一个示意图。二叉排序数示意图完了过后呢,我们又给他讲了二叉排序数的创建,遍历、删除。当然有人说添加没有讲第一个就就讲到添加了。啊,第一个就讲添加了,所以这边呢,我们就讲了二叉排序数的各种用法。啊,先讲的是这个便利,还有创建这个讲完了过,讲完了过后呢,我们又因为代码后面是一个整体,我就放在一个整体后面,又给大家讲了二叉排序数的删除,那二叉排序数删除呢,情况相对比较复杂。对吧,我们考虑了有这么三种情况,尤其是第二种情况,这个稍微容易容易蒙圈。
12:05
啊。其实第一种情况和第三种情况反而比较简单。OK,因为他要考虑到你删除的这个节点是它的左边还是右边。好,这个呢,反正最后我们还是把它写出来了,然后最后呢。呃,这个各个删除直接点下面的代码,我就不一个个的说了啊好,我把这段代码给大家放到这边来。其实就一段代码,就这块儿。啊,一共大概。200多行。好,把它放到这儿。代码整理就是二叉。排序数的一个代码实现。代码实现。那代码实现呢,我就直接放在这里了。好,同学们,最后一个,我把这个就说完了。
我来说两句