00:00
各位同学,我们来继续学习二叉树的删除,那前面呢,我们给大家介绍了二叉树的创建和便利,对吧?那现在我们来看看下一个二叉树的删除,那首先呢,我们先要把二叉树的删除它的几种情况给各位同学分析把。那么二叉树的删除呢,它的情况比较复杂,应该有三种情况需要我们考虑,第一种呢,删除叶子节点,也就是说你删除的这个节点呢,它是叶子节点。它没有左指数,也没有右指数,比如说我们这里的二五九十二。像这个二。五九十二,它们就是叶子节点。这是第一种情况,那么第二种情况呢,我们删除的是只有一颗指数的节点,也就是说你先删除的是一个指指数,但是这个指数呢,它只有一个节点,你比如说我们的这里的这个一。
01:00
这个一呢,它就只有一颗指数,就是它下面呢,相当于相对于说它只有一个子节点,但是这个节点呢,可以看成一个指数,明白还有一种情况呢,就是删除有两颗指数的节点,你比如说我们这里的七。三和十这个呢,我们可以认为它是有两颗指数的节点。对不对,好,那么当我们有了这个概念以后呢,老师先给大家分析一下这三种情况,我们删除的一种思路,因为你先有思路,我们才能走代码,那各位同学打开我们的Excel。我们给大家聊一聊,就是我们二叉排序数删除节点的这么三种情况,我们分析吧,或叫图解。图解什么呢,二叉。排排序数的。呃,二叉排序树删除节点的这么三种情况。
02:01
三种情况。好的,同学们,我们来一起看一看。好,我把这个图放在这里,那各位同学现在呢,我们一边说我们一边讲,我们先说第一种情况好不好,先说情况一。第一种第一种情况,那第一种情况呢,就是同学们刚才说的,呃,给各位同学介绍的删除叶子节点的这种情况,它的一个删除思路是什么样的呢?我分析一下。分析删除,呃,就直接写就行了啊第一种。各位朋友。那大家看,假如我们删除的叶子节点是五二五九三二五九十二,我的思路是这样子的。我的思路。思路如下嘛,第一种我们首先要去。
03:01
我们首先去要要去找到这个要删除的节点,或者说我们首先要确定你要删除的节点是存在的,大家明白我的意思吧,所以第一个呢,我们需要。需要先去先去找到或者定位找到要删除的这个节点,比如说这个节点我们叫做target。Target node。OK,这是第一步。你首先要干这件事情,这个大家能理解吧,你找不到那就那就没办法删除吗。第二个,因为你在删除节点的时候,大家有没有发现,比如我们要删除的是二号节点,假如你现在呢,已经找到了这一个。目标节点。那大家想一想,你找到这个二,这个节点,你能把自己删除吗?显然你删除不了的,因此呢,你还要找到这个三。目标节点的负节点是不是这样的道理,所以说按我的第二个思路呢,然后再找到确定。
04:04
在找到。找到什么样就是target。Target no的负节点,负。负节点。那么各位同学这个负极点,比如说我们取个名叫parent load。就叫parent吧。OK,没问题吧,Parent。那当然这里面情况就比较复杂了,有可能你要删除的这个节点,它并没有负节点。这里面你还要考虑有没有这个负节点的问题,对不对,还需要考虑是否存在负节点。那有些东西为什么要考虑呢?打打个比方,比如说你上来删除的就是七。对,他有可能就没有啊,当然如果是对于子节点来说呢,它是它是不用考虑这个问题的,所以这个呢,我们可以先先不考虑啊,先不考虑第三种,第三个当我们找到这样一个节点的时候,其实下一步我们要做的事情是要干什么事呢。
05:05
你找到这个节点,你还得判断它load是这个负节点的左子节点,还是它的右子节点。然后你就能删除对不对,然后再继续判断什么呢,确定。确定target。对,Target node是什么呢?是父节,是parent的。Parent的左子节点,左左子左子节点。左子节点还是右子节点?又子节点。然后再确定删除,因为你如果不能确定它是它的左子节点还是右地点,你是没办法删除的。这边就有好几种情况。好,那下面我就写第四句话了。根据。根据前面的这个。呃,情况来决定来。
06:01
来对应删除啊,来对应的删除,对应删除,因为如果你这个target node是parent的着子节点,那。你应该这样删,如果是左子节点,左子节点,那你删除的时候是不是这样子,parent.left等于一个空就可以了。那如果它是一个右子节点呢?右子节点是不是你这个parent.right等于空。是不是这样子的,所以说你这个情况呢,是不同情况有不同的处理,好这是我们说的。就是。呃,就是删除节点的第一种情况,第一种情况,那下面呢,我们继续来给同学们分析一下删除节点的什么呀,第二种情况。那大家想想,如果你要删除的是第二种情况,也是我们所说的什么情况来看第二种情况。
07:03
第二种情况呢,我们刚才分析的是这种情况就是删除只有一颗指数的节点。一颗指数,也就是说你删除的这个节点呢,它下面还有一颗指数。举个例子。比如说我们这里所说的一。比如1OK,比如一。一号这个节点,那你这个时候你的思路又应该是怎么样子的呢?你这个时候思路应该怎么样子呢?前面肯定是一样的,要找到要去要需要先找到这个删除节点,再找到他给的附节点,这个肯定是一样的。说前面这两个步骤没有问题。他的思路。跟前面一样,这个OK。那下面呢,你要做的事情是什么样的,同学们?那因为你要删除的一直节点只有一个节点,所以说我们要确定确定这样一个情况。
08:02
确定什么呢?这个问题要注意啊,要确定。确定这个target。他可以,呃,应该确定他,诶这样写啊,注意听这个稍微有点麻烦啊,Target mode。有的,应该说确定target的子节点。子节点。是左子节点,左指节点还是还是右子节点。右。子右子节点。诶,这个写错了,右右子节点。好,为什么你要确定它的子节点是左还是右呢?因为你后面在删除的时候,这个方案它是不一样的,明白这意思吧,因为你这个不同的情况,你处理的方案不一样。好的,这个确定完了后呢,你还要确定一件事情。你还要确定一件事情,就是你要确定target node,注意听啊,Target node。
09:06
Target target是parent的。Parent的左子节点还是右子节点?左。左。指节点。那这个老是这样子啊。左子节点还是右子节点?对不对,还是右子节点,也就是说你还要确定你这个target not是parent左侧节点还是右子节点,那么这个时候呢,就有四种情况。说为什么有四种情况呢?好,你听我说,如果。呃,啊,这个有点不好写啊,呃。这样写吧,如果target的子节点是左子节点,这样说,我们这样说,如果target。Target是parent的着子节点。
10:00
假,假如是啊,假如说如果target,如果target的是parent的左子节点,那么分成两种情况,5.1什么呢?呃,就是target的子节点是又是左子节点。这样写,并且呢,它的子节点是左子节点,那么我们删除的时候,它就应该怎么写呢。应该怎么写?那就是parent。点left。对于target。No。Left。是不是?是这样删除,那如果说你这个target是是它的target的子节点,是它的右子节点。追听又几年,那么你在这一方换掉的就应该是什么呢?郭同学,如果。呃,也也就是说target的子节点是右子节点,那么应该是parent.left。
11:01
是不是他的,我想想啊,是他的。右子节点。他target是parent的镯子节点。左子节点,那么这个地方我们就应该写成什么呢?大家想想应该写成什么?应该写成什么,是不是应该写成这样一个东西。那么这个时候我们应该这样写,就是因为你是。那就是这样写的,Left等于什么呢?等于它的right。对吧,但这样子呢,我们到时间代码实现比较麻烦,所以说我我把这个思路再重新捋一捋,我这样写呢,这个思路是没有问题的,但是实现起来呢。啊,不是特别的好,所以说我把这个思路换一下,我把这个上面第五步这个思路呢,换成这样子,大家看看能不能理解啊,我们这样子,这样子来走第五步我们这样走。
12:00
怎么走呢?我们先判断,我们先判断,就是说你这个target是就是先判断什么呢?Target。判断。判断target。Target。No,就这样写吧,这样写。呃,如果,如果target的。Target load有什么呢?有左子节点,哎,这样子是不是就思路清晰清晰清晰一些左止节点,假如说我们target的loadde有左子节点。那么这个时候呢,我们再去区分这个target是parent的左侧节点还是右侧节点,然后再进行进行这个处理好再往下写,那再继续判断,如果注意听啊,如果target。Node是parent的,Parent的什么呢?他的主子界定。
13:00
左子。节点。也就是说target target node由卓子激他,如果target由卓子激励,并且呢,Target node是parent的卓子激励,那么这句话就应该怎么写,是不是应该写的parent的left等于什么target?target.left。是不是这样子的,那还有一种可能性,还有一种可能性,那如果说target是parent的优质节点呢。这是有可能的。是的,右子节点。OK,柚子节点注意听啊,我先把思路分析清楚,如果是柚子节点呢,我们应该是parent。Parent,注意parent.right等于target。The no,点什么呀,Left。大家看这样你不理解,因为你target是parent右节点,所以说parent right,但同时你target有,Target是有左子节点,所以这样练起来就可以了,好,同样的道理,各位同学同样的道理,如果说target它有右子节点,因为你现在有一个节点不知道是左和右,你肯定要去判断嘛,是吧,如果他有右子节点。
14:20
那么这里面又有两个情况,哪两个情况?哎,跟刚才一样的,跟刚才一样,如果target node是parent的着子节点。它如果是它的着子节点,那么我们应该怎么写成什么呢?就应该写成parent left。对不对,也是你你是人家的左子节点嘛,那我就先写,那下面呢,应该是target no点什么right,那这个看看能否理解,反过来还有一种可能性。还有一种可能性。如果target。对,如果target是的优质节点。
15:02
六指节点,那么这个时候呢,我们就应该写成点right等于target。他给的no的right。好,这个同学看看能否理解。对,首先我们判断它是由右还是左,然后再判断target loadde是parent左还是右就完事。OK,好,这就是这么一个思路,这是我们删除只有一颗指数的节点的情况,那么还有一种情况呢?大家再来看这个情况呢,要稍微看起来麻烦,但实际处理起来并不麻烦。还有一种情况就是我们所说的第三种,如果我们删除有两颗指数的这种节点。对不对,好,就是情况三了。情况三。情况三是这么一个情况,好,为了好看呢,我把这个图给大家再往下面挪一下比较,比如说现在呢,我要删除的是哪一个呢?我要删除的是十号几点,假如啊同学们。
16:08
那这个时候它的负节点应该是七。假如现在我们以分析以以以删除十号节点进行分析,大家能理解吧,好,在这种情况下,大家想你会怎么处理呢?你的思路应该是怎的呢?好,大家看我的思路是这样子的啊,注意,因为后边我们这个思路清晰了,我们才能写代码,不然你听我讲课。你也不知道老师在说什么?前面的一套思路仍然一样,就说你还是先去找到要删除的这个节点和要删除这个节点的负节点,这个没有,没有问题,有,现在情况已经变成这样子了,也就是说绿色的箭头指向我们要删除的节点,而七这个红色的箭头指向我们。要删除节点的负极点,应该怎么删呢?各位朋友,其实特别简单,你应该这样删是干什么呢?因为你现在这个十下面有两颗指数,所以说你应该怎么办呢,从。
17:07
注意听从target。Target node。的柚子树。右指数找到,找到最小的这个节点。最小的,那你找你找最最小的节点,你找一找是不是它往左指数一边找,最后找到九了。是不是找到这个九以后,同学们,你们知道他要做什么事情吗?好,第下一步用用一个临时变量,用一个临时注意听临时变量。变量将将这个最小值最小节点的值保存。保存。比如说你保存到一个temp,打个比方啊,我这里不一定,到时写代码temp找到了,保存下面第五步删除注听。
18:06
删除谁呢?下面我们下一步就是要。删除。啊,我们要删除这一个,原目标节点还在这,目标节点还在这啊,比如说你找到最小的。假如说你找到最小的,用另外一个,用另外一个索引找到的假设是一个蓝色的。所以说这个呢,其实你找的是12,这个相当于说这个temp呢,就是12。是这样是吧,删除这个最小值相当于刚才删除的,应该是把12删掉。删掉,那删掉过后呢,再怎么办呢?把这个12再重新付给他,给这个value,那也就是说这个十变成了多少呢。变成了12。诶,你看这样才是对的,对不对,诶这样才是对的,刚才老师分析的有一点小问题,大家。理解一下。好,我放到这,那也就是说你如果删除这样数呢,它最终变成了这样一棵差排序树,但是大家有没有发现它仍然是满足二叉排序数的,因为它仍然是最大的。
19:10
最大的,所以这样子呢,就把我们这一颗具有两颗指数的节点。是不是,那有些有些同学可能想说,老师,假如我们这个柚子树下面还有呢,没有问题,其实也是一样的,大家看我再给他分析一把,假如我们下面还有。他又比12。比十大的比十十二小的,那只能是11了。对不对,假如这里面还有个11,我我我举个例子啊。假如这边还有C,是不是我们就从这个柚子树。柚子树。往右指数一直找,找到最小的,那这个时候这个右子数找到就应该是谁呢?就应该找的是11,能理解我的意思吧。你这个时候就应该从这边找一个最小的就是11嘛,因为你刚才12只有一个节点,那没没得说,那如果是这样找的话,相当于这方保存的是11。
20:05
然后这边这个十就变成11,能理解吧,变成11过后呢,再怎么办呢?好。变成11过后,我们再把这个节点删掉,那那这样子就会变成相当于相当于类似于把这个最小的这个移移到上面去了,同时把这个干掉,你看它仍然是一颗。二叉排序数,因为11呢还是比12小。是不是这个道理,这个这个思路大家理解了吧。也就是说你一定要从左右指数找一个最小的节点,然后呢,把这个最小的节点的值啊。给给到这个target node,然后把这个最小找到最小这点删掉就可以了,那有些同学说,老师假如我要从镯子数找呢,如果你从镯子数找的话,同学们,那你就应该找到左指数的最大的这个节点。然后呢,也是把最大这个节点的值呢,保存起来。付给这个target,然后再把这个最大的值干掉就可以了。
21:03
思路就这样子,大家看听懂了没有?听懂没有好,那么这就是我们的一个思路,那现在呢,我已经把第一种。第二种第三种思路给大家分析清楚了,下边呢,我们就准备代码给大家实现一把,OK,关于思路分析就到这里。
我来说两句