00:00
好,同学们,我们根据前面对这一个线索化二叉树的一个思路的分析,我们来实现中序线序线索二二叉树,注意啊,我下面讲的代码呢,是以中序的方式来线索二叉树的,那如果是前序和后续呢,会对这这一个代码做一些微小的调整。那么我们就以哪个为例呢?咱们就以这个案例为例来进行讲解,对吧?好,现在呢,首先我们打开这个eclipse,我们新建一个文件,我们新建一个文件来走一个,那这个文件呢,我们这样取个名字叫什么呢?Ready。ED什么呢?就是binary。Binary什么呀?DEMO把这个主方法勾上。好的,把这个去掉,大家认真听啊,这个线索二叉树,线索化二叉树呢,有一定的难度,理理解起来有理解起来有一定的难度啊,那首先呃,我们是不是还是按照以前的规则先要创建。
01:11
先要创建hero。Hero node呀,这个节点肯定要有的,也就是说我们首先还是要把这些个节点创建起来,但这个节点呢,我们在前面讲二叉树的时候是其实我们是讲过的,对吧,如果讲过我们再去,呃,再去重新写一遍呢,就没有意义了。所以说呢,我就用。我就用什么呢,我就用前面讲这个二叉树的这个hair no来讲解就可以了,理解我的意思啊,那现在呢。就这样子,我把前面讲的这个hell no拿过来用用。这个节点在哪呢?我们找一下。我说一下。节点。是在这对不对,我把这个节点的方法全部都拿过来用一下。
02:00
呃,这样子啊,因为这里面这个节点,如果我拷贝过来的话呢,名字就重复了,对不对,那这样子同学们,我我在这稍微的在这个tree里面呢,我们再建一个包吧,这样把它分开一下,我就不用把这个类名重新改变了,好不好,这个我取个名字叫SHTHR什么呢,这个二叉树binary。好,这个包名有点长啊,但是没有关系。这样我省点事嘛,大家也听得轻松一点,我就把什么呢?我就把刚才这一个类,咱们拖拽到这个纸包里面去,这样讲好吧。好,OK。拖拽过去就行了,那拖拽过去过后呢,现在我在用原先这个hero node这个类的时候,我们就无需做,无需做太多的改变,名字也不用改了。因为你如果放在同一个包,还得重新改名。好,同学们,我把这个hell no的节点拿到我们这个地方来。
03:02
你看这就没有任何需要修改的,对吧,那刚才我们讲过,我们讲过什么呀,就是对于这个hair load呢。我们讲前面在讲这个分析的时候,注意听,我们知道当线索化二叉树过后呢,我们的这个节点的左右指针。它的指向就有可能是左指数,也有可能是前驱节点,也有可能是右指数,也有可能是后继节点,那你怎么样呢?你是不是应该设置属性来区分。我们这一个指针的它的性质或者它的类型的,这是肯定的,因此我们上来过后呢,先干什么,我们先来创,我们先来定义两个新的属性,Int,什么呢?Left type。对,再定义一个属性int right type,我说一下这个地方的规定说明吧,各位听,注意听啊,那说明什么呢?我们规定。
04:09
呃,说明这个规定规定什么呢?如果,如果这个left type它等于零。表示什么呢?表示它指向的是左指数。左指数这个能理解,如果为一呢?啊,如果type等于一,如果是一,则则表示什么呢?OK,则表示指向的是前前区节点表示指向。前驱节点。这个大的前提你要定下来,否则待会代码没法写,知道我意思吧,你没有规则就没法写吗?前区节点理解,那同样我们还要规定,如果我们的right type它等于零。表示什么呢?OK,表示指向。
05:02
是柚子树。右指数,而如果是一表示什么呢?表示指向后继节点。这些先要把它规定清楚。后继节点,好,那既然有了这两个方法,我们是不是应该给他把这个set和get方法给它放进去呀?好,这个地方我们加进去。这两个新的方法放进去就可以了,后面我们需要用到,好,这是对he load的一个节点的改造,那这个改造完了过后呢,下面我们就可以来写这一棵线索化二叉树了,那同样的道理,我呢也不想完全的重写,因为有些方法我们是可以用的,所以说呢,我们这个地方怎么样?还是拿原先这棵二叉树来进行修改就可以了,因为你要重写这个成本太高了,对不对,我们需要改进,因为线索线索化二叉树相当于就是在原先写的二叉树的基础上增加一个功能嘛,就是增加它可以进行线索化的功能。
06:12
他并没有跟原先这个二叉树完全的冲突,对不对,所以没有必要完全重写,好我把在这边写的二叉树的这个类给各位朋友放到这里来。放这来过后呢,我们把这个名字改一下,以示区别,那现在我们创建的是什么呢?这样一棵二叉树。Threadtad thread。Bay tree这个呢,就是相当于说我们创建是线索化,就实现了,实现了线索化。线索化功能的功能的这个二叉树明白。好,那现在你这样做了过后,他其实是没有进行线索化功能的,那怎么办呢?各位朋友,现在我们就写这个最核心的方法。
07:03
也就是说现在呢,我们需要把这个线索化的代码写出来,好现在直接上代码啊,就是呃,编写编写对二叉树,二叉树进行线索化的,我们写清楚叫中序线索化。线索化的这个方法第一解啊,那现在开始写public void,然后呢。ED,什么呢?我们的no,其实你所谓的线索化就是把这些节点进行线索化,你理解吧,好,那你肯定在线索化的时候呢,你要把这个节点给我。对不对?你要给我一个纪念,好同学们。首先上来过后二话不说,我们先判断,也就是说我现在干什么呢?这个就是传,传入一个节点,我对这个节点进行线索化,先说清楚啊,就是对什么呢。这个漏,这个漏就是当前需要线索化的节点明白。
08:08
这点大家要有个整体认识,那我们现在判断,如果说你当前节点为空,我们就没有办法线索化了,也就是说当我们进以这个线索化的结果,你找了一个空的这个节点,让我线索化,这是不可能的。比如说你上来过后你个root。这个节点就啥都没有,你让我先说话,这是不可能的,是不是?所以说我们先判断,如果nod nod等于no,那么就无法先说话就直接退出。就不能线索化,那不能线索化,我们就退出就完了,怎么写呢?如果no等于no,说明什么问题?为空,我就不线索化,直接返回就可以了,这个没问题吧,同学们。否则的话呢,我们就来开始按照中序线索化的方式来处理,注意啊,你是中序线索化,那么我们中序线索化的大的步骤应该分成这么三大步,第一步先处理,先应该是先线索化我们的左指数。
09:08
这个能理解吧,左指数为什么呢?因为你是中续变利吗?我们知道中续变利是先处理左指数,再处理当前激利点,再处理右指数,所以说我们先把大的这几个步骤先写清楚,这个是干什么呢?线索化当前这个节点理解好,这个处理完了过后,我们是不是应该第三大部分应该是在在什么在线所化什么呀,柚子树。但优指数你得判断好,就是三部曲。好,同学们,我们想一想啊,同学们,我们想一想。那么我们在进行这个线索化的时候。我们在信息线索化的时候,大家都知道我们有个前驱节点,也就是说打个比方。我们在进行线索化这个,呃,某个点的时候,我我这用一个线头啊。
10:06
因因为这边已经画好了,所以说我们假设这有一个箭头,这个箭头指向的假如指向的是我们当前的这个要准备线索化的这个节点。这个就是我们所说的node,那家知道,因为我在处理本节点的时候,其实我需要有个前驱节点。大家理解我的意思吗?因为你你你要让这个节点去处理,去线索化,你得有一个,你得有一个指针,或者有一个属性,它始终是跟这个当前节点构成一个。呃,构成一个前驱的关系,也就是说你假如我们这个绿色的是一个node。假如说我们这个绿,绿色的箭头指的是当前这个节点no,那么我们在整个处理的过程中,就应该还有一个一个指针指向前驱节点,比如说我们叫P。
11:07
大家能理解我的意思吗?因为你这样子做,你才能让这个node,才能让这个node有可能去指向这个前驱点,从而实现这个线索化。是不是,所以说我们在这里呢,我们应该再加一个属性才能处理,在哪里加呢?怎么在这加。我们在这讲,我们在这里加一个什么东西呢?同学们,在这个地方我们应该去加一个前驱,应该这样说啊,兄弟们,我们干什么呢?为了我说明啊,为了实现这个线索化,线索化需要需要创建一个一个这个指向。指向前区应该指向当前节点的,前驱节点的一个引用,是不是前驱节点的一个一个变量,或者是一个指针都都可以。
12:02
OK,那这样子的话呢,我们就应该定义一个这样的东西,是不是here no here node什么呢?就叫pre初始化呢,我们为no。因为你只有这个pre,你才有可能实现线索化。也就是说这个pre再说的再直接一点,就说该这个pre指向是什么呢?Pre总是保留前一个节点,就是说怎么说在在这个递归进行线索化时。线索化时这个pre总是保留,哎,总是保留什么呢?前一个节点能理解。因为我刚才已经给各位同学分析了,如果说你没有保留这个node的前一个前驱节点,那你没有办法,因为你这个是本身是单向的,你把它找到了,你怎么能找到他前面呢?你只能让node去跟这个play发生关系,才有可能实现这个线索化,对不对?所以说这个动作呢,这一个定义是不能少的。好回到这里面,我就开始可以开始走我们的代码了。
13:10
那刚才我们讲到,就是我们有了这样一个。这样一个思路过后呢,下面我们就开始写代码了,先处理主指数,这先线索化。呃,左指数非常的简单,就帅。Nose,谁就是我们这个nose点。Not get napped。是不是这样道理?那如果处理柚子树怎么办呢?也非常的简单,是不是thread nose?呃呃,Not not.get它的right是不是就完了?关键是中间怎么写。因为你处理好,你可以先手画左指数右指数,这写完了,关键是中间的代码比较麻烦。这个地方我先说下啊,有有有点难度的,有点难度。
14:03
有点难度,大家认真听,我尽量的呢,给大家讲清晰一点,那大家想一想,大家想一想,你在进行这个线索化的时候,你在进行线索化的时候,比如说。好,我我把这个往这边挪一下啊。把这个往这边挪一下。比如说你当前这个节点是node指向了八,因为我们第一个被线索化的这个节点,按理说就应该是八,你为你中序嘛,你中序不停的左走,应该是先变离到八了,你要处理它是不是是这样子吧,你是不是应该先处理当前这个节点的左左左指针,再去处理这个当前节点的这个右指针。是这样子的吧,所以说我们先来做一件什么事情呢?来同学们写一下,先处理。我直接先把这个代码先写下,先处理是处理当前节点的,当前节点的前驱节点。
15:05
前驱。前驱节点怎么写呢?各位朋友非常的简单,一句话的事儿来走。如果。如果node。load.get left。它怎么样,它等于空的话。各位。如果我们这个node.get na等于空,那我们现在就可以干什么呢?写上去话,就让当前节点,当前节点的左指针。左啊,左指针。诶,这样子啊指针。这样不好写啊,左指针干什么呢,指向。指向前驱节点。前驱。节点,这个大家理解啊,那就说我这样应该做一件什么,load.set na。
16:00
然后呢,前驱节点就是P能理解吧,呃,你把这个做完了以后,还要修改当前节点的左指针的类型。啊,要修改当前节点的着。指针的这个类型。什么类型呢?那就是node.set。是这意思吧,那应该把它置为一。也就是说这个时候我们就认为这个一,就说你当前这个浊指针,它指向的是一个什么呢?是指向前驱节点。就当前这个就相当于说它是指向什么呢?它是指向的是前驱节点。前驱节点。能理解,那说老师你这个有点不好理解,不好理解,我给你举个例子,还是打开我们换成假如我们便利到第一个漏了。假如啊,我们遍历了第一个node了,本这个八,大家知道此时此刻这个。
17:01
这个pray是不是现在是空的,因为你你不停的往上走,这个pray还没动过呢,它不停的往下按照这个中序啪啪啪啪走到这走到吧,这个P11111次都没动,那P一个都没动的话,它应该保持原子是谁是空,那也就是说如果我们以这个八这个节点八这个八这个节点线索化来看的话,它的代码就应该是这样子的了。那就说我们处理完了过后,那么这个八节点的,我们这以八号节点来讲解啊,以。以什么呢?以八这个节点。节点来理解的话。来理解,那么同学们就应该这样理解,就是这个相当于我们这个八号节点的。就八节八号节点的八节点的这个left,它应该只向一个空了。对的吗?说老师为什么之前空了,你看你按照中区边利八的前区节点是不是空了没有吗?你没有没有写错啊,那么八的这个同时再把这个八节点的它的left type是不是为一了呀,当然我们可以验证。
18:12
等于一,为什么等于一呢?就代表我们此时此刻这个八呀,它线索化过后,它的左边这个指针其实是相当于指向前去一点空。好,这个就醒完了。那么你现在只处理了。这个节点的前驱节点,你是不是还没有处理它的。后期节点呢?是不是你现在只是处理他的这个,就是关于八号的前驱,那有没有你还没有处理这个八的这个后继接触这个这个三还得指向,就说你这个后继呢,还有一个八要反向指向这个三号。这样才能表示我的八的后继节点呢是?是三,也就是说现在还要处理的是这条线。
19:02
是不是同学们?还要处理这条线吧,那你处理这条线的话呢,同学们看,这就需要同学们动脑筋了,也就是说当你处理这个右边这个节点的时候,其实是什么意思呢?其实是我们在下一次处理的这点要理解啊,相当于说这个漏呢。往这边走了,然后让pre指向这个节点的时候,在这个下一次的时候,我们才去让这个load节点去指向,呃,去去处理现在看到的这条线,这个有点不好理解,大家认真听。那也就是说,实际上你在处理这个八的后继节点的时候,其实是在下次递归的时候,让他的这个下下一个漏的节点来来去指向这个八,也就说在漏的这个关系建立好的情况基础之上,再让它反向指向它,也就是在下一次处理的。有点绕是不是好?没关系,我把代码写出来,你们就大致明白什么意思了,现在呢,我们再来说处理这个后继节点。
20:06
后期节点,那后期节点其实是在递归的时候,是在下次处理的。是在下次处理的,那代码呢,其实非常简单,我写一下大家就明白了,其实就这样写,就是什么呢?就是PRe.get我们的right。Right。好,如果是等于空的情况下。如果是等于空的情况,因为你只有等于空我才能去处理,如果它本身这个节点它已经有值了,你就不能不能动,所以说pre等于空的情况下,我们现在就要写这样写了,PRe.side right指向我们的当前节点。然后再怎么样呢,点right。然后呢,它的类型哦,Type。Type,它的type呢,我们就设为一是这样子的。大家看能不能理解,当然你在做这个事情的时候呢,你要小心一点,因为。
21:03
如果这个他。不等于空,你就不能做,所以说界面还有个判断,就是pre呢,它不等于空,我们才能去做这样的一个操作,能理解我的意思吧,好,要加一个判断。这判断好代码呢,咱们就写完了,这点有这句话有点不好理解啊。有处理后继节点的时候,实实际上是用下一次来处理的,下一次就是你在下一次挪动时候,当漏指直到这个三的时候,然后呢,P就指向了八,这个时候在这种情况下我们做了一个什么动作呢?大家看我们还以这个八节点来处理,这个时候你用的是P不等于空好PRe.set right PRe.set right notde,其实就是搭建了。这条线看到没有。然后呢,再把这个pre,因为你现在是这个位置嘛。再把P的这个。右边的这个指针的类型是为一,这这样就搞定了。
22:05
这这点大家要注意啊,因为你是单向的,你不能说同时处理这个左右。明白这意思吧。因为你刚开始处理前驱件的时候,实际上也是这个逻辑。明白啊,建议大家认真理解一下,好,这个呢,就是我们所说的这个处理后期,但是你这个处理完了过后,不要忘了一件事情。啊,我把这个地方也做一点注释好吧,做什么让前区。前区节点的右指针。右指针干什么呢?指向当前这个节点。是这意思吧,同学们,下面这句话是什么意思啊,改变或者修改啊,修改这个前驱。前区节点的右指针类型。又指针类型这个呢有点不太好理解,就前面这个还好理解,这个呢有点不好理解,就是我刚才讲的,它是进行下次的处理。
23:04
好,那么这个处理完了之后,还有一件事情,特别特别特别的重要,就是这个动作一定要加进去,否则这个线性化,线索化就会失败,这句话是什么意思,尤其重要啊,很多同学在写线索化的时候呢,这句话没有写。这句话是每处理一个节点后。节点后让当前节点,当前节点是下。一个节点的前驱节点。这个大家看看能不能看懂。因为你你你这个你现制化过后,你的node是往下面走了一把,但是你pre呢,就变成了上,就是你pre也也得移动一下,就是说当你noe往下走的时候,这个pre呢也要跟着走。你要保保存这个上一次漏,你才能实现这个后期节点的实现。你明白吧,好代码,其实到这我们就已然写完了。
24:01
啊,代码量不大,但是呢,有一点难度是不是同学们。
我来说两句