00:00
好,来。二叉树。删除节点,我们先来看这个二叉树,删除节点呢,它的情况比较复杂。他的情况比较复杂。我们这里面先做一个简化处理,待会儿我们再考虑三种情况,本身它应该考虑哪三种情况呢?一种是。要删除的节点是叶子节点,还有一种情况是要删除的节点下面只有。一个子节点,还有一种情况是要删除的这个节点,比如一有两个子节点。但是我现在先做一个简化,先让大家先考虑进去,然后再。分不同的情况去描述。好,我们现在呢这样做啊。如果删除的。节点是叶子节点。则删除该节点,这个很好理解,比如五和四,它下面没有节点的,直接干掉就完事。还有一种情况,如果我们删除的节点是非叶子节点,理论上来说,比如说我删除三,按理说呢,应该把这个三。
01:08
删除了,删除完了过后,呃,让五或者是顶上去,但是我现在做一个规定啊,我做一个先做一个简化的约定,就是说如果删除的是被叶子一点,把整个数就全部删掉。后面我们再说这个分开三的是怎么处理好,现在呢,我们要求做这样测试,删除五号叶子节点和删除三号指数,就是说第一种情况我们把这个五删除。第二种情况,我们把这个三整个这个指数干掉。那这个代码好不好写呢?我们来看一下它基本的思路是什么样子的。他基本思路,我们先来搂一圈,简单的看一看它的基本思路。首先。我们要这样去判断,如果你左边就是我在三的时候,我先看你当前这个节点。
02:03
它左边是否为空。如果不为空,它左边跟这个编号相同。好,我就直接怎么样。如果它左边不左,它的左边不为空,同时左边又等于这个no,我就把左边之空return,那就相当于什么,相当于把这个左边这个就就干掉了。右边也是一样的处理。这个地方大家看我这种写法,其实是没有考虑,呃,下面有没有指数的对不对,没有考虑都直接干了,所以说他其实不管你是非业绩节点还是指数,它就统一了。呃,这种是一种简化的处理方案,肯定在实际开放中不能不能这么干,除非人家就就就是这个意思,那你这么干,因为更多的情况是三删掉这个三就是删掉三,而不能把五和四干掉,对不对?啊,我们待会儿会做处理的,然后你这个做完了以后呢,有一个问题,假设你当前这个节点不是要删除节点,你是不是仍然要向仍然要向左递归和右递归去删除啊。
03:07
搜索代码非常简单,来,同学们,我们给大家简单的写一下。打开我们。我还在这写了,没有办法啊,都在这写,那下面呢,我们还在这写bary tree。我们就写到上面去啊,写到这儿。小字我们来写,删除节点。删除节点,首先我们先把这个删除节点的规则给大家捋一捋,刚才这个规则规则我已经说清楚了。就是这个规则。就说我们不考虑,呃这个你是不是,呃有这个子节点通通干掉了,这是我们的规则第一个。第二个这个规则呢,显然对我们写代码起到了一定简化作用,对吧,很简单,但是呢,后面我们还要去考虑更复杂情况,好写delete no。那同样你要你要删除一个节点,你只需要告诉我你要删除哪一个编号就行了。
04:07
根据刚才我们的思路,首先比较。首先比较。比较当前节点是否为要删除的节点。是否为?哦,是否为。要。删除的这个节点。对吧,就跟我刚才说的准确的讲。是比较的,是当前节点的。下一个节点,因为你当前,如果你都已经找到当前节点了。那你写其实是删不了的,对吧,所以说这个地方应该这样说,你看我这代码一上写的,我是这次点na na.no不是这个no直接比较的,所以说我这个说法有问题,首先比较当前节点的。左子节点这样子说就对了是吧,左止。
05:01
指节点是否为要删除的节点为,为什么呢?因为如果你真的找到当前节点,你删不了,我们是单向的,也就是说我目前,我们目前这个链表它没法实现自我删除,除非你做的是这样一个结构,有没有这种自我删除呢?也可以,除非你做的是这种。这种数。就是双向。二叉树有没有呢?也有这种树就叫线索二叉树。啊,这种这种书呢,就能够实现自我删除,比如说我要删除三号,我就找到三号,我也是能够把它干掉的。这个我们在学双向链表的时候说过这事,但是目前我们是单向链表。哦,单向的这么一个什么呀。单向的二叉数,所以说你只能是,比如说你要三三这个节点。你肯定是在这个位置。先做的就是说你先判断这个节点的左边或者右边是不是要删除的,你才能干掉卢俊义。
06:05
不然你没有机会干掉他,是不是这个道理啊?这点大家一定要清晰的知道啊,我这里就呃说到这了,所以说我们这写的是首先比较当前节点的。的。左子节点是否为要删除的节点,好,那下面代码就非常简单了,就if this点首先要判断这个不为空,如果为空你也不要再删了,就退出就行了。并且。This是点nap.no它刚好就等于你要删除的这个值,好同学们,那你就放心了,左边刚好就是你要删除的,那就简单简单,就它的左节点直接制空。下面也就别别走了,直接return。好的,那还有一种可能性。就是嗯,如果左边它这个不是你的,那就还有比较当前节点的右节点是否为你要删除的节点。
07:02
啊,然后比较当前节点的右子节点。右。又,诶,又到哪去了又。呃,第一个就是是吧。这跑过去了。不是不是这个用吗?又右子节点是否为要删除的子节点,那简单咱们就写一辅已去。this.right你一定要有这个动作,同学们,我们在写很多人出血出写二叉树的时候经常把这句话干掉,会有控制针啊,如果它右边不等于空this.right.no又刚好等于这个你要删除的编号,那这个就简单了,那就直接this.right。等于这个空。OK,然后不走了。对,那如果这这个当前节点左右都不是你要删除的节点,怎么办呢?好,向左。
08:04
就向左递归删除。然后是向右。因为左边也有可能没有向右递归删除,所以说这个语句非常重要啊,非常重要,那现在呢,我们来看一下,如果向左递归,那显然你首先要判断左边不能为空。二唯空也无法递归。那如果它左边不不空,就是Z是点left.delete。把这个no传进去。同样的道理对吧,同样当然你这个这个地如果成功了的话,呃,这个他如果成功他就返回去了嘛,如果他有一个,因为他往里面递归,它肯定会如果他唱到就return了,所以他不会往下走了,那同样道理,如果。认点right。对吧,认识点red不等于空,不等于空,那么我们就向右边递归啊,右边递归。
09:02
Right。Right。Right,这个地方是不是最好有个return?要不要return同学们?哦,不用是吧,上面有点delete。Delete定delete过后,定delete过后呢,我们这边写上这个no。一个是向左递归,一个是向右递归,删除。向右低维生素,那么我们现在呢,来来看一下这个对不对。来测一下。好,同样道理啊,我把这个检索这个先去掉,我们先来删除一下,测试删除节点,呃,我们这不是有要求吗?我们测试的是删除五号和删除这个三号对吧,那我就测这两个节点看看对不对,我先删一个五号。呃,五号的话也非常简单,就battery tree。Battery。
10:00
点delete。啊,我是不是还你们还没写啊,不好意思,这没有没有调,它这边还要写一个方法。在我们的这个better tree里面,我们还要写一个方法,DD到漏,因为根节点在人家这些地方,所以你没有办法,你只能这样去处理一下,然后。好,那现在呢,我们就做一个判断,如果你这个root本身就等于空,那肯定没有办法去删除,所以说只有不等于空的时候,我们才去删除这个节点,那我这写个no。否则的话呢,就不去处理了,就直接就就不玩了,也没有什么else,这句话他不进去不就不执行了吗?好,下面呢,我们来调一下。找到我们的主方法,OK。现在我们来调delete,写一个,我写完五,我怎么知道他被删掉了呢?很很很对,刚才同学说的很正确,我们随便找一个方法来便利,好吧,我们就找一个情绪便利方法来变一下。
11:05
看看它有没有变化就可以了,来走一个。那么如果这个五号同学们看一下啊,如果五号真的被删除了,他的输出应该是怎样子的呢?我们来看一下。五五号如果真的被删除,用的是又是前序便利,那就应该是1234对不对,好那。看看这个结果对还是不对,就应该是1234,同学们,我们运行一下。我们运行完完了之后,我们发现这个结果呢,跟我们想的是一样的。好,我们再来删除一个。有子节点的一个节点找一个三号,我们把它干掉一下。如果我把三号删除,这个结果就是一二是不是,那我就直接执行,看看有没有抛异常。对好以上OK,那现在我们还有一个问题,同学们,如果我们删除的就是这个,一会出现一个什么问题呢。
12:06
诶同学们,我们这样写,假设三的一,大家看会有一个什么恐怖的问题啊,来看一下,如果删除,一来各位运行。我们发现这个地方,诶,你看一个都没删掉啊,为什么呀,同学们。因为他,因为你这样子根本就进不去啊,你想一想这个地方的问题在哪里,我们打开大代码,你看这里。因为你在整个这个,你在整个这个D的过程中,我们注意下。你上来过后,它不等于空,你就直接往里面走了是吧。可是你你在走的过程中,这个route。他他自己没有机会跟自己比啊。是不是因为我们不是找的要删除节点的下一个节点,它其实把root就跳过去了。能理解吧?他把弱叫过去说,你这个代码就错了,那怎么解决呢,同学们?
13:00
怎么解决呢?是不是,如果你这先判断一下,因为你进去过后就直接判是以root这个往入的下面找的,所以你这边要先预处理一下。先处理一下这个root是不是要删除的,是不是这意思啊,那这个就应该这样写了,如果你刚好走了大运了,这个root的点no。它就等于你要删除的no,那这个道理就直接把这个root制空就行了,那相当于整个数的被干掉了,是这意思吧。否则你才去走,我们的真正写的这个代码是这个逻辑吧,好,同学们,我们现在再来执行,你会发现这样子呢,就一科。一什么都没有了,就是个空的。没,没问题吧。代码是正确的,好同学们,那这个删除删,关于这个节点的这个比较简单的删除方方案呢,我们就先给大家讲到这里,好我我们把这个代码简单的整理一下。
14:04
我们在接着讲下面的,呃,这个这个其他的内容。好,我们来看看刚才我们讲了哪些内容。刚才我们这块讲的是便利。嗯,便利现在我们讲的是一个查找和删除,对吧,诶我们来看一下。二叉树的遍历我们是在前面已经讲过了,然这讲了二叉树查找的三种方式。我们写到这里来。二叉树的。这个查找的方三种方式,那这里呢,我们一共用了三种方式来进行这个查找,对吧?那么这是我们的代码实现。代码实现。和思路分析,首先我们把这个思路分析给同学们,诶,拿过来。这个思路分析重点就是放在这里的。
15:01
后面的分析我就直接写在代码里边的,大家应该有个印象,我把它放过来,那具体代码呢,给同学们放在这边了啊,代码我这就其实已经写在一起了,那那怎么办呢?好,我还是给它就放在一起吧,啊放在一起无所谓,因为这是整个代代码放在一起,我把那个诶。具体的代码用不同的颜色标一下,我就找一个前序查找就可以了。就把这段代码大家看一下就行了啊,我标成一个蓝色。啊,然后在我们的这个root里边还有一个。呃,在这个节点里面还有一段核心代码。啊,在哪呢?在这诶前去查找。这段代码其实是它的和。核心好,这边我们给大家标一下,好,同学们看这个代码就能看到大概是哪个位置。好,这个说完了以后呢,我们又给大家讲了一下二叉树的删除节点的这么一个方式,当然这个方式呢,还比较简单,没有考虑到,呃,下面的有没有节点的问题啊,OK啊,现在我们把这个节点删除也给大家整理一下。
16:15
好,往下拉一拉。OK。那这个具体的要求是刚才我们标出来的。好,那直接把代码翻过来了啊同学们,代码。呃,思路在代码里边,在代码中。输入在代码中,自己到时看一下代码就能看出来,还把这个复制一份吧,无所谓了。啊,刚才应该是写完一个就复制一份就好,好同学们,那关于这一部分我们就先说到这。
我来说两句