00:00
各位同学,我们来看一下二叉树的下一个操作,删除节点。那么二叉树的删除节点呢?我们这里先有这么一个要求,第一个要求如果删除的节节点是叶子节点,什么是叶子?叶子节点呢?就是没有子节点的节点就是叶子节点。比如说。二号五号四号就是叶子节点,那么如果删除叶子节点的话呢,我们就直接把这个节点干掉就可以了。那如果我们删除的是非叶子节点,比如说三号,那么我们这先规定,如果是删除非叶子节点,我们就删除该指数,比如说我们要把三号。这个节点干掉,其实呢,我们这里要求直接把这个指数删掉就可以了。那有些同学老师,那为什么你要这样去规定呢?是这样子的啊同学们。嗯,我们先来简单的,我们先给大家讲简单,因为如果我真的把我我比如说删除的非叶子节点。
01:06
是三号,那你把这个三号删掉的话,显然这个地方你还要考虑需不需要把下面的左指数或者是右指,呃,左指数或者是右指数往上提的问题是不是。嗯,在你这个数还没二叉树还没有什么规则的时候,其实呢,这个意义不并不是很大,你把左把这个带删除的这个节点的左边还是右边删除,呃,是把它的左边左指数提上去,还是把它右指右指数提上去,这个呢,实际上都可以,因为你你这个二杀术没有规则,所以说呢,待会我们在后边讲到。二叉排序数的时候,我们还会去讲,如果我们删除的这个节点,它不是一个,它是非yes节点,我们怎么删除,好吧,所以这里呢,我们先规定两个叶节点就删掉叶子节点,如果是非叶子节点就删掉这个数,相对来说呢,我们会比较轻松一点,后边我们再深入的。
02:08
跟大家讲解好吧,深入的讲解,呃。怎么去把左他的左子节点或者是右右子节点把它提上去的问题,好,那现在呢,这个规则我们已定好了,我现在呢,来给大家分析一下,我们应该怎么去删除,好吧,先把这个代码给大家玩一玩,呃,还是以这还是以。这个二叉树为例来进行我们的思路分析,来吧,同学们。把它放到这里来。那现在呢,老师跟大家做一个分析。跟他做一个分析,我们来聊聊删除节点的问题。好,现在呢,我们是呃,完成完成删除节点的这个操作。首先我们这里有一个规定,因为你的这个规定会决定,决定你的代码会怎么去写,是不是我的规定呢?先给同学们拿出来,就是刚才给大家说好的。
03:13
做个规定。啊,这个规定是我们事先定好的,规定是这样子的。好,在这种规定之规定下呢,我们再来谈我们的一个操作的步骤。好。我们来说一下这个思路,好吧,思路第一步。第一步我先做一些说说明,因为我们现在这棵这棵二叉树呢,是单向的,大家有没有发现,就是你这个节点往下走,也也就是说我们这个节点呢,并不能找到它的前驱节点。我们一号找到它的后左左边节点,或者是右边节点,但是你有没有发现三号卢俊义并不能找到它前面这个节点。是这样子的吧,所以说这点你一定要分析出来什么意思呢,因为因为注意听啊,因为我们的。
04:06
二叉树。二叉数是单向的,单向的因,所以。所以我说一下,所以所所以。所以怎么样呢,我们是判断判断什么呀,当前节点的什么呢?子节点,它的子子节点。子节点是否需要删除?需要删除就是我们这个当前的子节点是否是待删除的节点,或者是是否需要删除的节点。是这个意思,嗯,而不能,而不能干什么呢?而不能去判断。去判断当前节点,当前这个节点。节点是不是需要删除的节点,大家理解我在说什么?比如说我们要删除的是五号或者是三号,无所谓,就比如说我们删除的是五号,你如果真的把这个指针指向了五,其实你你会发现你没有机会干掉这个五号,为什么呢?因为你你你没有办法找到它的负节点呢。
05:23
所以说同学们应该这样去考虑,我们在找的时候,其实是找,是在判断你当前节这个节点的左边或者是右边是不是需要删除的节点。这样你才能把你的左左支节点或者是右子节点干掉。是不是这个道理,所以说我们写第二句话。第二句话就是什么意思呢?就是我们应该是这样来玩的啊,就是。我们这样子,我们这样子先判断当。判断什么呢?如果这样写,如果当前节点,当前节点的什么呢?左指数不为空。
06:07
不为空,这边一定要认真听啊,不为空,并且。并且。着着子节点。着子节点。桌子节点。对吧,他的左。这个地方做子节点。这个又是这个字。左。做止。止节点这个节点啊,并且左子节点,那这地方我们也是判断的当前节点的左子节点啊,左止。左子节点又是个节点看。讨厌的很作。指节点,就是当前节点的左子节点不为空,并且左子节点的这个编号。
07:02
编号就是需要删除的,呃,并且着止节点就是要删除的节点。对不对?那么我们就干什么呢?就将就将this.ne之空就可以了。是这样子的吧,好,这这个地方要分析出来,第二点还要分析出来什么呢,如果我们。这个。是如果啊,如果是,那我就复制一份。复制一份,注意听,如果当前节当前节点的右子节点。又当然你你这个一旦满足了这个条件,一旦满足就返回了,这里还要说句话啊,如果这个。就说如如果第三步这个已经已经返回自控了,并且一定要注意,就就结束这个递归了,并且就返回,也就是说结束什么呢?结束。
08:00
就结束我们这个删除任务。我我我们删除应该是递归的吗?可以认为是叫结束递归了,就不要再去看它的右右子节点是不是为空,并且去删除了,明白吧,不然的话,你你你找到了你再删你就。很郁闷的,因为我们这这个编号是唯一的嘛,所以说这方就马上就结束递归删除,那么我们再看,假设你左侧节点你没有找到,你就去当前节点的右子节点去找,如果右子节点不为空,并且右子节点。注定啊,右。右子节点就是要删除的节点,那么就将右边指控。This right指控,并且跟前面一样,并且返回。也就是说相当于说你在右稚节点就是要删除的,那你就把它520返回了,那么第四一步呢,要注意,如果你第二步第三步都没有完成,你就需要递归。进行这个删除对不对,如果第什么呢?如果我们这个第二步和第三步。
09:06
第三部。注意听第三步。对,都没有第三部。没有没有删除这个节点。那么那么那么怎么办呢?那么我们我们就需要需要分向什么呢?向右左指数,但你这个顺序看你决定啊,假如说我们是向右向左这边去找向左指数,左指数进行递归删除。OK,如果,呃,当然你你这边也要判断左指数是不是为空。阅读之如果为空,你你也没办法删除了,对不对,那么第五步。如果你这个向左指数删除也没有删除成功,那你就得向右指数继续删除。能理解意思吧,啊,如果这样子还要干什么呢,如果。
10:02
啊。呃,如果左指数没有成功,但你这肯定有个语句嘛,对不对,好如果这个,呃第四步,第四步也没有删除。也。没有删除这个节点,则应当应当干什么呢?向右指数继续删除。向右指数进行递归删除。递归删除是这样子的吧,好,就是需要同学们注意的地方,那么我再说一遍,比如说打个比方,我们先到一号去找我们删除的五号不是吧,先看这个当前这个,先看这个一号的左边是不是要删除的不是。不是的话呢,我们,呃,我们怎么办呢,各位同学,这个时候我们就去看一看。看一看他的镯子。就是它的左子节点是不是空,左子节点它不为空的话,我们继续往左边去找。
11:04
那么直到到到最底层,然后从右边去找。好,如果整个这个镯子数都没找到,那么就向右边去找。对不对,向右边去呢,就右边去的时候呢,也是一样的道理也是。呃,如果是我们就删除,如果不是,我们就继续往右边去找,先左后右,先左后右这样子递归,那么这边还要考虑一个情况,考虑什么情况呢?就是考虑还需要考虑,呃,如果这个数。是空诉。什么是空呢?就是root本身。Root本身等于空的情况下,你是没有办法删除的是吧,还有还有考虑,如果还有一个情况啊,如果root只有。只有一个root节点。如果只有一个root节点。那么其实就是相当于把整个数字空,因为你root节点只相当于只有一个root节点,其实就相当于把这个数字空,则等价于,则等价将二叉树。
12:07
二叉树之空。能理解我的意思吧,自空。好,代码呢,看起来好像123456,比较复杂,其实代码本身并不多。本身并不多,那不管这个思思路,我还是给大家分析了一遍。也就是说,你一定要明白是一,一定要明白节点,首先明白我们一定是判断当前节点,节点的子节点是否要删除,你不能跑去哦,傻乎乎的,你判断这个节点是不是要删除,那你没有机会删除掉了。一定是删除,判断当前节点的子节点是否要删除,当然这个子节点可能是它的左边,也可能是他右边。是不是,所以说你看我上来过后判断当前节点的左左子节点是不要删除的,那这就相当于说我们这个root节点,其实我们并没有判断。因此你一定要考虑上来过,先把root节点判断一把,如果root节点不是你,才能继续进行我们这个12345的这种递归操作,能理解吧?
13:10
这个听起来有点绕,是不是代码呢?其实并不难。但是你一定要有这个思路,也就是说上来我们先看你是不是个空诉。然后如果不是控诉,我们看看是不是root root节点只有一个,并且是不是要删除的。好,如果这个不是好,我就开始的时候12345这样递过来做,那干什么呢?因为这个节点我入的节点,我刚开始在第上来过后,我先判断了一把。也就是说第六步其实我是要最先做的,或者这样子啊,或者我把这个第六步先给同学们写到最前面去,大家应该就。比较清晰了,首先先先先处理,首先先处理这个情况。首先先处理它是不是一个空数和删除的节点是不是。是不是,呃,就是root节点,然后呢,下面这个步骤就是,然后再进行下面这个操作。
14:05
然后进行下面的这个步骤操作,那就是干什干什么呢?先看这个root节点的左边是不是要删除的。好,如果是,那么我们就干这个,如果这个不是怎么办呢?我就看,我就判断,我就让这个,我就让这个递归,继续在以这个无用为。为这个嗯,负节点继续往它的左边去走。明白我的意思吧,那那当然,那当然不停的往下走的时候呢,肯定我如果左边一直没走到,那就还要往右边去找,总而言之,最后整条线板右边全部变定完了过后才到这,但是一定要记住啊,它这个向右的时候,其实实际上已经到了我们这个递归的最下面,是不是然后再一层一层往上走的。这点大家要理解。这点大家理解,待会儿呢,我们可以通过通过这个,呃,通过这个debug,你可以看到它它的这个这个流程。
15:03
啊,它是怎么判断的啊,待会我们看,我们通过debug看到,诶,它到底是先判断的,二二判断完了过后干什么呢?二判断完了过后再去判断,它先判断一这个是不是好,这个不是就判断。它下面这个二是不是,但实际上它先判断的并不是二,而是判断二的下面,因为你这个二在我,呃,在我直接刚指向这个一的节点的时候,我已经判断它,不,它不是要删除的,于是我就把这个往下挪一下,再判断二这个节点的左边。一直把这个左边全部走走完好走完走完,因为这个地方没有嘛,所以说相当于走完,然后回到这边呢,过后呢,我再判断,如今液。卢俊义,你判断这个一,这个节点的右边是不是好,右边不是的话,又以这个节点开始判断它的下一个节点关胜是不是。好,如果关胜不是,那么继续让这个关胜往下走,但是关胜呢,下面没有怎么办呢?又回到卢俊义,卢俊义右以右边。
16:04
开始走,明白我的意思吧,好,最后整个走,整个走完了,如果没有就相当于没有删除,说待会我们可以看一下到底他判了几次。好,实录大致呢,就先说到这儿,一会儿呢,我们用代码给各位朋友编写一把。
我来说两句