00:00
各位同学。我们把。二叉树的前序、中序后续便利给各位同学演示一下,打开我们的eclipse。打开eclipse,我们新建一个类。这个内容我们就叫binary binary tree。好吧,Binary tree。把主方法勾上,到现在呢,我们就开始来重建吧,首先是不是先创建节点?先创建这个per no的节点没问题吧?呃,我们写这个节吧,这两个节点大家都可以啊,两个节点,这个节点。那现在呢?我们写class hero node。Here no。那首先我们应该有哪些信息呢?Private首先有编号,是不是private,那我们每个英雄呢,有个名字。我们再来创建,因为刚才我们分析到就是这棵二叉树呢,它左右两边都有可能指向,因此呢,它应该有指向左边的这个索引和指向右边的索引,因此呢,我们应该写he no left,没问题吧,然后。
01:18
Private hero node node什么呢?Right?对,我们还需要什么呢?需要一个构造器,这个构造器呢,左右里面不需要给,因为默认为空,好我在这里写一下。这个默认默认no是可以的,因为当你刚创建的时候,不知道指向左边,呃左左侧节点和右节点是什么时候,这就是默认空没问题。好,这个地方我们就写完。那紧接着因为我这属性都是私有的,所以说我需要干什么呢?诶,我需要把他的这些方法给他。对吧,好生成就可以了。
02:01
那生成以后,节点咱们就完成了,那有了节点,因为节点待会儿我们要输出嘛,大家还看没看到,因为待会儿我们要输出当前节点的内容,因此呢,这里我们直接重写,突出对方法。To string方法,来,我们写一个吧,托斯string方法。做方法呢,我们把这些都勾上,但是左右两边咱们就不要打了,因为你左右两边一打的话,左边它继续往下递归去找就麻烦了,所以说我们就不要打左右子节点,这就拿到了para load的编号和它的什么呀,和他的名字就OK,好,这是节点咱们就写完,紧接着下面呢,我们来写什么呀。写这个节点的一些方法。那么这个节点有哪些方法呢?同学们,首先我们先编写它的前序,便利的方法。情绪便利。便利的方法。再编写后续中序,按顺序来啊中序。
03:01
便利。对不对,然后呢,再是后续便利,咱们一次把它搞定,后续便利。那既然是前序编利的方法,我们就开始这样写就可以了,Public void前序变成叫pre order。可以吧?然后怎么做呢?刚才我们讲过前序便利的时候呢,它是先输出当前节点。当前节点,再判断左指节点为不为空,如果不为空,递归前续变利,右子节点不为空,递归前续便利,是这样子的吧,所以说我们先来走一把,那就先输出对,先输出当前这个节点。当然有同学说,老师当前这个节点你为不会,为什么不去判断为被空呢?废话,你都进来了,他怎么可能还为空呢,对不对,进都进来了吗?好,所以说你这直接输入this就可以了。这个就是所说的先输出什么呢?负节点。副局。
04:01
互节点,诶这个节啊,咱们还是用这个节点比这个好好一点,那然后呢,我们就来判断,像什么呢?递归向左指数,因为左子节点下面有可能是一个数嘛,所以说我这写的是左指数没有问题,左指数递归呃那个前序。序编历,那你这样首先要判断它左边还有没有是不是,首先判断如果this是点left,它不等于空,在不等于空的情况下,我们再去向左指数变利是不是这样写的,那就是this.left点什么呀?Order?魅力吧。那如果这个做完了以后,我们继续。看,因为他把左边递归完了,过后又回到了。当前这个节点,是不是因为它向左走完了,过后他不是又递归它,它每一层的站就慢慢返回来了吗?对吧,反过来说说我们这儿还要做一个判断。
05:00
递归向右指数。指数干什么呀,情绪便利。没问题吧,那就是加一个判断,Z是点left right了,Right,如果它右边这个数呢,不等于空,我们Z是点right.order就写完了。这是前序,那中序是不是非常好写了?Public void中序我们用的这个单词呢,是in fit啊,有些喜欢叫mid都可以,我这用的in fix,那么同样是alder,对不对?顺序要发生变化,首先干什么先?递归,递归向哪里呢?向左指数左子数。这个中续便利,中续便利。中序遍历没问题吧?那当然你要判断咯,你不判断是要出问题的,所以说先left是不是?如果left不等于空,我们就向中续走。
06:08
是这样子的吧,This left.in fix order,然后输出什么呢?输出当前节点,也就是我们说的负节点。不节点。嗯,很很讨厌这个啊,负节点。对不对,那就输出来了system。哦。怎么说呢,非常简单直接咱们就把它打一下就可以了。对不大,就是刚才我们这样写的,就是认识。是不是啊,当然了,要递归向什么呢?向右指数,右指数中续便利。中序遍历,那中序遍历是不是也也要判断一下了?This是点right,如果它不等于空,我们才可以中序遍历,那就是this right.in fix order。
07:03
好,这是这边,那后续遍历是不是也是一样的道理啊,写上吧,后续遍历public avoid post。Order。代码呢,跟刚才其实是非常一样的,那我就开始写了,那就是直接写啊,Z是点它的left,如果不等于空,是不是我就。后续便利。递归的,然后呢,如果它的右子数right不等于空怎么办?我们向右边变利right.post order,那然后我们再输出当前这个节点也是负节点。This,代码就写完了。好,这是我们写的前序,中序和后序,那么整个这一棵这是是节点而已,是不是我们还没写竖啊?那么现在我们开始编写什么呢?创建啊,就是定义吧,定义一个binary tree,这个数就是我们说的二叉树。
08:09
二叉树,那么二叉树长什么样子呢?首先。各位,我们有一个binary tree这样子吧,那二叉树最重要的是不是就是有这个根节点就可以了,你只要把这个根节点给我,那么我就可以完成这个便利是意思吧,所以说我先要有一个根节点,这个根节点呢,我们就叫private hero node root。好的,那你给我什么呀,给我一个set方法就行了,你给我SET1把。你进来过后,你把根节点给我,根节点给我,我就可以完成相应的操作好,真正的这个便利工作呢,其实是由这个二叉树来调的,只是黑load呢,他提供真正便利的这个方案,从这呢,我们开始写前序便利。
09:01
呃,大家知道我在说什么啊,前序便利,也就是说前序便利的。呃,出发的这个位置其实是用根节点的,因此呢,我在这呢,呃,在这里面去调我们hero load写的这些个方法能理解吧。啊,这点大家想一想啊,就有点类似于我们前面讲的哈希表,那个哈希表是不是,呃,我们是从哈希table里面去调,呃,调我们对应的那一个链表的方法是不是一样的啊。好,那现在开始写了,那我这写一个public void。那这个就比较简单了,我怎么写呢?如果this.root它不等于空。因为它不等于空,我才开始能够进行情绪便利嘛,那我怎么便利呢?this.root.order就完事了,大家有没有发现,当我这样调的时候prior order时候,这个prior order传进来它这个this。
10:03
这个认识是不是第一次,第一次传进的这个认识就是我们的root呀。能看懂吗?因为你我们前面学Java基础的知道谁调用这个this就指向谁,有是调进去第一次调的时候,这个play order里面那个认就是root。那如果你不,如果你不为空,可以打印出一句话,说当前二叉树为空,无法遍利,是不是这样子,可以提示一句话,同学们写句话嘛,说二叉二叉数为空,怎么样,无法遍利。好,这个就写完了,那中序便利实际上是一个意思,中序便利,那中序便利呢,我们写public void。VO怎么写啊?In fix order是吧?那我就写了,如果this.route它不等于空。它不等于空,如果它不等于空的话呢,我们就去调用它的中序遍历方法,否则我们仍然提出提示刚才那句话。
11:07
就是如果你root等于空,那就别玩了,下面呢,再是我们的后续遍历,后续遍历一样的道理。Public。Avoid the post order。是这样子的吧,同学们,Post order那就写了啊,如果this.route它不等于空,它不等于空的情况下,我们就进行什么呀,后续遍历post order,否则我们也提示这样一句话就完事了。好,这是我们的。呃,就是我们所说的前续便利和中续便利,后续便利的一系列的方法,我们就写完了。我们就写完了,好,那创建完了过程,待会我们就写一段代码来进行。对这个二叉树的一个测试。
12:00
测试的代码我们放在下一个视频为大家讲解。
我来说两句