00:01
具体代码呢,我们来看一下,首先呢,我们先把这个二叉树创建起来,然后完成一个遍历。一个数组创建成一个对应的二叉排序数,但是这个数组也也有可能是你从那个控制台输进去的,也有可能是从文件读进来的,这个无所谓,你这个数组长什么样子也无所谓啊,我都能形成一个二叉排序组,我们把它创建起来,创建起来过后呢,我们再用中序变历这个二叉数,你就会发现中序变力得到的这个数呢,刚好。是一个有序的数组。比如数组为这个我们创建二叉树是这样子的,那现在我们就来写一下这个代码啊,这个代码呢,添加了整个这个思路是这样子的,我们先把这个思路给大家捋一捋,大致的思路这样子。就是我这里会有一个节点。你给我来一个节点,我先看当前节点,这个节点会不会空,如果你这个节点是空的,我就没法添加就走了。
01:00
好,然后呢,我这里有一个判断,如果你这个节点的值,就是你准备插入的这个节点值小于我当前这个值。说明我应该把你这个节点插入到我的左指数,这个能理解吧。因为你这个要操作的节点比我当前这个节点的值要小嘛。那我用左子数左指数插的时候呢,你要判断你这个当前节点左边是否为空,如果为空就直接插进去了,否则就递归。往里面添加右边一样的道理,代码非常简单,那同学们,我们来写一把。好,同学们,我们写一段代码,我们这个这个就叫这个名字啊,叫做二叉排序数,就叫binary sort tree。好吧,那当然,我写个DEMO有点出事嘛。好的,那现在我们把这个需求先拿过来,需求是这样子的。这个数组呢,我要用啊,把这个数组形成一个。
02:01
二叉排序数。这个速度你怎么放都行哈,怎么放都行,反正它都会形成一个二叉排序数,这个做成做成一个二叉排序数。排序数OK,那现在呢,我们把它先建一个节点,因为你到成都是节点嘛,所以说先定义。定义节点。定义这个节点,节点很好很好很好写,我们就叫node。No。Nod node。OK,这个load呢,我们在做的时候,你给我传一个值进来就可以了,就把你把你把这个值给我啊,给我一个值value。好。No就是T。啊,你给我一个值,然后这个值有有了过后呢,我们这边这边写一个吧,啊,比如说你这一个编号也行,叫编号也行,Load编号。就叫直接性啊,我们就写个VR。Va value。
03:02
呃,这边就干脆不写了,因为这边本身就是一个属性,对吧,到时间我们这这这个属性,这个属性要加一个VL是吧,如果我不改的话,就是VL要改的话写成Y,然后这个节点是不是还得有一个东西啊,左右两边是不是要有。对吧,要左边和右边,那现在呢,我们写一个叫做这个VAR,然后left。它的类型就是no。Nod初始化,给它一个空,别忘了VR,然后是right right呢也给它做一个节点类型no。还需要什么吗?好,暂时好像就不需要了,不需要了,有这个节点过后,下面呢,我们来先写一个添加的方法。添加的方法。OK,那添加的方法呢。是老规矩了,老规矩我们就这样写的,D你在这个地方做的时候,你把一个节点给我。
04:00
你给我一个节点,Node。你给我一个节点,好那。这个节点我首先要判断,如果你给的这个节点是个空的,那我就嗯,我就不能不能做这个处理,我就直接给你return。就是如果节点是空,就不做处理了。如果啊。如果节点为空,那就返回了。对吧,那下面的问题就来了,就说如果这个节点它不为空。就是它有具体的值。它有,它有这个距离值,我们。就是不是要进行这个比较。你把它放在哪个位置啊。是不是刚才我们在地方已经说过了,如果你这个值比它小怎么处理,比它大怎么处理,就是比你当前这个节点,因为你这个节点是要挂在当前这个节点下面的嘛。好,那现在我就做判断。我做判断啊,如果要加入的。要加入或者要插入的,插入的这个节点的值,它小于小于当前节点。
05:09
节点的值则则怎么呢?则可以处理,就进行这个处理了。如果就是你这个。这个no里面的这个value,它小于当前这个value,大家看这个能理解啊。这个很好理解,就是你这个加入这个节点的值,它小于当前这个节点值,那么当前这个节点要做判断呢,如果刚好你当前这个节点的它应该往左边跑了吗?这个节点应该是。就这样子啊,如果你当前这个节点的左边,它已经等于空了,说明什么问题?哦,说明它下面就可以直接挂它了,是不是就是它下面没有指指数了,这说明。哦,说明。
06:00
说明这个这个就可以加入了,这个时候啊,说明这个该节点,该节点下没有左指数能理解吧,或者没没有左左子节点。那就可以插入了,那就怎么插入呢?点left等于这个no。是不是这个道理,那当然还有一种可能性,就是人家人家不等于控制吧,那就是else了吧,是这意思吧,就else就说如果说你。你不等于空,你不等于空,我就递归。递归的进行这个这个这个添加地心I递归进行这个插入。啊,插入。那现在这个地方也很简单,就是你this left点,把这个节点往里面扔。但是它往这个进行递归,就这往下递归的时候,它到底把这个note挂在下面的节点的左还是右,这个不定对吧,因为它下面你就不好说了啊好这个就写完了,写完过后是不是它还有一种可能性啊,就是S。
07:02
这个我就不写了,就说他这个条件不满足,必然就是大于它嘛。为什么为什么说呢?因为这个note节点等于等于这个我们我们是在往里面添加是吧,我是判断它下一个节点,所以说else条件就可以了。OK,呃,那等于等于的话,我们就认为小于,还有一个条件,是不是就是大于等于,大于等于我都可以把它放在右指数,这个也不错,是不是也没什么大的问题,因为刚才我已经分析了,那下面呢就写这个条件。如果我就写一句话啊,因为现在大家能看懂,后边放久了大家看不懂了,写点注释,如果插入的极电子大于。大于或者等于。啊,不小于也行啊,叫不小于也行,叫不小于。不小于。当前节点值,那么我们同样有这个逻辑判断是吧?那一样,首先你判断你当前这个节点的右节点是否等于空。
08:03
如果它等于空,是不是就可以直接挂下去了?那就是this right等于什么呀,No?哎,当然这个这个地方就就就就可以了,然后S。要是要是要递归,递归的这个进行插入,那下面这边写一下,这边要改成right,别写错了。Right。好,我看这边。好再录制啊好,这个就是这个啪这个声音啊,没问题,这是向左右进行添加这个就可以了,可以过后你看这它也是个小圆圈递归的。那现在呢,我们这个节点它是属于一棵树的,对不对,所以说我们现在要写一棵,这棵叫做递归二要素,叫定义我们的二叉排序数。二排序数呢?我们取个名字叫class binary。Short。
09:00
跟我们刚才那个逻辑非常相同,我们也写一个root节点,因为不管是什么数都有一个根嘛,啊,你不管是二叉排序数还是普通的二叉树都有一个根,所以说root初始化呢,我们仍然是一个load load,大家给他一个no。好,那现在我也在这写一个函数叫艾,那同样你给我一个node节点,你给我no的节点。你给我一个漏节点呢,我进行这个处理对吧,那我就判断,如果你这个root等于空,说明什么问题,说明你当前还是一棵空树。是直接挂上就行了。这是一个空诉,我直接挂上。热点呃,就直接指向它就可以了,是不是直接指向这个load就完事,否则怎么办呢。是不是就用我们root点我们的爱的这个就行了。好代码就行了,这个添加就完事。那添加完事是不是为了证明我们这个添加对还是不对,我们是不是应该写一个便利方法。
10:02
遍历方法是不是前面我们已经学过了,哎,我们用哪个方法,大家觉得哪个方法能够刚好让它是个有序的呀,是是不是这个中序刚好是对的,你看中序它是。怎么是中序呢?应该是前序吧。是不是前序哦,中序说错了啊,中序中序是对的,中序就是一把这个先输出来吧,中序下一个说什么三五七九十十二对不对,这样就能够证明我们这个代码是正确的,好,我现在写一个中序遍历,中序便历我就不写了,因为前面我们写过,我粘贴复制过来,中序遍历在这都有来,同学们,我们在哪里面写的有在这。好,我就复制一份,同学们。在这边我找一下啊,中序遍历找这个结构。中旭便利这边有一个infect order。把这个拿过来啊,各位朋友复制一下,然后呢,切到我们的这个二叉排序数。
11:01
这边二次排序数。好,我在这呢,就把这个中区编底值写到这个noe里面去,对吧,这个大家应该能理解。好。把这。扔一份。一为什么错了?中序便利ne的这个节点,哦,对,我们这只有个只有一个值了,对不对,那就是这个值了value。好的,那下面呢,这个我们就不要了,诶就把这个值的,因为我这没有写别的东西,我这边应该写个Y6。是这意思吧,啊,下面没有改变的了,同样我们还需要在它的这个地方写一份,我我也不去写了啊。在我们这边还有一个,还有一个。诶,这个为什么出不来了,这边。好在这找到我们的batter tree切换到这边,它也有一个中序在这,诶在下面下面找。下面找一个就他。好,我把这个呢也复制到,复制到我们的这个二叉排序数里面去,那这个呢,就放在我们的这个二叉排序数这个类里边去,好写到这。
12:09
这个应该不需要什么变化了吧,好的同学们,现在我们就已经做好了,做好过后我们来测一下呗,我们来测一下,那这这就测试一下,测试一把。这是一把好,这个数组我已经有了。我就不去重写了啊,那就写个va等于它。然后呢,我们创建一棵,创建一棵这个二叉排序树。排序数啊,非常的简单,二大排序数呢,就是刚才我们写的battery battery sal tree VR。写进去。Very short by three,好,写完过后我们是不是用一个for循环往里面加就行了,哎,非常简单,For循环item走,然后我要遍利这个里面的所有数据,对不对?那very tree.i new一个node是不是?
13:06
把什么放进去啊,Item放进去就可以了,然后我们遍历一下。这颗电力这个二叉排序数是不是这样的意思啊,现在better tree,点我们的那个什么呀,Infe。好,现在就要看这个结果了,这个结果如果是顺序的就对了,那应该是一。三五。七。九,然后是十,12,好,同学们,我们预习一把。我们看这个结果我们想的一不一样呢,我们运行啊各位同学诶。准在哪去了,我们发现是不是跟我们一样的,一三五七九四十二,那有些同学,有些同学可能说老师,那假如我们这个再加一个可不可以一样的啊,说老师我加到最后呢,也是一样的,因为我们考虑到这些问题了,对不对,那你看你你即使加了一个二。
14:01
哎,你看一下它仍然是一个有序的,对不对。因为因为你在加到每个节点的时候,你都考虑这些了吗。考虑就行,因为你在这做判断了吗?你应该加哪个地方做判断了,好同学们,这一个叫做二叉排序数的创建和便利,我们就呃想到这儿,我们下面接着讲,我截段视频。
我来说两句