00:00
各位,我们用我们呃一个数组,我们把一个数组哈,把一个数组创建成对应的二叉排序树,然后呢,我们用中序便利这棵二叉排序树,看看情况是什么样子的,好吧,啊,现在呢,我们就直接对这个数组进行操作了,那一边讲呢,一边给大家分析事物,这个比较简单,比前面我们学习的赫夫曼数和赫夫曼编码要简单很多,所以说这个地方呢,我们就直接上代码了,一边讲代码一边给大家分析,打开我们的eclipse,那现在呢,我新建一个包,为什么我不放在tree下面呢?因为有些节点的名字相同。我放在这大家,呃,造成这个节点冲突,所以说我新建一个包,听清楚了,那首先呢,我们建一个包,这个包呢,我们就叫做。啊,叫做二叉排序数B。好吧。OK,那现在我们就在这写代码了。写一个类,这个类我们就叫binary binary2叉,Short tree。
01:04
DEMOOK,没问题吧,DEMO,那把这个主方法勾上,嗯,各位同学跟上我的思路,首先呢,我们先把这个节点建起来,是不是同学们class有个load。好,这个漏呢,它应该有有这么几个信息,首先呢。呃,我想想应该有哪些啊。呃,有这样子,首先我们把它的值写出来,它有一个int value。对吧,Int value。呃,然后还有什么呢?同学们想,除了有inter过后呢,我们应该还有一些信息,比如说它的左子节点或它的右子节点,这些都应该有我写上。Left。初始化为空。Right,那么这边诶。这个方法写反了,怎么会写成这样子,No?Load这边有个load right。
02:02
那么这边呢,我们给他一个构造器。给他一个构造器,好,这边构造器咱们写一个。这样隔到七就行了。left和right呢,不用给。是吧,这是个构造器。那拿到这个歌期过后呢,我们开始写它的相应的方法,那大家想他有哪些方法需要同学们去写呢?第一个就是我们要写一个添加的方法,是不是往这里面添加值嘛,所以说添加添加节点。添加节点的方法。添加节点的方法。那开始写这个代码了,那就是public。Public,然后void ad,你给我一个节点,你给我一个节点,然后呢,我就开始按照二叉排序数的方式来添加。到时我们递归添加肯定是递归的啊,递归的形式。
03:01
添加节点。啊,注意需要满足满足二叉排序数。二叉排序,排序数的要求很简单,我写写就可以了。呃,第一个呢,首先我们就判断,如果这个node它等于空,那没办法玩了,直接。Return就可以了,那如果它不等于空,咱们怎么判断呢?OK,就要判断,判断什么呢,传入的。传入的这个节点的值。啊是和什么呢,和我们当前他这个传入这个节点的值干什么呀,和当前。这个。指数当应该是,我看看应该怎么比较。你现在这个节点要加到我们这地方来,和当前指数的什么呢,根节点。根节点的值的关系。
04:03
那我就直接写了,同学们看啊,如果说如果说你这个no.Y6它小小于我们z.Y6,就是因为你在加的时候呢,其实最终。最终我可能是加到一个树上的,对吧,你这个节点加到我一个树,那我要给你找一个位置,所以说这个Z呢,就等价于我们当前这颗当前这个指数的根节点。是不是,那如果说你这个节点小于我,小于我,那怎么办呢?我们就这样写,就要判断了,如果当前这个节点left。它呢,等于空。什么意思?我做一个注释。就是。如果当前节点。左指数或者左子节点吧,左子节点为空,那这个时候不用犹豫,直接把它挂到下面就可以了。
05:01
挂在我们这个月,把这个节点挂在我们的组织节点就完事了。是不是代码就写完了,好,如果你这个左边它不为空。怎么办呢?同学们,如果左边不为空,我们就Z是点left.i load就递归的向左边去进行这个添加。这句话看看能不能理解递归,递归的向左指数。添加。OK。因为你你现在没有找到这个位置,那还得往下看它的左子节点,跟你这这个要新加的节点的关系对不对。那又是跟下面这个左子节点是大还是小啊,又得走。好,这是第一个层面的关系,那还有一种情况,各位同学,还有一个情况是什么呢?朋友们就说else,如果你这个node value,它大于等于this value。要漏点value大于等于,那这个时候呢,我们应该干什么呢?各位,那就应该这样做了,如果也也要判断this.right等于空。
06:09
如果如果你这个条件是这样子的,就是。呃,怎么说呢,就是你新的这个节点,节点的值大于我当前这个节点值,就是添加的节点的值大于。大于什么呢?大于当前。当前。节点的值。节点的注意啊,你当前这个节点其实就等价于当前这个指数的根节点了。是吧,因为你你你有可能传进来这个漏,它直接就是我们这棵树的根基点嘛,这是完全有可能的。好,那如果这样满足的话呢,我们又得判断你。这个节点的右边是不是为空,因为我要准备把这个节点添加到我这个当前节点的右边。
07:00
但是你右右指数到底是空还是不为空呢?也不一样,如果你的右边为空,好,那就直接挂到我的右子节点,是不是这个大家看能不能理解,直接挂到我的右子节点。否则怎么办呢,否则我就递归的。递归的像。向哪个方向呢?向右指数。添加。因为你右指数下面还得看右指数跟你什么关系是不是,所以说这个时候就是this.right.i什么呢?Load。这个代码就写完了,大家看能不能理解啊,一个IFS就完事了。应该不是很难,对不对,好,这个爱的方法就写完了,写完以后。写完以后呢,呃,我们为了将来测试比较好测试,他这不是有要求吗?还要用中序便利二叉书,那我把中序便利方法也顺带给他写了就行了,好吧,所以前面我们写了好多遍了,中序遍历我就快速的给各位朋友再写一遍,Void in fix什么啊,Order。
08:10
那order我们怎么去玩的呀,是不是先我就快速写,我就不判断我我就不说那么多注释了啊,如果left不等于空。如果它的左左指数不等于空,我们就zz.left.in fix order是这样子吧,然后输出当前这个节点。是吧,那就是this。那么紧接着呢,如果它的右指数对它的resting right,这个不等于空。我们怎么办啊,同学们,我们向右进行这个D,这个中区编地点什么infe order就写完了,大家看到这边有一个输出,所以说我我我把这个凹,把这个节点的这个信息呢,也给大家输出来就可以了,来走一个。对,走一个就可以了,那这边呢,我们。
09:00
把它的值打出来就行哈,把值打出来就行了,大家看到就就OK好,也就是现在呢,我们添加和这一个便利就写完了,下面呢,我们把这棵树写出来。这个是节点。这个是创建这个节点。创建load节点。没问题吧,现在呢,我们要创建,创建什么呢?创建这棵二叉排序树。二叉排序数二叉排序数名字我们就这样取了,Class binary binary什么呢?Short tree。各位同学,这棵树呢,肯定有个根界点,所以说我们先把这个根节点给它整出来,我们叫private no root,没问题吧?好,现在呢,我们写上这个添加方法,添加节点的方法,快速走一下public void。什么呀,爱你给我一个节点,你给我一个节点,我就往里面加。
10:01
对不对,那首先我们我们先来,诶这个地方你给我一个节点。好,这个节点呢,就是你的这个node。这个node。好,现在我判断一下,如果说我当前这个root这个节点呢,它是等于空的,代表什么意思,就是现在你这个节点一个都没有是吧,现在现在你在添加的时候。这这这还是个空数呢,如果是空数,我们直接把这个note挂上去就行了,这样子啊,如果root为空。为空,则直接放到。直接让什么呢?直接让root指向这个node就行,完了,如果它不为空怎么办呢?好,不为空的就好办了,点ADD把我们这个节点。加进去,那加的时候呢,他是不是会掉,我们刚才写这个方法,是不是就开始递归完成这个事情了,是不是同学们好,然后呢,我们再写一个便利方法。
11:01
便利,呃,但是中区便利了。中变中学变量,我们一一并把它写一下,Public avoid什么呀,Infe order。是这样子吧,同学们,那order时候也很简单,如果这个root它不等于空,我们才进行这个中序遍历,是不是root点我们的一个infe order。大家看我这边有一种有没有做判断,如果都不等于空,我才去做这个事情的,否则我们直接打印,一句话说当前这颗二叉排序是空的,无法编译。就写这句话,二叉,二叉排序数为空,不能便利。不能编译代码就写完了,各位同学我们测一下。我们测一下,看看这个行不行呢,首先呢,我把这个数组搞定,这个数组的数据是刚才人家已经指定好的,就是这七个数。对不对,是七个数吧,放这来。
12:01
那放出来以后呢,我们六一个二叉排序数的这个对象。非常简单搞定,那紧接着呢,我们要开始加节点,加节点的时候呢,我用一个for循环把它搞定就行了,For循环。就循环的。循环。循环。循环的添加节点到哪里呢?到这个二叉排序数。二叉排序数就完了,那就不循环了,按ti等于零,I小于r.NI加加。对不对,那怎么加呢。标点六一个node,因为你每次传进来no的值它是不一样的,怎么写呢?A,哎,大家看清楚没有。好,这个就加完了,加完过后呢,我们用中序便利一把便利二叉排叙述。
13:02
好不好便利呢?好便利,Barry。点我们的这一个,呃,Infe order。那同学们,我们我们来测一下吧,这叫中序遍历二叉排序数。那如果不出什么问题,我们想一想,它输,它输出的这个内容应该是什么样子的,我们来看一下。根据我们中旭便利的这个特点,我们来推推。他怎么走呢?他是先把幼指数全部便利完毕才做这个事情好。他往右走。哎,这个不能输出,这个也不能输出好一的时候呢,又指数没有了,所以说他先输出一一输出完了过后。是不是输出这个它的负极点就是三。三输出完了过后,输出它的左左子节点是五。五输出完了过后应该。
14:01
这边七这个右指数就输出完了,应该输七。七输出完了以后呢,就应该往下走,80还不会输出,因为十下面还有它的右右子节点还没到头呢,输出九,九输出完了过后,上上头十这个节点的右右边已经编辑完了,输出十,十输出完了过后呢,输出十的。这右,嗯,刚才是刚才说的左啊,这个是右,右是12,因此它的顺序就应该刚好是个有序的,就是一三五七九十,12,也就是说刚好按照中序变历,如果我们对一个二叉排序数进行中序变历,它刚好是一个升序。大家看清楚没有,刚好是一个顺序。就是升序排列的,那同学们看,如果我们运行过后呢,是一个升序的,说明我们就正确了,是一。三。五。七。对不对,1357。九。九好。
15:01
十。十二一共几个数呢?一共七个数,1234567。啊一三五七九十十二看看对不对啊,七三有了十有了12有了五有了一有了九有了,好,那就应该是这样一个顺序,我们运行值。好,我们运行一般,我们发现的确跟我们想的一样,是一三五七九十十二正确,好同学们,那关于我们第一个就是关于二叉排序数的创建和便利呢,我们就说到这里,大家看能不能理解。好的,那关于二叉排序数创建和便利,就先给同学们讲解到这里。
我来说两句