00:00
各位,我们刚才给大家讲解了线索化二叉树,那现在呢,我们来看一下便利线索二叉树的这么一个。呃,功能怎么去实现,那首先大家看这个幻灯片。对前面的中序线索化的二叉树呢,我们需要实现一个便利,首先有一点大家先思考一下。因为线索化过后,各个节点呢,它的指向有所变化了。因此原来的便利方式不能再使用,为什么呢?大家想我们还以刚才这个图为例,你原先在便利这颗没有二叉树的,没有进行线索化的这棵树的时候,大家想你是怎么遍历的,是不是你进行中序编辑的时候,你是有一个判断,当它的左子数或者右指数为空的时候。你才停止便利对不对。是这样子吧,同学们。那如果这样子的话,同学们想一个问题。
01:00
同学们想一个问题,就是说如果我们仍然以原先的这个中续或者前续或者后续的便利,是不是它是。它是会出现一个死循环了,因为有可能他的他原先自空的这个右子针或者左子针不再是空的了。那这个时候你就停不下来,所以说同学们可以看到这段代码,如果我们用原先这种方式来编译的话呢,会出问题,来看一下。来,同学们看我不在这里。注意啊,当。当。对,当线索化,线索化。线索化。诶,这个还不行啊,现。线索化。当线索化二叉树后,哦,不能。不能再使用,使用原来的。原来的便利方式了,便利方法。
02:02
那我给大家举个例子啊,同学们看,如果我们再用原先那个方式来走的话呢,你看会出现一个什么情况,Thread threed battery tree,点我们仍然用in fix order,那同学们可以看啊,当我运行的时候,同学们看到下面呢,报了一堆错误。报了一堆错误。看到没有,这这一堆错误,你们有发现是不是285279 285279说明什么,说明在这一行。在这一场,或者说我们说在这一场已然出现了一个死循环。因为他始终是在285279 285279这样子反复的做,那死循环就会造成我们的溢出。是不是好,那这样的代码呢,就出了问题了,出了问题那怎么办呢,同学们看。大家看我这已经有一个解决方案。嗯,这时需要使用新的方式来便利。线索化二杀素,各个节点可以通过线性的方式来便利,因此也不需要再使用递归了,这样还提高了便利的效率。而且大家要记住,当你便利线索化二叉数过后呢?你按什么方式线索化的,当它便利完了过后,它的秩序应该跟对应的便利方式保一致,比如说我们刚才是对我们刚才刚才是以中序线索化二叉树,那我便利购物呢,仍然应该和原先的中序遍历保持一致,就那个顺序啊,输出的顺序保持一致。
03:33
是这样子吧,同学们好,那现在呢,我们就直接升代码了啊,直接升代码并不是很难,大家这个比刚才要简单一点,来打开我们的eclipse,我在哪里写呢?我们就在这个数里边写就可以了。在哪里写啊?我们来写到这儿吧。直接写到数数里边。我们写在哪里呢?我们干脆就写在先前,这一个就是线索化。
04:01
二叉树的方法的前面我们写一段代码,叫做便利。便利。现。线啊,应该这样写遍历中序,你这个因为你遍历方式跟中序是你用中序后续前续还是有关系的啊,所以说我们写便利便利这个干脆这样写啊,就叫便利线索化二叉数的一个方法,那现在呢,我们就就来开始写了public voidri。什么呢?对不对,这种方式来编译,首先呢,我们先要定一个变量,定义一个变量干什么呢?我们存储。存储存储什么临时应该这样说啊啊,临时存储吧,就是或者存储一个都可以啊,存储什么呢?存储当前便利的这个节点,因为后面需要用啊,而且大家一一定要记住,我们便利是从root开始的。
05:02
是不是,所以说我上来呢,先写一个load。追听para load,那么初始化呢,我们root。因为我们从入开始嘛,那么先来判断。啊,Y循环,这个Y循环呢,我们一直做,只要我们的no,它不等于空,我们就可以来便利,是这样子吧,同学们。好,那么同学们想,我们在这个循环便利的时候,是不是还按照这个图来讲,是不是我们首先要找到哪一个呢?是不是从这个节点一直找,一直找,我们首先找到它有一个type,就是na的type。这个类型等于一的这个节点才表示我们的头啊。也就是说你你整个这个线性遍历的时候呢,你首先要找到八这个节点。那这个八个八这个节点有什么特点呢?八这个节点它有一个特点就是。他有一个节点,它有一个特点,就是说它的这个left left。
06:06
这个type呢,它是等于一的。是这样子的吧,所以说我们先把这个代码呢给大家写出来。干什么呢?循环的找到。找到什么呢?Left type。等于V等于一的这个节点。等于一的这个节点,第一个,第一个找到的,第一个找到的就应该是八这个节点。是不是这个道理啊啊,当然了,我说了,后面随着这个随着这个Y循环呢,嗯,这个load可能会变化。啊,所以说我们写上这句话后面。诶,后面会。后面后面随什么呢?随着这个便利,便利会而变化而变化。不是它不是固定的啊,就是说它不是固定的而变化。
07:01
啊,变化是这样子的吧,好,那么为什么呢?因为当当left,注意听当等于一的时候。一的时候说明什么?说明该节点。该节点是按照按照线索化。这样写啊。线索。线所化线。线所化。是按照线索化处理后的。处理后的有效。有效节点。是不是这个意思啊,同学们,那现在我就写这句话了,Y循环,如果root.get它的ne type,只要它等于零,我就一直涨。是不是,那就让load等于load.get net?是不是这个道理,我就一直找,直到他找到一个。
08:03
Na type等于一的才停下来,那同学们可以想象,第一个我们找到就应该是八。是这样子吧,因为你一直这样找的嘛,你看na一直找肯定就找,从root一直找,你看从root开始走,这这个root开始第一个它肯定不是他自己肯定不是一嘛,在下三三也不是,三也不是,接着往下找。是不是这样就找到八了,八就是第一个节点。八找到以后呢,下面我们就打印,打印当前这个节点,这个能理解吧,当前这个节点。好,非常的简单,一句话是system。好,我们把把这个节点输出即可。那这个做完了以后,下面又干什么事情呢?好,下面我们要继续做这样事情,如果当前节点,注意听啊,如果当前节点的右指针。当前节点的右指针指向的是后继节点。
09:03
它有什么特点呢?大家想。就一直输出。也就是说我这个呢,当天节点打完了过后,我再看他的右指针是不是后期节点。那有些同学老师我怎么知道node的右指针是不是指向后继后继节点呢?因为刚才我们讲过后继节点的它的right这个type是等于一的。是这样子吧,所以说我们这句话应该这样写,While循环什么呢?no.get它的right。是这样的吧,如果它等于一。说明什么?说明当前这个no指那个right no,当前这个节点的右。右呃,右边指右指针指向的这个节点的确就是它的后期节点。这样没问题吧,如果是这个节点我们就干什么呢?哎,我们就准备输出我们就可以,我们这样子啊,先就获取到,获取到当前节点的这个后继节点。
10:05
怎么拿到这个后期节点呢?Very easy,直接用node.get right就可以了。因为你右边的就是我的后几点,然后输出当前这个输出这个节点就完事了。他一直找一直找好,当Y循环结束的时候,说明什么问题?说明什么问题,说明你现在。已经遇到一个不等于一的了,那如果不等于不等于一的话呢,我们就替换。I替换。替换这个便利的节点就可以了,怎么替换呢?非常的简单,让他直接去指向它的right。代码就喜欢了。那有的同学这个东西我这看不懂啊,没关系啊,如果同学们看不懂,待会儿呢,我们用debug的方式来给大家再追一遍,你们一下就明白了。因为这个东西都说了,我们不管怎么讲,大家都会觉得有点难度,好,同学们,我们再来便利,用我们的线索化的方式来便利吧,看看对不对啊,原先方法已经不能用了。
11:08
好,我先输出,我先输出一句话。System out,好,我说呃,使用使用线性便利啊,叫做线索化。现。所化的方式便利什么呢?便利这个线索化二叉树。没问题吧,同学们,那现在我就把这个代码给大家写一遍呢,所以。点什么呢?我们刚才写的thread list就可以了,我们看看用这种方式输出的是不是跟我们这个中序遍历的顺序一样,一定要保持一致才是对的啊,也就是说我们输出顺序应该是八,三、11 14和六。如果这个顺序不对,说明我们这个便利就有问题,好各位朋友运行吧。
12:05
好,我们可以看到现在呢有一个问题。好,有一个问题,空指针出现哪里?那么我们可以看到,在这里我们有一句话有问题,他说root。你为什么写root,这有问题的,是不是刚才我们拿了一个root就不对了,因为你现在不再是root了,你是把root给到node了,因此这个地方应该写成node。是不是我们这留了一这方,就刚才这个地方就写的有问题。因为你一排错就排到了吗?来各位朋友再运行一把。并一次。好,同学们可以看到现在我们使用线索化便利的时候呢,八三十一,14和六。好,跟我们想的一不一样。八三十一,十四六完全正确。完全正确,所以说我们在出现一个错误的时候呢,一定要注意你在比如说假如你这个地方没有替换,会出现什么问题呢?我来编你。
13:07
你看,死在这儿了。对不对,所以说我们在每一句话呢,都有它的道理的,不然的话,你不替换他就反复在这方打成了一个什么是成了一个死循环呢。因为他不往下走嘛,好,那现在我们用debug的方式来给同学们来。Debug一下,追一追这个代码来,现在呢,我们在这里下一个断点。我们在这里下个断点,来,各位朋友下个断点呢,我来个debug,我们来看看这个顺序到底是怎么玩的,来走一个啊。首先呢,我们先追到这个代码里面去,首先我问大家,第一个我们拿到节点漏应该指指向谁,是不是指向第一个节点汤姆,那么汤姆现在它不等于空进去了,进去过后汤姆的na的type肯定是不等于它是它就是等于零的。因为。你现在相当于说。
14:01
相当于是在这吗找到它,找到它,你现在它是不等于它是等于零的,所以它往下面走一下进,它会进到我们的这个Y循环来进去。果然进去了,下一个好,这个时候这个load指向哪里呢?指向我们的Jack了,编号为三的,编号为三的也它的那个type呢,也等于零,于是再进来一次。好,这次就不一样了,这次他已经指向八这个节点了,八的left type是等于一的,因此Y循环退出。好,这时它会输出我们这个八号节点。说出来了吧,Mar没有问题,那这个时候呢,他接着往下走,Node的right这个节点type实际上是谁啊,实际上是三号。那。八的右边这个指针的这个类型呢,的确也是等于一的,因此呢,这个Y循环会进去,它会输出几呢?它会把下一个节点输出,也就是我们的三号节点。当把三号节点输出来过后,我们再来看此时时刻,他现在把三号点三号节点的右边。
15:06
这个是蓝色的线,不再是。不再是我们的一个真实有效的后期节点了。怎么办呢?他会。退出这个Y循环看啊是不是退出来,退出来过后呢,他让这个节点的right给他,也就是说现在一复制这个node呢,就真实的指向了十号,因为他要准备下一次嘛。他要准备下一次,所以这个时候呢,他会。往下走来看。因为note现在已经指向哪里了,指向十号了,就是我们这个king。接着继续往下走,好十号本身它的这个na type就是。十号本身它的它的na的tap就就是向这个方向,它本身就是一个有效的节点,线序化有效的节点,因此呢,这个十号。会这个外循环他不会进去啊,他不会进去,他就直接把这个四号景点输出了。
16:01
好,十号节点输出以后,我们继续往下看,十号节点的右边这个指针的类型是什么?是一个红色线,显然它就是一个有效的,于是它会把一再输出,它会进来啊,进到外循环,好得到右边这个漏呢,再一得下这个应该就是四号。呃,是哪一号啊,是是一号对一号,一号这个节点是什么就什么输出来。八怎么看一号输出来,以此类推,下面我就不再debug了啊,我就不再debug了,因为也比较简单,所以说同学们呢,我我把这提一下,所以同学们经过一个debug的方式,我相信大家对这个更理解了一些,对不对,代码并不是很难。好,现在呢,我们到此就把这一个。就把这个所谓的便利啊,便利线索化二叉树的代码就给大家讲完了,那这里呢,我留了一个作业。我这里讲的是中序线索化二叉树。那么前续后续。
17:00
思路类似。思路的意思,同学们呢,做一这个课后把它完成就可以了,包括呃,用前序线索化二叉树和。遍历都把它写出来好吧,好同学们,那关于这段带这个地方我们就讲完,我们把刚才讲的内容呢,给各位朋友板述一下,看看我们讲了哪些内容,来捋一捋思路。屡屡思路。OK,首先呢,我们在这里,我们在这里讲的是线索化二叉树。我们怎么讲的呢?我们怎么讲的。首先我们先。给大家看了一个问题。看了一个什么问题,说我们目前有这么一个数列,而且呢,我们把它形成了一个,形成了一棵二叉树,这个二叉树呢,长的就是这个样子的。没问题吧,但是我们分析这棵二叉树呢,它有一个,它有一个问题就是什么呢?就是它没有有效的利用我们的左右指针。
18:00
所以说这个时候呢,如果我们希望有效利用的话呢,我们就可以对其进行线索化,就是我们分析的问题。从而也提出了我们的。线索二叉树的这么一个概念,是这样子吧,好,当我们听完这个。提出这个问题以后呢,我们紧接着就给同学们介绍了线索二叉树的一些它的特点。啊,这个特点呢,一共有四个,我就不再一个一个的念了,同学们给大家板书到笔记里面就可以,对不对?好,这是线索二叉树的基本介绍。给各位朋友板书到这里,诶这个不行啊。这个变大了,反出四点嘛,也很好解决,大家注意啊,我们说一个节点的前个节点叫前驱节点。一个节点的后面,这个节点叫后继,不叫后区,好吧,不要把它念错了。小心念错啊,那这个写完了过后呢,我们就说,诶,咱们就给大家讲一个案例呗,那么案例呢,就以刚才分析的这个案例来给大家讲解的,说白了。
19:03
就是把这一棵二叉树。进行一个中序便利啊,中序线索不是线索化。那在讲之前,我们首先给同学们说了一下思路,就是我准备怎么干这个事儿。对不对,我怎么怎么干,那具体来说呢,这这是我们的一个思路分析。思路分析这里呢,我就没有费费大劲了啊,我直接呢,以呃一个图解的方式给同学们来讲来讲解,就说这个这个线形呃线呃以以画图的方式给大家做了一个分析,把这个分析完了过后呢,我们说当我们线索化过后呢,存在要小心一个问题,什么问题呢,大家看我这里写出来了,就是当你线索化过后呢,根据我们的分析,我们发现这个漏的节点,它的left和right呢。它有可能指向一颗指数,也有可能是指向前驱或者是后继节点,因此这个特点会直接影响到我们后面的代码实现。
20:06
我们怎么实现的呢?是不是为了解决这个问题,我们给每一个节点增加了两个属性,一个是left type,一个是right type,区分它是指向左指数或者是右指数,还是指向前驱,还是。后后继节点是不是这样子的,好,当我们有有有了这个思路以后呢,我就没有啰嗦了,我们直接把这个代码给大家实现了一把。那这一门就是我们的代码实现。代码实现。我也给同学们。加一个小箭头,把代码呢给各位朋友满足到这里,这就是我们全部代码。线索化,二叉树的全部代码都在这,包括它的呃线索化和它的便利。OK。哦,好,当我们把这个做完了以后呢,我们又紧接着给他讲了一个便利线索二法图,因为刚才是线索化。而现在是便利,便利我们提出,因为你线索化过后呢,这个二叉树它的节点指向有所有有改变,比如说原先。
21:09
为空的,他不再为空了,你如果还用原先的便利方式来做的话,就有可能实现这个死地归或者是循环。对不对,那就不行,怎么办呢?我们就使用便利线索化二叉树的方案来给大家讲解的,是这样子吧,同学们好。呃,这是我们线索便利,线索化二叉树的一些特点,第一个首先呢,我们给他做了个说明,第二点我们做了分析,最后呢,我们上了代码。尤其要注意哈,千万不要因为各个节点指向了,因此原来的便利方式不能用了,这点大家一定要有印象,不要再用以前的方式来便利了。那代码来说呢,呃,就是这块。哦,这个地方上面已经有了,那我就呃截了一小块吧。线索化的那一小块,线索化便利的那一小块,代码哪里呢?
22:02
实际上就是这。是不是就是这么一小块儿啊。那这个代码我们是。放在哪个类里面写的呢?各位同学,这个是在我们的ried。什么呀,这个binary tree OK tree。这个类中写的是吧,是在这个类里面写的代码就放这。有个印象啊,同学们,好的,那最后呢,我们还给大家留了一个作业。就是。同学们完成这个过后呢,希望把这个作业再念一遍,就我写到这。这是什么呢?就是线索化。线索化。2A线所画二叉树,二叉树的课后作业。那这个作业呢,我我要求同学们在老师讲解的基础上,把前序和后续这个呃,线索化也做一遍,好吧,也不是很难,大家动动脑筋就可以了,好,各位同学,关于线索化二杀术呢,我们就先给各位同学讲解到这里。
我来说两句