00:00
好。所有的这些代,所有这些呢,通过代码大家理解起来就比较OK。首先我们看。对于这个数的便利,我要给大家讲清楚。二叉树里面呢,有三种特别重要的便利方式,这三种便利方式对我们后边使用。二叉树非常重要,一个叫前续便利,一个叫中续便利,一个叫后续便利。那么首先我们讲一下什么叫做前中后,大家看我这句话。大家看这句话啊,先输出负节点。再输出左指数和右指数,这个就叫做。谦虚、便利。也就是说他先把不节点输出来。采取。左左指数,再是右指数,这个就叫前虚,那何为中续便利呢?先变利左指数。输出负结点,再变利右指数,这个就叫中续变历,后续变利,先把左指数变历完毕,再变历又指数,最后输出负结点,这个就叫后续变利。大家看我这有个小结,怎么记?
01:16
怎么记这个前中后呢,你主要是看这个负节点。它在什么位置输出的。如果负节点是先输出。那他就是。前续的,如果这个负节点是在中间,就是。中间输出,那它就是中学变力,如果负节点最最后输出。那那就是后续便利,好这个基本概念大家要理解了啊,好理解过后呢,我们现在直接走代码了,现在呢,我们准备写一段代码来给大家演示一个前续中续和后续的便利,大家首先看我这里有一张图。这个图大家可以看到是一个二叉树,对不对。这个没问题,肯定是个二叉树。
02:01
那么这是个二叉树呢?待会我要把这个二叉树建起来。然后呢,用前中后给大家跑一把来,现在呢,我们来开始写代码,首先首先同学们看一下我这。要做的事啊,我把这个图截过来。我们要把这个这边这个数的要创建起来,并且呢完成。前中后的便利,我们要完成的目标。完成的这个任务,第一个是要创建,创建左边的左边的二叉树。第二个要使用使用我们的前序。啊,前续中续和后续进行遍历。那么这是我们的第一个最简单的案例,后边的难度呢,会逐渐增加啊,先把这个电力搞定,那现在呢,打开我们这个。Idea,我们写一个包包,这个包包呢,我们就叫二叉树bay tree。
03:06
OK,好,我们先写第一个案例,走一个。我们这个名字就叫binary tree DEMO没问题。好,跟上老师思路。那首先呢,我先写一个主方法对吧,这个很简单,那大家可以看到我们这边,因为你这里呢,有这个节点,这个节点有编号和名字,好,那首先我们我们先把这个节点定义出来。好的,我们先定义节点。定义这个节点。啊,那这个节点呢,我们就这样取个名字吧,叫hero node问题那he node呢,我们已已然进行这个初始化,比如说它有编号啊,它有编号int,然后呢,这个hero有名字,有名字我们也把它。啊,初始化下。
04:01
我就在这写了啊呃,编号呢,我们一般不让它变啊,初始化了一次就不动它了,等于你传进来的这个编号。好,第一个第二个它有一个名字,名字有可能变化,所以说呢,我用VAR来进行接收,下面呢,有向左边和向右边的一个指针。对不对,那就left。那下面这个hero等于初始化为空吗?对吧,没毛病,然后呢,We are right。Right,它也是这么一个节点。Nu。这个是我们的一个这个节点。那现在呢,我们就把这个二叉树写写起来。那class这个二叉树呢?我们叫battery tree。这个二叉树里面我们先写一个根节点啊,我们先放一个根节点放这。Root。
05:01
啊,书里面肯定最重要就是根节点了。因为你只有通过这个跟据点才能完成所有的这个操作初始化,我给他一个空。好的,这个二叉树有了,我们现在开始开始玩一把啊,我们开始玩一把是现在注意啊,我第一次先用这个,最最笨的办法就是硬给它连在一起,后面呢,我们可以把它做成一个递归,往里面追加,我们现在先用最简单的方法先用。啊,我们先用。先使用,诶先。使用比较啊,比较简单的方法。简单的方法直接关联,就是直接把它。直接把它关联起来的方法,直接关联的方法。好,那现在我开始创建几个,我们先看一下,我一共要创建几个节点啊,一共有五个节点,看清楚了来,那首先呢,我先创建五个节点,很快hero编号为一,给他一个名字叫松江。
06:04
啊,VR这个节点呢,大家都知道将来是根节点,为什么你们可以看到,因为它将来就是放在最上面的,对吧,所以说我给他起个名字叫root,其他的。以此类推,第二个节点。第二个节点呢,我们叫做看一下名字,第二个节点是吴用,第三个是卢俊义吴用。无用。好,然后呢,我就给它取个名字吧,叫叫HERO2,注意听啊,同学们,咱们争取一次性把它都听明白了,晚上呢,大家就可以做练习,然后这边第三个是卢俊义,卢俊义OK,第三个节点我们叫HERO3。HERO3。OK,我们在,诶我们再来第四一个节点,第四个是林冲。好,林冲。林冲呢?我们给它来取个名字叫HERO4。
07:00
好,最后一个就是关胜。OK。关胜,它是第五一个节点。Carol。好,现在这个关系已经有了。那我们怎么把这个数建起来呢?我们先来看他的一个最笨的方法,就是宋江的着子节点是吴用关起来,先说好,那就先关了啊,Root。点他的left。等于HERO2,我现在用的是最简单的方法啊,后面我们肯定实际开发中不可能这样玩。实际开发中肯定是你给我一个节点,我找到相应的位置加进去,后面我们会做这个事情,大家不要着急,先来一个简单一点的,你突然来一个猛的,大家可能有点跟不上思路。第二个节点Q3,当我们把这个工作做完了以后,大家应该可以想到就是这。这三个就连起来了,那卢俊义下面呢,还有两个节点,一个是关胜,一个是林冲,关起来那首先我们。
08:04
找到卢俊义。HE3。他的左子节点是大刀关胜。关起来,然后这个HERO3的右子节点是林冲。没问题啊,没没问题,还四好,最后我们把这个根节点给到我们这个by tree的这个root属性,那很简单,我们创建一个by tree。没问题吧,好,V are better就有了,然后呢,我们直接让这个better tree的root。指向我们这个root节点。好,同学们。经过这番。导致呢,整个这个数大家应该想到就成立了,现在我们重点是要完成中续后续的便利,待会注意看这个顺序对我们有什么影响啊,各位同学。好,现在呢,我要开始编写这段代码了。
09:03
编写这段代码。呃,那么我们完成这个中续后续遍历的话,在哪里写呢?在哪里洗比较合适呢?显然这个我们把这个方法呀,直接写到这个地方会比较合理,就在这里面写比较合理,是这意思吧。也就直接写到这个hero节点里面,比如说我在这边也是这么去设计的,直接在我们hero load里面写这个前序后,那么better里面调查一下就可以了,然后现在开始写东西,好,我们先完成最简单的前序,便利。前序便利前序便利,我先写个名字,Pray。Order。那你在进行这个便利的时候。我们是前序便利,大家都知道,首先呢,应该怎么样啊,是不是先把自己说出来。是吧,先把自己输出来,输出来过后我们再去走下一个节点,就是像我这写的一样,先去做这个自己的一个便利,但便利的时候呢,我们不需要传这个值,不需要传这个值,所以说我们取的时候就非常简单了,就这样写,先输出当前节点的值。
10:18
啊,前序遍历不这样子的,我想想啊,啊对前序遍历四前序遍历是先输出当前节点的值。那我就先输出了,笨。那要判断一下。啊,这个当前肯定就不会,当前节点不会了啊,当前点你都进来了,肯定他不会空,所以说我把这个节点的信息说出来。说出来啊,节点信息。啊,这个节点啊,节点信息。那么我们把它编号输出来一下,No等于这个。然后呢,它的名字等于WS节点。对,然后呢,把他的名字也输出来,为了好看,我们待会换一行。
11:00
这个就完事了。那下面呢,我们这个输出来以后,我们得判断它左左就要开始递归。递归的调用什么呢?这个呃,向左递归吧,向左。向左递归。输出什么呢,左指数。对吧,左指数,那你在递归之前,你要先判断一下你当前这个节点的左边是否为空。如果不为空对不对,我们才去进行向左边的。递归调用递归显示,那就this是点点order。对吧,那这边做完了以后不要着急,还要向右边向右。向右边这个递归。递归输出柚子树。右指数,那这个呢,也要做一个判断,因为你不判断有可能它下面没有了。
12:02
你又去输,那肯定就要报空指针异常,所以说右边呢,不如果右边的这个节点不为空,那么我们在进行向右的递归调用,那怎么样呢?就是刚才我们所说的这个pre order就写完了。好写完以后我们再调的时候呢,我们这样做。在这里大家看此时此刻,你这个是节点往下走,但是你其实是有一个根节点给它关起来的,因此呢,我们这个地方还要写一个。就说我调的时候还是通过这个BY去调哦,调它这个节点就是便利,前续便利。情绪便利啊,不着急,那现在开始写了。Order order,那现在我们就做一个判断,如果你当前这个root。你当前这个入等于空。啊,等于空,那就没法变,因为没东西嘛,所以说只有它不等于空的时候,你才去便利,如果它等于空,你直接其实一句话说,当前数为空。
13:09
当前二叉树。二叉数为空,不能变利。不能便利对吧,不能不能便利就退出去了,否则呢,我怎么做呢,我用root去调它的pre order。好,同学们,前序便利。我们就。写完了,那程序便利我们来用用,我们先来看看它输出什么效果,走一个。情绪便利的结果。钱旭。便利。程序便利呢,我用battery tree.pre order,我先不去运行,我们先自己想一想它应该输出什么样的结果啊,来,我们打开SL文件。我们先来说。前序便利的结果应该是,首先。
14:02
先把宋江说出来一号。然后再输出我们的二号。对吧,因为先把中间除出来,它就往左边走了嘛。往左边走,他往左边走的时候呢,他左右那边没有,他要把自己节点先先说出来,所以说这个二号就输出来,输出来我往往右边走,右边走的时候他发现三。就是这个节点说把三又输出来了,把三输出来过后向左边走,把五又输出来了,把五输出来过后,这个三节点往右边指数走,四又数出来应该是123。五四同学们,我们运行一下这个结果。好,各位同学,请看运行的结果,看看有没有问题。运营一把,OK。我们说出来看,这个结果跟我们想的完全一样,12354正确,好,现在呢,我们来完成一个中序便利。好,这些遍利呢,为了好看呢,待会我我看这个结构在这边看啊,这边看起来呢,就这边按照这个structureer呢,可以把我们当前文件拥有的这个类,还有它的方法显示出来,就比较方便,那现在呢,我在这来写一个,在P前面写一个。
15:14
呃,中区便利,我这样写比较好看一点啊,中区便利。那中需便利我就直接写了啊D中虚便利呢,有些人写的是me order,但更多的比较规范的应该是in fix alter,这个名称更更严谨一点,好,我写到这in fix就是中罪的意思。那么电力的时候呢,它跟原先这个唯一的区别是先把这个左边的搞定,再输出当前节点,再输右边,因此我也不重细节了,来,各位同学,我把这个先输出来。一定要有判断啊,同学们,如果你没有判断你是你会死的,很难看。因为他走到最后那个叶子节点。你下面没有指数了,再往下面一走,就控指针所向左边递归,输出左指数,然后输出什么呀,当前节点。
16:09
当前节点,当前节点完了过后再向右说输出,诶右指数这个怎么回事,右指数来各位同学我来给大家调一下。中区便利。我把这个先注销。然后呢,我复制一份叫中序遍历,看清楚了,中序遍历我调动方法要进行一个修改。叫invis。In。这么一出来是吧。哦,我这边还没掉,对同学们说的很正确,我这还没掉是吧,因为我这个地方还要调查一下,没错,因为我们还有一个中序便历写一下第。In fix,然后呢,Order。然后这边的代码呢,跟他应该是完全一样的。只是把后面这个改一下,把地方改了,把这把地方改成我们的infex order就可以了,然后呢,我在这个地方就可以掉了,同学们啊,常规的处理方法点in。
17:11
那么中序便利我们先不要去运行,我们来推一下。打开我们的这个Excel文件,我们看中序遍历,中序遍历的结果应该是怎样子的呢?来,首先是不是先把二改输出来,二完了过后是把一输出来了。啊,然后这边。该输出哪一个了?是不是该输出五了?五输出来了过后应该输出什么呢?三,然后再输出四,所以它的顺序应该是这样子的。啊,二一什么呀,五。接三四,那有些同学老师你这个前序中序会对有什么影响吗?这个很有影响,就是后边我们在用不同数的时候,你就要针对它的特性用不同的便利,不然这个结果是错的啊,那我们看看21534是不是跟我们想的一模一样,注意听讲。
18:08
那看屏幕。好,同学们,可以看到这个结果,我们想的是21354,完全正确。诶诶,刚刚好哪写错了。二。我看看啊215。21534我看哪里们咱们写的有问题啊,21534我们看哪里有问题。哪里写错了,咱们这儿。是不是我们来找一下。找到我们这一个infect。Infe,是不是我这有点有毛病吧,是不是我自己写的时候。乱写了一个就跑了呀,哎,所以说同学们要注意,因为我们复制粘贴这个是很容易出问题的啊,那我们重新把它改一下,所以说写的时候呢,一定要验证一下。有时候为了省事,你复制的时候就可能忽略了这些小细节,来,同学们,我们再来跑一下运行。
19:07
这样子应该没问题了。对21534对吧,完全的OK,好最后呢,我们再把这个后续遍历也给大家写出来,后续遍历我们仍然按照这个套路来写,找到我们的hero。好,我们来写个后续遍历。后续便利,那后续便利呢,我们就一般叫post。Order啊,他这个叫post order。那么我们一样的道理啊啊,后续边利它是先把左指数打出来。这次我们要小心点,改一下,马上就改。Post。然后呢,再输出左指数啊,先输出左指数,再输出右指数。把柚子树也输出来,柚子数不要忘了,也把这个改一下,哎,刚才我们就吃了亏了,Post。然后呢,再输出我们当前的这个节点,没问题吧,好的,这个这个就写完了,然后我们找到我们batter battery tree找到这边。
20:11
我们在这个better里面呢,我们写上这个后续便利。后续便利。啊,注意听讲啊,待会你就可能听不懂了,现在大家觉得很轻松对吧,Post。Order,走。然后呢,这个代码我就复制一份,同学们不写了,然后把这个地方改成点post order。好,同学们,我们找到我们主方法。我们再写一个后续遍历的代码。好,打开这个我们输出叫后续遍历。后续遍历呢,我们调用它的方法是点对不对,Post。Order没问题吧,我们先不要执行,我们先自己来判断一下后续变量的结果,是后续便利的结果,我们直接说结果了啊,首先它是二。
21:06
再输哪个?二五。姐,254该出事了吧?三。一。看到没有,所以每个都不一样,那这个将来对我们搜索检索也不一样啊,就是25431 25431,我们执行一下,25431执行,我们可以看到这个结果呢,跟我们想的应该是一样的,25431完全正确,好同学们,我们一个最简单的便利,咱们就OK了。最简单便利就OK了,我们把这个代码呢给大家板述一下,再接着讲下面的二叉树的什么呀,删除,还有它的检索等等。好,刚才呢,我们讲的这些内容,我们进行一个简单的板书。对,刚才我们讲了什么内容呢?诶,我们刚才讲的内容是这样子的,首先呢,给大家讲了一下二叉树的这个示意图里面包含的常用数的术语。
22:10
好,这是二叉树的示意图。二叉树的示意图,这个二叉树的示意图里边呢,我们针对这个图说了一下它的概念。把这个图呢,给大家拿过来对吧,这个图,然后他这边拥有的这些概念呢,我也写到这里来了,放这一共有11个概念。要做一个介绍啊,要要做一个,呃,说明11个。我这里标一个。符号。好,那么这个术语讲完了过后呢,我们又给大家讲了一下,呃,常见的这种数二叉树,完全二叉树,还有满二叉树,二叉树的基本概念有这里。暴力了。二叉数的概念啊,我们讲了这么几个,是有很多种对吧,有这么一些概念在里边,我把这个图就截过来了。
23:04
什么叫二叉树?这个都叫二叉树,这三种都是二叉树。好一。二叉树。给大家放到这,那二叉树你只要记住这一个就行了,每个节点最多只能有两个子节点的这种数就叫二叉树。对,至于他是不是,呃,至于他是不是,呃一刚好两个,这个无所谓啊,假设只有一个也可以,然后。这边呢,我们又说了。就是满二叉树是一个什么样的数,还讲了一个完全二叉树是什么样的数,好,我把这个呢也给同学们拿过来。好,这个是讲的。这个满二叉树。然后下面呢,我们说的是完全二叉树,还有一个示意图。把这个示意图呢给大家放过来。好,就是说的。这两种数对。
24:02
这两数,这两种数讲完了以后呢,我们就给大家举了一个例子来说了一下二叉树的变例。对吧,二叉树的便利,那二叉树的便利呢,我们要非常清晰知道,常见的便利方式一共有三种。有前、中、后三种便利方式。下面呢,我们就举了一个例子。我们举了一个什么例子呢?就是针对这个图啊,我们就是对把这个拉过来就可以了。对,这个前序后续便利一个说明啊对。各种各种便利方式的说明。对吧,我说了一下。前序后续是什么概念?那地方我们给它来一个小箭头。然后针对他呢,我们就做了一个实际的案例。这个便利的实际案例在哪里呢?就是这讲的。来看一个。针对他我们做了一个前后前续,中续后续的便利,那这个图我们就从这截了。
25:03
好,我们看一下。这是这个示意图。呃,然后呢,我们把代码也给大家拿过来,就是代码实现。那代码实现在哪里呢?就在刚才老师写的这个文件里边,我放到这里面去。好,同学们放好了。好,同学们,那关于二叉树的一个便利,我们就先说到这这段视频。
我来说两句