00:00
下面呢,为了。更深刻的理解线索化二叉树呢?我们来举一个实际的应用案例,大家看这个案例的要求很简单啊,他是说将下面的二叉树。按照中序线索线索化。那么我们首先要明确这一棵二叉树。如果按照中序遍历的话,它的顺序应该是八,三,11 14和六,这个大家能理解吧,因为你按照中序遍利化的,它就是这样子的,那么。这个题已经说出来了,现在我们在做,之前呢,做一个思路分析,来我们看一下思路分析。那如果我对这一棵二叉树进行中序遍离过后,它应该长什么样子呢?来,同学们聊一聊。我呢,就直接在这里画了啊,同学们时间的关系,我把这个复制一下,直接。放到我们这边来。
01:02
好,这个图不管它啊。那我们来看一下这个后面这个图,先把它挪到这边来,好吧,这这个这个压缩文件放这,那么我们现在看,首先刚才我们已经讲过了,这棵二叉树如果进行中序便利化,呃,中序便利过后呢,他得到的顺序应当是这样子的。也就是说,中序后。也就是说中序便利的结果应该是这个好,那么你在进行中序线索化二杀术的时候,你就要考虑它的结果,前区还有后期节点要满足这个条件,那么我们来一起画一下,首先我们来分析第一个八八,前面呢,没有前驱节点就不用去动它的左。左左指针,那么八的右,它下面这个后继节点是三,于是呢,我们让这个它的右指针指向它的后继,呃呃,那个叫做后继节点,好,这个线呢,给大家画到这里来。
02:03
好,这个八我们就处理完了。那么我们再看三。三呢?他。它的问题是它的左右两边大家看清楚啊,它的左指针和右指针已经充分使用了,你不能改动,说三呢,你不能处理。你不能处理这个三,因为三指左,左指针和右指针已经是实际上是使用使用起来了,你不能乱动,说三不用动,那么现在到十了,十我们来看十的前区节点是三,于是我们让它的左指针。指向它的前驱节点及三。那么十它的后继节点是什么?是一好,这时我们让它的右指针指向它的后区节点,即一,诶,后后继节点啊,后继节点是一。那么一对一来说呢,一没有办法线索化,因为一的左右指针已经充分使用了,不能动,我们再看14这个节点实施这个节点呢,它的前区节点是一说说我们可以用什么呢?OK,我们用它的左指针。
03:11
指向它的前驱节点。就是这个节点没没问题吧,好,这个地方大家看清楚了,那么14的呃,后继节点是谁呢?16,于是乎我们让它的右指针指向这个六。OK,看清楚啊好,六我们就呃14我们就完成了,那么六怎么处理呢?六它的前驱节点是14,它已经指向这个14了,不用动。那么六的后继节点是谁呢?没有,没有就不用动,所以说当我们如果以图形化来讲的话,这棵二叉树中序变离以后呢,它应该是变成这个样子的。那待会我们要用代码实现。大家有没有发现?如可能听到这有些同学已经开始心里面就有点呃,有有点有点犯嘀咕了,说老是这不对呀,你这样子并不能完全的保证这个中枢变异的,它的一个一个节点就是指向它的前面和后面。你比如说一。
04:12
你比如说一一按照中区边理它的前区节点哦,它的前区节点实际上是11,但是你它的左指针并没有指向。并没有,并没有指向这个十啊,是不是,是的,确实是有这个问题,待会我要分析,你再比如说一一,它的这个后继节点,按理说从这个中续并列来说,它应该是指向14,但是它实际上指向16的。也不对呀,所以说我要把这个问题给大家答出来,大家看。当线索化二叉树后,Node节点属性,这个ne和right呢,就有这么两种,就有这么几种情况,第一点大家看啊,待会我们在写编程的时候要考虑。Nap的指向的就是na的呢,它有可能指向的是左指数。
05:01
啊,也有可能是指向前驱节点,你比如说一这个节点,你看一这个节点left呢,它其实指向的是自己的左指数三嘛。而十这个节点,大家看十这个节点呢,它的耐呢,确实指向的就是前驱节点,你看十。它的前驱界点。他左指针就是na,确实指向的是它的前驱1.3对不对,所以说对于这个na。这个属性呢,或者叫这个ne的指针就已经有两种情况了,同样right呢也有这两种情况,Right呢,它有可能指向自己的右指数,也有可能指向后继节点,你比如说一这个,你看一它的这个右指针其实是指向他自己的右指数,并不是指向自己的。后继节点,但是十,你看十,它的right的确是直接指向自己的。这个后期节点一对不对,所以说这这个地方我们要把这个问题分析出来,待会儿呢,我们写代码就会有一个比较明确的认识。
06:04
比较明确的认识好,那同学们这样子啊,这样子,那么关于我们线索化二叉树的这一个思路分析呢,先给大家聊到这里。一会呢,我们用代码将其实现,大家就能理解是怎么回事了。好,代码实现呢?我们下一个视频为大家讲解。
我来说两句