00:00
好,那现在呢,写完过后,我们是不是应该测试一把了?对不对,我们是不是应该测试一把,诶,这个地方不要了,我们是不是应该测试一把,来测试一下,我们测试一把。这是一。一把这个啊,中序中序线索。线索二叉,二叉数的一个111个功能是否正确。好,那么现在呢,我们还是老规矩,我们就以这个为例吧,我们就以这个,呃,以这这样一棵二叉树为例,我们原先二叉树这样子的,待会呢,线索化过后会变成这个样子,是不是好,那现在呢,我们开始来玩一把,首先呃,有些代码我就我就溜吧,这快快速溜一下,Here no。Load,我一共有几个节点呢?同学们看我一共需要创建六个节,六个节点好,我们现在就开始写了第一个节点,第一个节点的名字呢,我们比如说叫汤姆,好吧,我们快速的。给他走一下,那第一个节点呢,其实说白了就是我们的root节点。
01:03
是不是这个意思,下边呢,我就复制了啊,一共有六个,好第二个节点,我们叫Jack,没问题吧,同学们Jack,然后呢,我们就写成LOAD2。第三个第二个节点它的编号不是二啊,第二个节点它的编号是三,第二个节点它的编号是三,所以说呢,我们要把它写成三好,第三个节点来,第三个节点的话呢,它的它的编号是六。好,我们写成六吧。六然后这个名字呢,我们改成史密斯,史密斯OK,第四个节点,各位node是第四个节点呢,我们看一下它的编号是几啊,它的编号是八,OK,那就改成八。把这个名字能不能换一个叫做Mary?问题,下面第五一个节点NO5第五个节点它的编号是多少呢?八后面是十,好把十写上。
02:01
再取个名字叫king好随便写啊,King第六个节点MODE6好六是14,对不对,再给它取一个名字吧,叫做D好随便好,现在呢,我们把这个关系建立起来。我说了啊,呃,二叉树,二叉树呢,我们后面会递归的,创建二叉树。二叉树呢,后边我们要递归创建,递归创建现在呢,呃,我们就笨一点,我们就笨一点,我们就手动创建,实际上不可能每次都是像我这样按照这个图形来把他的关系建起来,对不对,但是为了简单的,我们先这样子手动创建啊,目前现在现在简单一点。简单处理使用什么呢?使用这个手动啊,手动创建一下。然后后面呢,我们可是用程序呃,把你这六个啪了一下,111段代码就把这个关系搞搞明白了是吧,现在呢,我简单处理一下。
03:03
好,嗯,那这个关系其实挺简单的,我们先把这这个关系搞懂,第一个root root site,它的na是几呀。现在看一下note set,它的三就是NOTE2。NO2。很简单,No搞定,那么root set,它的ne right,它的right t呢,是LOAD3。把这个放进去,好,这地方线就说了,那NOTE2呢,我们看NOTE2下面呢,也有两个节点,我们看一下NOTE2是有一个八有一个十。八是NOTE4。这个别写错了,待会呢,我们要测的好,还有一个set,它的right right是什么?是十,那就是漏五了,是这样子吧,同学们。这个做完了过后,我们还有一个就是NOTE3。NO3这个节点呢,它指向的是A,它应该有个右边还是左边,我看一下。
04:05
是它的左边啊,是它的左边,看懂了14呃,NOTE3呃,它的左边那就是set。呃,Nap是吧,Na几呢,Na就是我们这个节点呢。哪个节点呢,就是NODE6没问题吧,同学们好,六现在我们关系就已经形成了,形成以后呢,我们来线索化一把,我们测试线索化。各位,呃,那线组化呢,特别简单,我们。我们创建的是一个binary tree,是不是啊,这个地方这个名字我们改一改吧。我们叫ried的ban tree,这样呢比较OK,比较清晰一点,好吧,那我就创建一个RI。Battery这样一个对象实例明白。好分配一个名字。
05:01
他这个地方。看一下啊,这个地方red tree。SW,好,我复制一下看看。说什么问题啊,六一个。六。OK。那么分配一个名字就可以了。就th by tree吧,就他,然后不要忘了一件事情,这个root是不是你没有给别人了,那我就没法调,所以说呢。点set它的root是谁啊,就是你这创建的root,那这个方法呢,大家可以看到这个方法呢,我们这he load,呃,那这传就应该传root,但是太麻烦了,所以说我对这个ready的note呢,进行一个重载。这样简单一点啊,我重载一把。涂在一把什么呢?就是线索化的这个方法。简单一点啊,那我就去写public avoid thread。啊THRD啊,把这个方法写进来。那怎么重载呢?我在这里直接就去调用,在这里调用啊,就是调用我们的方法就是这点right。
06:09
把什么传进去呢?把这个root传进去就可以了,大家看在这里面呢,我直接先判断呢,等不等于空,如果等于空就直接走了,所以说WHY在这一层呢,我就不再判断root到底是否为空,明白这意思吧,好,现在我们来线索化的时候呢,就调用刚才我们写的那个方法,Ried not,代码写完,那代码写完过后我们怎么测试。我们怎么测试这个线索化中序线索化是对的呢?同学们想想我们怎么测试呢,我们我们找一个点就可以了,比如说我们找。十这个点,我们看看十这个点的前驱和后继节点是不是已经变成了三和一就可以了,理解意思吧,那现在我们来玩一把。啊测试我们以测试以哪个的呢?以我们以十号十号这个节点做测试。
07:05
十号节点测试来玩一把,呃,十号节点其实就是我们的。NO5是这样子吧,同学们,那我就拿一个啊note5.get它的。Left。Na。好,我写上一个left no,好吧。Na node。它左边这个节点,那同学们知道,呃,因为现在我已然线索化了,我已然线索化了,那这个时候我NOTE5得到的这个左边圆,在你没有线索化的时候,这个get ne肯定是个空。是不是那现在我线索化了过后呢,我node get它的这个这个这个na呢,就变成了它的前驱节点,也就是说三号。如果我拿到四个三号,说明我这个线索化中区线索化是OK的,明白这意思吧,那么我们输出一下就可以了。
08:00
那同学们,我们输出一下这个na node的一个情况,好不好把它输出来。OK,那现在呢,我们把这个话打出来,我们说十号节点的前驱节点。十号。十号节点的前区对不对,前区节点诶写错了啊,节点是。OK,把它打出。我们来运行一把,我们来运行一把,看效果。那么我们可以看到这个效果呢,的确是JT,就是我们的三号,看是不是三号呢。三号吧,三号是Jackie,没有问题吧,没问题,好,我们再来看一下十号节点的。这个后继节点是什么玩意儿?走一个十号。说节点的后进。后继节点是什么呢?我输出一把。那当然我要获获取一下啊,NOTE5。
09:03
对不对,5.get它的right。是这样子吧,同学们,我们仍然接收一下这个right。的这个名子啊,那就给你们写成right node没问题了,同学们。好,同样我们把这个right节点拿拿过来,Right节点就是它的后机节点了。因为我们右面呢,是指向它的后极节点的,对吧,那这个应该是几呢?刚才这个是三,那现在它的后继节点如果没有出错的话,就应该变成一。他原先是空啊,现在就是一了,来玩一把,我运行一下,同学们走起来。我们可以看到呢,它的后继节点啊,的确是一,是不是汤姆呀,说明我们这个中序线索化呢,是没有任何问题的。没有任何问题,那大家理解一下这个代码,看看老师这块,呃,就说大家想的明白没有。
10:01
呃,难度是这个线索化呢,稍微的有一点不太好理解,但是我已经把它讲的比较清晰了,就说第一步,第二步,第三步,每一句,每一个地方呢,我也用按照这个图给大家说出来了,尤其是在需要注意的地方呢,我加了三个叹号,千万不要忘了这句话啊,这句话一旦没有写,那整个线索化。就会断掉。好,同学们,嗯,关于线索化的这一个,呃,它的线索化的过程就写完了,待会呢,我们还要去完成一个功能是什么呢?就是就是线索化的一个便利,那么线索便利,线索话术呢,我待会下一个视频再为大家讲解,这讲呢先给同学们说到这里。
我来说两句