00:00
各位同学,我们走一下代码,首先呢,我们还是把这个删除的。方法我们先写在这个位置,好吧,写到这来,我们要递归删除节点。好,那么地位删除这个节点呢,我们这里是有一个规定的是吧,按照。这边给出的题,我们来给大家来看一下这个规定。他的规定呢,有这么两点。啊,如果是叶子节点就删除该节点,如果是非叶子节点就删除该指数,好,下面呢,我们就开始写代码了,Public public void什么呢?Delete。删除节点,当然你这个时候要传一个编号过来,你要删除哪个节点?是不是这样子的,好,嗯,我们刚才也做了这个说明,我们也做了说明,就是说。嗯,这个这个地方的处理工作啊,同学们,这个处理的工作,我们再把这个。
01:06
逻辑放在哪里呢?把这首先处理的这个逻辑,我们会放在这个位置。我把这个放到哪里呢?放在我们的binary tree这个方法里边去,我们hero node呢,我们就认为已经进入到了。这个12345步,明白我的意思吧,就说他是个空数,还是说这个root节点就是被删除的,我们把这一段的逻辑呢,直接写在battery tree里面的这一个delete load方法,而这这个hero load里面delete。No的,嗯,方法呢,我们就认为它已经进入到一个递归的过程了,明白我在说什么吧,应该很好理解,对不对?同学们并不是很难,好,那现在呢,我们就开始在这儿完成这样几个任务。好,我把这几个思路呢,先给各位同学整理到这里来,这是我们的思路。
02:01
好思路呢,刚才我们已经整理好了,大概就是这么。这么几个地方需要同学们注意的是不是?好,把代码稍微的给各位朋友整理一下,现在我们开始走代码了,理解啊理解,嗯,首先呢,我们先判断它的桌子节点,呃,它的着着值节点是不是,呃要删除的this.left。点点no是不是等于要删除的no?好,如果是的话,同学们这个条件满足,是不是我直接让left自空,就相当于把它删除了,并且返回。但是我这样写呢,会有风险,大家知道会有什么风险吗?你这样写是不是没有判断当前节点的左止节点是不是为空了,因为这我们说了,只有不为空的情况下,我们才进行这样一个操作,是不是你把它吃空并且返回了吗?在这个地方return就体会出这样一句话,能理解。
03:01
那所以说你在这呢,为了这个稳定,或者是呃,代码的严谨,你一定不是严谨啊,就必须写在不等于空的情况下。并且满足这个条件才做这个工作。这就是我们所说的。这句话。是不是同学们也就是说这下上这句话就是体现出刚才我们的这个逻辑。那。这个如果左指节点不为空,这样做,那是不是应该判断右子节点呢?是把这句话也要体现出来啊。这句话怎么体现呢?一样的道理,如果this.right它不等于空。就是它的右子节点,它不等于空的情况下,并且我们满足z.right它的no等于要删除的。是不是,那这个时候把右子数之空就可以了。
04:01
同时return。是不是这样的,那如果这两个都没有,都没有走到下面,我们应该走什么了?是不是应该,如果二三步都没删除,我们就需要向左指数进行递归删除,是不是相当于我们下一个动作了,但是你像左指数进行递归删除的时候,你应该也要做一个判断是吧,为了稳定。This left不等于空的情况下,我才向左子数递归的进行删除,那递归删除呢?this.left.delete no no就完事。是不是?好,那如果你这一步也没有完成,是不是相当于进入到我们这个柚子树了?是不是应该向右指数进行递归删除?右指数递归删除我们应该怎么玩呢?各位同学,应该是if this.right。不等于空,对不对,走,然后怎么样,我们继续往这走一半就是Z是。
05:08
点。Right。点定力。Node。是不是向右进行这个。操作啊,这个是向左嘛,这边就是向右嘛,一个向左一个向右,这样进行一个操作就可以了。好,那这样代码就写完,那写完以后呢,我们来看。好,我们来看一下。呃。各注意啊,同学们注意。你这个地方还不能够,嗯,这个地方return先不要写啊,为什么不要写呢?呃,因为这里面有一个问题,就说你往左边进递归的时候,其实有可能并没有删掉。是这意思吧,所以你return的话,那它这个右指数就有可能没有去进行操作,所以这个呢,先不要去写它。
06:01
啊,就是说他做指数啊,如果是成功了,那就成功了,如果没有成功的话呢,继续想右边操作就可以了,因为你要防止左子数是没有递归删除成功的,是这意思吧。好OK,这边大家要注意一下,好,下面呢,我们把这个写完了,过后我们就来开始写这最前面的。这段代码的处理好,那现在呢?我们找到哪里同学们?我们找到。我们的二叉树。Binary tree。在这里我们写一个方法。在这个位置哈,现在已经进入到BY了,我们现在来写删除这个节点。好,这个节点的规则还是跟刚才是一样的,我就不多说了,Public void什么呢?Delete node,同样你传一个no。是不是要传一个编号给我呀,那你给我传一个编号的话,我应该怎么做呢?首先我判断root是不是。
07:06
不等于空,因为如果root等不等于空,我们才去操作,否则是不是你可以直接提示一句话了,说什么呢?这是一个空诉,无法删除。是不是这样子的啊,说空诉不能删除。有没有这种可能呢?当然是有可能的,那如果root不等于空,我们现在首先判断应该走哪个逻辑了,同学们是不是,如果这个只有一个root,那么我们要判断它是不是这个root是不是就是我们要删除的,因为root上面它已经没有负节点了,你必须立即判断。这里马上要判断,不然不然后面就不行啊,这里需要立即判断,判断root是不是是不是就是要删除的节点,否则后面就没有机会了。那现在我上来过呢,衣服如果root点什么呀?
08:00
Get它的它的no没有啊,Get他的no。对不对,如果它等于什么呢?等于你要删除的这个no好的。那说明这个root就是要删除的,很幸运,那这个时候呢,不用犹豫,直接将root整个这个制空,因为如果你删除的root的话,相当于把整个数失空了,否则怎么办?就是你这个root不是要删除的,那就开始进行我们递归删除。递归删除就可以了,那这个时候怎么调呢?root.delete no,好,咱们就写完了。看看这个逻辑能不能思考起来。能不能思考起来?好,同学们,我们来玩一把吧,那我们来玩一把,现在呢,我们来进行一个测试。好,我们测试一把删除节点。的代码。啊,同学们可以看到现在呢,我们,呃,我们这样子啊。呃,我把前面这些都先暂时的程序便利,我们都先暂时的注销一把,好吧,因为待会呢,我想做测试,我需要把现在这些代码先暂时的注销。
09:11
对,我先注销。好,现在呢,我先写一个删除前是个什么情况,再写删除后是什么情况来,呃,我们先打一句话。好。删除前。删除前我们这个前序便利吧,来一个。情绪便利。那程序便利的情况呢?我们就用better tree。点P。Order没问题吧,我们删除一个。Not by。点delete,我们删除五号节点。因为他这里面给我们的测试是先是测试五号,再测试三号指数,好玩一把。那这边我再提示一句话叫什么呢?叫做删除后,删除后这个仍然是情绪便利。
10:02
情绪便利呢,我们还用tree。点什么呀?Pre order看清楚没有?是不是也说先是情绪便利吧?然后呢?删除,删除过后再提示一句,删除后先去便利,那我们这个信息应该是什么样的,我们先不要去执行,我们先判前序便利。在没有删除之前,前序遍历的结果应该是12354,这个是肯定的。是不是这样子的,12354。那么等到我们删除了一个五号以后,这个结果呢,就应该是这样子的,相当于五号节点没有了,还保持前序,便利应该是什么呢?一。二。是不是先贬低自己一二?三四是不是1234好,我先把它撤回去啊,那就是现在变成了123412。
11:00
三四好朋友们,我们运习吧。我们运行吧,我们发现呢。诶,大家看。我们前序便利它是12354,但是我们删除以后,前序便利呢,变成了这个,那对我这不好意思啊,这两个怎么嗨,老老容易搞错啊,谦虚便利都是以P打头的,有时候不小心就嗯写错了,来再跑一下。好,1234正确的。正确的,好,我们再来测试一个,删除了。这个指数的这个问题,Better。那么这次呢,我们是指医生,是三号决定。同学们,如果我们删除的三号这个节点,它等价于把这颗指数整体干掉,那显然就是一二了,明白这意思吧,也就是说如果删除之后,那么这边删除的应该是一和二,后面三和四也没有了,执行一把。好,果然是这样子,那现在呢,我们来做一个相对深入一点的探讨,我们来debug一下,到底他这个程序,就是我们这个删除的流程是什么样子的,来我们下个节点。
12:10
啊,下一个断点,我们来看看他到底怎么走的,好不好,我来玩一把。好,同学们,我们第八个。我们debug走起来。好走起来,那首先呢,同学们可以看到它进到删除这个D漏的时候,他先进入到这个代码里面去找一把。诶,这个啊,这个地方我我走错了啊,重新来。呃,重新来,咱们重新来一把。来,我们继续第bug,因为我要追进去才能看到它的一个流程,是不是同学们。好,现在我进到这个代码里面去,进到这儿,首先我们看root呢,显然它是不等于空的,为什么呢,现在root其实是指向。宋江的注意,听啊,我们我们追一把,大家一下就明白了,他现在只用出root root不是root root因为不等于空,他马上判断root是不是要删除的,往下走一把。
13:05
Route get n number等于一,你删除的是五号显示,这个不成立。不成立,那么我就直接进入到else语句,看下一句。进入到L4,那我进到这个第一声豆子我追进去啊同学们。追到这里面来了,是不是这时他去判断我们这个this,这个this,其实现在是哪个节点,是root节点。宋江这个节点,那么呃,显然他左边,他的左边呢,其实现在是哪一个呢?同学们是吴用。他现在看无用是不要删除的,显然无用不是,所以说,所以说这样我们再下一步呢,它会进入到哪里呢?这个地方会因为不满足嘛,因为现在this.ne的this.ne的实际上是无用,看啊无用,显然无用的编号是二,它也不等于五,因此这个一不不成立,它就直接判断右面。是不是?也就是说。
14:00
我们按照我们刚才这个逻辑呢,他先。他先到这边去看吴用是不是无用,不是就判断右边的。啊,刚才我和分析有点小问题是吧,看那个执行流程有点小问题,就是说其实他是先判断右,因为我的代码是先判断右再判断左。是吧,先判断右再呃,先判断左,再判断右,好,现在呢,我们接着进行下一步动作的操作。好到右右面呢,现在是卢俊义,卢俊义是编号为三,所以说这个也不成立。于是乎他就。跳过去,跳过去,这个时候呢,判断this left是不是等于空,This left是谁呢?This left其实现在就是无用,也就是说他先把这个判断了,不是,这个也不是,然后呢,他又。接着。以无用为这个节点继续。按照刚才的一个流程走,显然无用。他现在现在进到这里面去,大家看进去了啊,肯定进到这,进到这里面呢,它要进行递归。
15:07
它要进行递归,好,我们先进到这个地delete,大家看我追进去了,是不是又到这来了。那么又到这儿来,过后呢?很遗憾,这时你现在认识这个节点是无用,而无用左边呢,是空。好,所以说他马上跳过这个。好,往下走,吴用的右边也是空,所以他又跳过。不用,他又跳过,他又跳过。就是他不,他不等于他现在rise等于空去跳过,接着往下走,跳到这里来过,怎么呢?他这个时候他想尝试着向无用的。左边再去进行这个递归。但是很遗憾,无用的,左边是个遗憾,呃,是个是个这个空是一个空,它就不进去了,不进去,所以说往下走不进去,右边呢,也是等于空的也不进去,好我们接着往下执行。
16:04
回来了。回来我们再继续往下走,同学们看是不是当时是判断无用。左边现在你看一回来过后。现在回到上一集的话。也就是说现在刚才是走的吴用这条线,左右两边都都走空了,现在回头走又回到宋江这个点了,因为他下面那个探索完了又回到宋江,也就是说现在呢,他又尝试着向宋江的右边去进行这个地位,现在现在看Z是谁,Z是宋江,Right是谁,是卢俊义。所以说这个时候呢,他会。的,它会往往下面追啊,往下走进进到这里面去,好往下走。走一个。好进到这,那么this.right呢,Delete,他想去这里面去,所以说我们追进去,追进去过后他去判断卢俊义的,看啊,关键点已经来了,他现在是到卢俊义的这个点。
17:05
卢俊义,哪点呢,关胜。也就是说,此时此刻,他已经注意到了this是如俊率它的左边,其时关升,这个时候条件已经满足了,因为z.left不等于空,同时z.left的no呢?这个值刚好就等于五号,所以说再往下面走,走一步,它会进入到这个语句。进入到这个鱼,所以说我们进去看进来了,这时他就会把哪个滞空呢,把我们z.left也就是说把卢俊义的左边滞空,这条线就会被断掉。这条线就会被断掉,是这样子吧,好,断掉,我们来看看,是这样子走就了。就了,好回去。执行完毕。那么这个时候在在return return过后呢,就我们继续往下走。他就饿死了。空数不能删除对吧,这个因为上面这个if已经走完了,再往下面走,这个代码就回到哪里呢?回到主方法了,再往下走回到我们主方法,看这是这个地方是主方法了,接着往下去玩就可以了。
18:12
看清楚没有,好同学们这个呢,就是刚才我们分析的这一个。执行的流程大家看懂了没有?刚才我说的,嗯,这个。代码思路是没问题的,只是我在说这个删除的时候呢,应该是这样子啊,先以先判断。这个根节点是不是要删除的,如果不是就先判断它左边。是不是要三个左边这个子节点不是就判断右边,如果右边也不是呢,它就像左边这个。这棵树的左边进行。这个递归的操作好,把这边全部做完了过后,又回到它的右边,在右边呢,又进行这样的一个递归操作,明白我的意思吧,也就说刚才刚才我们这个思路应该是这样去理解,就是找到一个节点,左边判断不是在判右边,如果两个都不是呢。
19:04
就照左左边这个节点的左指数进行这个递归的操作,是这样子的,好同学们,呃,如果还没有听明白的同学,没有关系,没有关系,你呢,按照刚才老师这个思路,把这个递归再去玩一把,应该很好理解,应该很好理解,对不对?好,那关于我们这个删除节点这个内容呢,就先给同学们讲到这,我把内容给大板述一下。那刚才我们讲的是什么呢?各位朋友来捋一捋。捋这个思路。刚才我们给大家讲的是二叉数的删除节点的一个内容的介绍和讲解。那么怎么讲的呢?首先我们提出了一个要求。好,我们提出了一个要求,什么要求,诶这怎么哦。我们提出了一个要求。这个要求是这样子的。是不是?
20:00
这样的我们要删除这个节点,叶子节点怎么办?非叶子节点怎么办,然后要求测试。好,这是我们的一个要求,那么当这个要求提出来以后呢,我首先给他做了一个思路分析。是不是先做思路分析的来写到这,这是我们的思完成完成删除的思路分析,那具体来说这个思路分析呢,就是用这个文字给大家描述了一把。是这样子的吧。哦,是这样子的,就是首先处理什么,然后再处理什么,这是我的一个思路。好,思路讲完了过后呢,我们紧接着给同学们讲了一下这个代码的具体实现,对不对,代码实现。对,那代码实现呢,其实就是还是在原先battery tree DEMO里面写的是不是,那嗯怎么办呢,要不。呃,因为这里面代码又越来越多了,要不我把关键的代码给它粘过来就可以了,好吧。
21:03
关键的代码粘过来,因为最后源代码也是给大家的,我找一下,我们首先在hero load里面我们加了一段逻辑代码,是在哪里呢?在。这个位置。是不是这段代码,我把这段代码给大拿过来啊,同学们,因为太多了,如果我全部粘过来呢,有点不利于大家阅读,其实就是这段代码并不多。是不是同学们好,首先我写一下,我们在hero no的点class加这个这个类里面,这个类里面增加了,增加了一个方法。具体来说就是这个方法。是不是就是这个方法,而且下面写了注释了,把这个方法写完了以后呢,我们紧接着又在哪里呢?对,在这个binary。Binary tree,点这个这个类,我们增加了一个方法,是这样子的增加方法。
22:01
哪一个方法呢?同学们,我们仍然在这来找。是不是这个方法need no的这个方法。其实也很简洁,是不是并不难?紧接着呢,我们在做测试的时候在哪里呢?在我们这一个binary。啊,Tree DEMO DEMO这个类里面我们增加了,增加了测试代码。是不是测试代码呀。诶测试代码,那这个测试代码在哪里呢?各位朋友其实就是。主方法里面的这一段代码具体来说。就是这样一段代码给大家完成了一个测试,而且呢,我们通过分析的确。效果跟我们想象的是一样的,是不是好把代码转过来?好,各位同学,那关于删除节点的代码说到这,那最后呢,我这里留一个作业题,大家思考一下。这个作业题呢,并不难。并不难,它是说如果要删除的节点是一个非叶子节点,现在我们不希望将该非叶子节点作为根节点的指数删掉,什么意思呢?说它如果是一个非叶子节点。
23:10
我们需要。比如说这个非页,这个山就是一个非叶子节点,你我在上山删这个删的时候呢,我并不需,我并不要求把这个删删掉,我是怎么要求呢?我是这样要求的啊,如果该非叶子节点A,假设这个是A。干什么呢?如果这个A下面只有一个子节点B,那么就用B替代这个A,明白我在说什么吧。就是假如这个卢卢俊义下面呢,呃,我删的是卢俊义。但是卢俊下面只有一个林冲,没有这个关胜,那就相当于说让林冲替代这个位置,把它往上挪一下就行了,大家想这个怎么完成?其实挺简单的,你做一个判断。看它是不是只有一个子节点,然后把它拎上去,如果该叶子节点A由左直节点B和右子节点C,那么则,则让左子节点B代替A,那就是像现在这个情况,什么情况呢?我再给大家说一下,比如现在我删除这个节点是A,它下面有两个节点,一个是B直节点,一个是C直节点。
24:19
我现在要求什么样呢?就是当我删除的。当我删除这个A的时候。这个A是我要删除的,但是它下面有两个节点,怎么办呢?我要求让这个B节点来替代这个位置。也就是说相当于把这个节点拿掉,把这个五拎到上边去,就这种代码。好,同学们想想这个能不能做完,请大家思考如何完成该功能,我刚才已经把这个提示给大家说了,那有些同学说老师我完成布料怎么办?不着急啊,后边如果你实在完成不了,后面我有我们再讲什么了,我们再讲解。讲解这个二叉,二叉排序数式。
25:03
排序数式还要讲解,还在再给大家给各位给大家讲解。这个具体的删除方法,具体的删除方法,因为这个呢相对比较简单,为什么呢?因为你你这个二叉数他也没有要求是保持一个什么顺序,所以说你你把左子节点提上去,或者把右子节点都无所谓,但是如果我们这个是个二叉排序数,那个难度就大了,所以说我们直接在这个二叉排序数里面去讲如何处理这种非叶子节点的删除。的这个这个任务明白啊,但是呢,大家有兴趣可以把这个工作做一做好的,我我把这个要求呢,给各位朋友板书到这里,那希望同学们在课后把这块先完成了好不好,也不是很难了,也不是很难好,这是刚才给各位同学。说的这么几个步骤。
26:00
那么这里呢,呃,我我把这个图也给他截过来,就是按照这个图的示意来玩。好,同学们。关于二叉树的删除节点,就给大家介绍到这里。大家好好的消化和。嗯,理解一下。
我来说两句