00:00
下面我们来对它进行一个测试。我们刚才讲过,你要做这个事情,先需要需要创建一棵二叉树,对不对,那你创建这个二叉树,你应该怎么去创建呢?各位朋友。大家想一想应该怎么创建,是不是应该这样子,先遛一棵这个二叉树出来。是这样子吧,同学们。Better,那么你现在一共有几个节点?大家看,目前我们需要一个、两个、三个、四个节点,好,我先创建起来,就是创建需要的节点。没问题吧,那就6HERO。No。那第一个我们编号为一,名字为宋江。没问题吧,同学们,我就给它分配一个变量,这个呢,我们叫LOAD1,简简单一点啊,就叫NO1。搞定,其他以此类推。NOTE2。
01:01
NOTE2NOTE3NOTE4,那NOTE2呢,我们。NOTE2这个人的名字是吴用。好无用,我们就按这个给的图式写好吧,这样好比较无用。NOTE3呢,是卢俊义。乐山卢俊义斗的是是林冲,这是卢俊义。卢俊义没问题。NOTE4是林冲。我把这写在这,叫林冲。林冲,好的喜欢,那么现在你有这个节点,他们之间还没有任何的关系,其实大家知道宋江这个是root节点。是不是可以直接写成root了?那么现在我们把这个,呃,按理说这个二叉树呢,应该是递归创建,但现在我为了测试呢,我先手动创建,我先说明一下啊说明。说明我们我们先手动创建该二叉树。
02:00
二叉数后边我们学习学习什么呢?学习递归。以递归的方式,递归的方式创建二叉树,明白我的意思吧,我们先把便利这块讲完。好,那现在呢,我们就挂root的点set,它的ne应该是谁呢?NO2。这句话代表什么意思?大家能看懂吗?Root这个节点。它的左边left呢,挂上了NO2,相当于说这条线就。形成了。因为我现在呢,是通过方法调用的,同学们呢,以前可能更熟悉的是这种写法,就是我以前也我我以前是这样写吗?root.left等于not一个意思,但现在不能用了,是因为我这个left做成私有的了。明白我的意思吧,说两种方法大家都要会明白,好,那现在root.set它的right是谁呢?应该是卢俊义三。
03:08
是这样子吧,同学们,那这样挂好了,过后是不是还有一个关系,就是卢俊义的下面呢?呃,右边有一个林冲,是这样子吧,啊来写到这一点。小这root点,诶在在这样那就不是root了,应该是load3.site它的right。右边的这个子节点是谁呢?漏是。好,此时此刻我们这个二叉树的关系就形成了,也就是说这三条线就挂好了,现在我们可以来测试。这是我们先来一把情绪便利。看看结果是什么前续。情绪便利,我们先分析一把应该输出什么。首先,同学们看。按照前序遍历的话呢,他应该是这样子的,先把宋江打出来。然后把左指数全部编辑成功,因此它应该是一,这个是一,这是二。
04:06
这篇做完了,过后呢,卢俊义。卢俊完了往卢俊义的左边,左边没有无法输出就输出四。就输出四,那也就是说这个顺序应该是什么呢?是一。第这这个前序遍利你发现没有,就是按这个顺序来的,1234来验证一把,由前序遍它的顺序是一。234我们运行一把,那运行这个结果呢,给我们想的,诶大家看啊,他这打了一个全序遍历,但是没有没有整,我们是还没掉哈,还没掉掉的时候就root点什么呢?哦,不是root点啊,应该是我们的better tree。大家看你现在有一个问题。还有一个问题我没没有解决,就是说你现在root呢,他们关系形成,但是你没有把这个root给到我们二叉树,是不是,所以我们还有一个动作是什么呢?By tree。
05:07
点set root,把谁给他,把root给他,这这样就形成了好,现在可以真实的谦虚便利,那这BY。干什么呢?OK,那就是pre order,是这样子吗?同学们来运行一把。看结果好,我们可以看到此时此刻出现了一个战役,出哪里出了问题,我们来调大家看,在129行,我们出现了一个问题。他说they是点post,你这少写个什么东西啊?大家看是不是这个地方你在调用的时候,你少写了left呀。OK,你把这个加上,因为我们刚开始的时候呢,你在写的时候你写错了。好,那接着我们继续再来试用一下,走起来。好朋友们,这次就没问题了,我们看现在前需便利,便利是2431,跟我们想的不一样。
06:07
跟我想的不一样,为什么不一样呢?我们来看。我们前序遍历,它的顺序是先把这一个。这个节点打开,我们看看这一模是写哦,这个怎么回事啊,掉错了,我怎么说的呢啊。好,调错了,那是pre order对,大家看一下运行好这个就没问题啊,1234。跟我们分析的是一样的,就前序便利是一样的,好,我们紧接着再来测试它的什么样。他的这一个。中序便利,那中序便利呢,我们仍然按照刚才这个套路来走,System走,那现在写啊叫中序便利,那中序便利我们玩一把binary tree。点什么呢?In fix order中序遍历的顺序,我们也来分析吧,应该是什么样子的?
07:01
首先中区变利呢,它先便利的是幼指数是这样子的吧。右指数好,这个它不会变利他先变你这儿。幼指数只有一个,所以说它第一个便利的是二。也就是说这个先搞定。这个完了过后呢,回到这边来。再把宋江打出来。为什么呢?因为柚子树已经编定完毕了,说宋江是第二。第二个出来的,这个做来过打卢俊义,但是卢俊义呢,他先编译卢俊义的。什么呀,柚子树,也就是说他这边完了过后到这儿来,到这儿来过后呢,先把卢俊义他先不输出,他先到。右边右边没有。右边没有,那就只能把卢俊说出来了。诺基说出来过后呢,再把四出零中出出来,那就是2134,看看是不是2134。好,我们输出来是213。是运行一把。好,我们可以看到。
08:00
2134正确,我们再来测试它的后续便利。后续便利,这个各种不同的便利方法后面都有用,同学们。便后续遍历,那后续遍历呢,我调用的方法就应该是post order,我们再来看后续遍历应该是什么顺序,来我们一起分析吧。后续便利呢,它是先便利。左边的再便利,右边的最后便利,中间的是这样子吧。所以说送下来了,他先不输出,他先把无用这柚子树处理完,柚子树没有吗。柚子树,呃,右子树只有一个节点,那二就输出来了,松江先不要动。因为他是后续编利,他紧接着找卢俊义,卢俊义呢,诶也是他有右边的,左右两边去处理啊,对不对,那到了卢俊义他先处理这个毒菌剂,右边的没有。紧接着处理卢俊义的右边的,诶林冲只有一个,林冲下面没有左右了,所以说林冲其实是。
09:01
第二个输出的。第二个输出的,然后再把卢俊义再输出。是不是因为你你这边输出完了,就就就输出他这个本身这个负节点嘛,好这个时候其实对于宋江来讲,他左右那边都便利完毕了,所再输出这个一,那顺序就应该是二。四。三一能看懂吗?就说这个才是后续便利。就是2431,我们来写,写出来验证一下。那这个是二。是。三一各位,我们运行之,我们可以看到这个结果呢,我们想的一样,2431完全的正确。完全正确,也就是说到此为止呢,我们这个。我们这一个前序中序后续遍历就测试完毕了,这里还有一个题。我们看这里面还有个题,那么这方呢,他有个要求,他说他说啊前按照前面这个图,我们给三号节点的左边再增加一个关胜,这个题呢,就是。
10:09
看大家是不是真的理解了前中后便利的这个规则,他说在上图三号节点卢俊义,卢俊义这个节点上增加一个左子节点,是五号关胜,然后问你前中后输出什么顺序,这个呢,就是考察你有没有听懂,来吧,我们给大家验证一把,打开这里,我们先建一个节点,这是第五一个节点是谁呀?关胜。走一个。关胜,那么关胜怎么挂到卢俊义的?右边呢,非常的简单,我们找到第三个节点。是这样子吧,我们把它挂起来,第三个节点。看清楚了S它的left几呢?五好同学们,这个就挂进去了。
11:01
好,那么现在前序便利应该是什么样子的同学们?好,我们来一起分析吧,啊,同学们注意听。现在的全学编利应该是这个样子,这个我我我我就我就先删掉了,好吧,这个我先删掉了,他全学遍利应该什么样子,来我们一起玩一把。首先呢,前序便利,这个是宋江先输出来,因为他先输出负节点,吴用没问杰,吴用下面没有了,然后再输出卢军一山,然后再输出左边的。这个附节点五,这是四,因此它顺序是12354,没问题吧,12354来验证一下。1235412354好同学们,为了不跟后面冲突呢,我先暂时的将后面两个便利方式。给它删掉好吧,注销掉运行值是不是123451354呢,12354跟我们分析的怎么样,完全一样,没问题吧,同学们好,现在呢,我打开我们这一个。
12:06
中序便利,我们又来分析一把,如果是中序便利,它应该输出什么呢?来动脑筋。首先中区变利呢,它先这个先不输出,先把右指数全部变利完毕,右指数便利到无用手只有一个说说二第一个输出。紧接着就是一没有问题吧,那么三呢,诶不能输出,因为三下面还有有指出呢,所以说这个五是第三个输出的。对不对,再输出三。最后再输出四,因此它是12534能理解。12534运行一把。这是12534动脑筋啊,同学们,现在呢,我们来运行看看中枢编利是不是125341,诶这个我看看是哪个地方分析错了啊,中序便历啊,中序便利啊。
13:02
中需便利怎么?哎,对不起啊,这我分析错了,我们重新来一下啊,中序便利。中序遍历,中序便历应该是它先不能输出,应该是先输出二,诶刚才是不是也是这样说的呀。12啊,12应中心面,那肯定是先输出这个。好,我看看啊,中序遍历是先把右边右边的全部遍历完,再输出自己那二应该是第一个呀,对呀,然后再输出。呃,这个一吗,是啊。然后在三三,但是三下面有吗?所以说应该是五啊没问题啊,五五再输出三呢。我在输出三过,我在输出四啊没问题啊,21534 21534没问题啊,怎么写的。212,嗨,自己自己糊涂了啊,本身分析的是正确的,但是呃,我写写错了,21534再来。21534正确的啊,正确的,刚才应该是我分析的,没没毛病,自己写错了,好重新来写。
14:07
后续遍历我们再来看一把,后续遍历呢,要一定记住它是先把左右两边。左指数和右指数全部编定完毕,再输出负节点,首先呢看一一先不会输出,因为他先把右边走完,右边只有一个搜索二。过来了,那么二完了过后呢。呃,宋江也不会输出。哦,他先要便利宋江的。这个右指数,右指数三呢,也不会先输出,因为卢俊义左边还有,所以他会先输出五号。没问题吧,五号输出完了过后呢,卢俊义也不会先输出,他要输出四号。四号输出来,完了过后再把卢俊义输出来。对,再把卢俊宇输出来,卢俊宇输出完了过后,相当于宋江的左右两边都完成了,再输出一号应该是2543125431啊,别写,别再写错了,二二。
15:04
5431没毛病吧,同学们,运行者。2543125431,正确的同学们,那到这里呢,我们就把我们这个二叉。二叉树的这个,嗯,一个前序中序便利的代码,就跟大家讲完了,大家看理不理解。应该也不是很难,对不对,应该也不是很难,就是你把这个理解了,应该就是很OK的很OK的,好,现在呢,我把刚才我们讲的这些内容呢,跟大家简单的板述一下来回到这里。呃,刚才我们讲的是什么内容呢,各位朋友。刚才我们嗯,讲了数的我看看。笔记写到哪了?好B应该是从这儿开始走,我们讲了二叉树的示意是树的示意图,通过这个数呢,我们把它的常用术语给各位朋友聊了一下,是这样子的吧,二道树的树的示意图。
16:01
那树的示意,诶竖的示意图呢,这就是他的一张图,有一个印象啊,同学们。那针对这张图呢,我们做了一些呃,术语的介绍,就是这块。我把它呢,直接给各位朋友放到。放到我们这个笔记来。插入一个小表格吧,好吧,这样好理解一下,那这里呢,我们分别提出了这样几个概念。就什么叫节点,什么叫做根节点,什么叫做这个叶子节点,什么叫做非叶子节点,非叶节点对不对,好这个呢,我就不再多说了,这块。这块说完了以后,这块概念说完了以后呢,我们给大家专门说了一下何为二叉树。是不是二叉树,是什么?因为刚才说的是树,现在说的是二叉树。走一个,那二叉树呢,我们首先说二叉树有很多种,对吧,比如说我们说的二叉树还有AV l树,有B数,有B加树,B心术等等。
17:03
那么二叉树其其实就是其中的一种而已,那么二叉树有什么特点呢?它分为左右。左左子节点和右子节点,而且大家看到最多只能有两个子节点。好,那么这儿呢,有一个示意图也跟同学们拿过来,我这里画了三个二叉图,二叉树的示意图放到我们的笔记中。是样子吧,同学们。好的,这是它的一个示意图,说完这个以后呢,各位朋友,我们是不是又接着讲了什么叫做满二叉树?这样子吧,这是我们的满二叉树,我就写到这儿了啊。呃,我们这标号多了一个,这个无所谓,满二叉数,满二叉树它的条件是什么,我这写的很清楚,就是所有的叶子节点。都在最后一层。啊,所有的业绩节点都在最后一个,而且要满足这个条件,什么条件呢?节点的总数是二的N次方减一。
18:04
这个就是买二叉树,那比如说我在这呢,给同学们画的这个就是,诶同学们看这个就是所谓的满二叉树。这个就是所谓的满二杀数。放到这儿。那么第五一点呢,我们又给他讲了,就是什么叫做完全二叉树这样子吧同学们,那么完全二叉树它的特点又是什么样子呢?我们来看一下,它是所有的叶子节点。都在最后一层,或者是注意听,或者是倒数第二层,但有个前提是,呃,最后一一层的业绩连在左边连续,倒数第二层在右边连续,我们称之为完全二叉树,比如说我们看到的这个图。就是。满二完全二叉组,但是我这里专门做了一个说明,大家看啊,如果我们把61这个节点删掉,那就不是了,因为你左边你你上面这一层业绩节点不再连续,是不是就是第倒数第二层的绩节点右边就不连续了。
19:07
那这样子呢,它就不再是一棵满二,不再是一棵完全二叉树了。好,各位同学,我把这个图给大家截到笔记中。好的,这是关于二叉树的概念,紧接着我们就说了,二叉树呢,我们先要学习它的便利。那么二叉树的便利有几种呢?各位同学来看一下。二套素的便利呢?我们分为前中后三种便利。是不是,那首先我们对前中后他的这几个便利的便利的概念做了一个介绍,就这写的。是不是这个这个意思啊。我写到这里来。是不是什么叫前续,什么叫中续,什么叫做后续,这里呢,我们有一有几个说明,看到没有,前续便利就是先输出负节点,再变利左指数和右指数。中虚变历是先遍历左指数,再输出负节点。
20:02
再便利幼子树。那么后续变定呢?反之最后这个小节就同学们怎么记,你只要看负节点输出顺序就确定了,负节点先输出就是前序副节点,第二输出就是中续副节点,最后输出就是后续。好,这就是他的一个概念,紧接着我们干什么呢?我们用代码给大家玩了一把,是不是我们用二叉树的便利,我们写了一个什么呢?应用实例是这样的吧,同学们。那我们便利实力是什么样呢?就是要求大家对这颗这个来进行便利,好我们就做了一个分析。是不是我们这做了一个示意图。然后呢,我们就详细的给各位同学说了,先去编辑的步骤中去后续编辑步骤这一个示意图,好这我写到这。啊,第一步就是就是实应用实例,应用应用实例的说明和思路。
21:00
是这样子吧,是吧,思路也给同学们分析了一把。好,这里呢,我们用一个小箭头了,只有。把这个图给大家拿过来,当把这个图做说完了以后,是不是我们就写代码了呀,是不是就代码实现了这个代码呢,稍微量大一点对不对,代码实现制。那在哪里呢,各位,就在我们的这个代码这个地方,这个里面的代码呢,有100多行,其实核心的代码并不多是吧,就是那个post order啊,In order啊这样的一个东西。实际上并不难,我们把它给同学们放在笔记中。好的同学们,那关于我们。一个比较,呃,刚开始讲的二叉树的前中后续便利,就给大家先聊到这,后面呢,我们再继续讲解二叉树的查找,删除这样相关的内容。
我来说两句