00:00
好,现在呢,我们来看下一个关节,下面叫顺序存储二叉树,这个是为我们讲解。这个二叉搜索术做铺垫了。我们先来看顺序存储二叉树,大家有没有发现我们讲到现在。没有把这个数和数组关联起来,也就是说你你在你们的现在脑海里面,你们认为数是数。数组是数组,但实际上我们要非常清楚的知道,从数据存储来看数组的存储方式。和数的存储方式,它是可以相互转换的。而且在我们。这个开发中也经常做这样的工作。即数组可以转成数,数也可以转成数组。那么我们来看右边的一个示意图。我们看右边一个示意图,好,这个示意图呢,这放到这,大家可能一下看不太清楚,我现场给大家再画一下啊,画一下我们做一个比对,比如说现在呢,我有一棵二叉树。
01:05
我有一棵二叉树,长得是这样子的,这是第一个节点,这是第二个节点。好,这是第三个节点。第四个,第五个,第六个,第七个,好,我在这分别的给大家画下。现在这个节点,第一个节点是值为一,第二个节点为二。第二个节点为二,第三个节点为三。第四个节点为四,哦,我们假设是这样子放的啊,刚好是按这个顺序来的我。下面这个节点16。最后这个节点呢,是七。好,七。好,同学们,它的这个二叉树长什么样子呢?它用这样关联的。这个事情他。这个二下面呢,有两个子节点。同样一号下面有一个三,三号下边呢有六和七。
02:00
好,同学们看,这显然是一个二杀术。这个没有问题,就是这个左边的。左边的这个二叉树,我们。我们也可以也可以。也可以。保存成或者以以什么呢?以这个数组的方式。数组的方式来存储。来存储。那么如果说左边这个二叉树,我们按照按照这个数组方式来存储,它应该怎么存呢?好,我们可以这样存。数组的方式来存的话。我们可以这样存。第一个。我写一。第二个啊,第一个1234。五六。五六还有个七。还有个七,那么我们来看看,诶还有七,我们看看这样存储其实就是顺序存储了。顺序存储,那我们现在要找到一个什么东西呢?找到它们的规律就说。
03:05
将来我们数组和这个数它要相互转换的一个规律,对我对于我们来说特别的重要,我们来看一下啊,同学们。它们之间呢,是可以相互转换的,我们来找它的规律。它的规律是什么样子的呢?我们看第一个。假如看啊,你这个一放到这儿是零,那也就是说这个地方如果按照它速度来说,它的它是第零个元素。你看嘛,的确是第一个元素就下标为零嘛,那同样道理,这边呢,是它的第一个元素。好,第一个元素这边二,按照我们刚才存储方式,这个这个三是。编号为二的。就是在数组里面是二的,其他以此类推。那么待会儿我们就要看规律了啊,我我这个一定要写一下。不画,大家到时间不知道我在说什么好,我把这个写成三。
04:02
这是第三个元素。然后这是第四个元素。这是第四个元素对应数组里面的第四个,呃呃,其实是数组里面第五个元素,只是下标为四。好,后面这两个。对,这个是下标为五。这个是下标为六。那有时候你你你讲这个有什么用呢,待会特别有用啊,大家不要着急,肯定有用的,不然我不讲啊,你看现在呢,如果按照这个标号来说,这个是。对应我们数组里面下标为零的,这个是对应下标为一的,为二的,为三的,为四的,为五的,为六的,那第六个的确就七,好,现在我们发现它有什么规律呢?我们看看它的第一个规律。我们现在要找第一个规律。找一个什么规律呢,大家看我这里。靠这里。看这里啊,诶这个地方,刚才我们把这个规律拿出来看一下,就这。
05:01
就是看这里啊,第N个元素。我们把这个拿出来规律于第N个元素的左子节点为。第几个呢?大家看看这里,比如说我第零个元素在这里面,第零个元素它对应的左子节点是数组里面的第几个元素呢?第一个元素。啊,下边为一啊,这个看这个是一,因为是二乘以。二乘以零加一等于一,你看这个关系就出来,就说第N个元素。第N个元素。它的左子节点这个元素对应的下标为一,没问题,我们再来验证一下。这个元素。第二个就是说这个下标为二的这个元素对应的右侧节点呢,是什么呢?来看第二个。再看第二个规律。这个大家大家可能现在还不知道老师为什么要写这个啊,因为待会我要遍历这个数的,用数组的方式来遍历的时候,这个就关,这个就很重要了,第N个元素的右子节点。
06:09
右子节点,比如说这个二。这这个三它对应的下标为二,那么它对应的这个右子节点在数组里面的下标是几呢?十六六就应该是。这个加二,你看我们来看看是不是啊,假设它对应的下标为二。它的这个右子节点对应的下标应该是几呢?就是二乘以二再乘加二等于几呢?等于六。但这个你看清楚,其实就是就是二乘以N加一,也可以这样理解,就是二乘以N加一,但是我这样写主要是主要是就是看起来更更直观一点。好,我们再来看第三个规律。现在第三个规律我们要找到什么呢?就是某一个节点,它的负节点。它的负节点的这个下标是什么,我们再来看第下一个规律,就是看这里。
07:05
第N个元素的负节点,为什么呢?第N个元素的负节点为N减一除以二。那么我们看看,比如说这个。下标为六的。为六的这个元素。他的。负节点是二,我们看是不是二啊,它是六。减去一个一。六减去一个一,除以一个二啊除以一个二。那理论上说应该等于2.5,但是它取整就变成二了,那再看这个,这个呢也是一样,你看如果是。下标为五的这个节点,它对应的。负节点的下标为二呢,也是为二,就是五减一。五减一等于四,四除以二还是等于二好,这这个关系大家记住了啊,记住了,为什么要记住这个东西呢?因为待会儿我如果要去把一个数组啊,把一个数组当做二叉树,或者把一个二叉树当做数组来进行编译的话,这个关系。
08:11
它就很重要了,好同学们关系我们已经已经找到了,就是他们之间确实可以通过这种这种关系来来找,比如说一,我要找一这个一。它对应的左,它在这假设,假设一个数字这样存的,我们把把它看成一个数的话,那这个一就是我这样我这样画个图啊,那这个一它对应的这个左子节点和右子节点是哪一个呢?你就查吗。一它的下标为零,它对应的着子节点就应该是二二乘以零加一,那就是它的着子节点就是这个家伙。它的右子节点呢,就是这个家伙,你看这个就能找得到,反过来我们假设要找这个山。对应的。这个三对应的这个着值节点呢,那它下标为二,那就是二。
09:03
二乘以二加一,它的着子节点就应该是五,那的确就是五,哎,不,不是五。卓子节点是几呀?下标是我那左支是16是不是啊,这就对了。16嘛。哎,我们再来看一下,你看假设我们要找这个三,这个三对应的着止节点是谁呀?是不是它的下标现在是二啊二二,它的左止节点是二乘以二。加一加一是不是等于五吗?五是不是等于六吗?是的啊,没,没有出错吧。1234564啊没错,那么大家好像有点疑惑是吧?没问题,好这样子的我们就可以这样去便利了,而且我在这说清楚啊,顺序二叉树呢,通常只考虑完全二叉树,就说一般我们这样去做呢,一般是把它当成完全二叉树来对待的。
10:02
它一一一定是呃连起来的,如果你中间有跳,那就不行了。你跳了一个,那那就不行,好同学们你跳的话,那就因为你你这个数组在存的时候,中间要有要有空的,那就浪费空间了,所以说在这种情况下呢,一般来讲,我们考虑的是完全二叉树。好了,同学们,那有了这个规律过后,我们现在写一段代码。我们准备写一段代码干什么呢?给你一个数组是123456,要求以二叉数的前序遍历方式来便利我们这个数组,注意啊,我是要求以前序变历来便利这个,那么如果是按前序变历的话呢,它的顺序它就应该是12456。1245367,为什么呢?大家看,因为你把它当做一个二叉树,而且你以前序便利来来对待的话,那就相当于。对,这棵树。进行前序遍历,那么我们看看对这个数进行前序变利,这个结果是什么样子的呢?
11:07
啊,是不是就应该是谦虚啊?谦虚。前序变利就应该是一嘛,然后是几啊二然后是什么。然后是什么呀,是。五然后呢,三。六。七就跟我这说的是一样的,1245367,我们现在来变一下啊,我们看看能不能把这个东西。遍历成功哦,我们来把它遍历起来一下,好同学们,现在呢,我们来走一下这个代码。我们新建一新建一个类了,现在不能在这儿再写了啊,我们切到这个工程,我们新建一科。二叉树。好,这个树呢,我们叫做a tree,就是把一个数组啊,当作一棵树来对待的。怎么去做?Tree。OKDEMO。
12:00
我们来写一段代码。那首先呢?我在这里先把那个数组拿过来,这个数组我已经有了,我就用它。我也不用别的了。好,VL。在于他。好写好了,写好了过后,现在我们写一个啊,写一个方法。哦,我们就写一个,写一个方法也可以,或者是我看我这是写个方法啊,我们这写一个类,或者写一个方法,我们就写一个类型啊,叫origin train。开始了,那就写。Or?那就写class。然后呢,在这里我接收一个数组,就你把这个数组给我。我就处理那这个数组的话呢,我就写个这样的东西。AV。然后。In,那大家看到啊,我这样写了过后,大家知道这个就变成了它的一个只读属性,这里面我们写成直接写int类型。
13:05
好可以了啊,可以可以,那待会这个数字我怎么去给它传进来,就这样传就传,现在我们写一个写一个方法。Pre order。写到这地方来,呃,那我们在pre order进行这个前序遍历的时候。我们是不是应该给他指定一个,你从哪里开始便利呀?所以说这边应该有个索引。应该有个索引,当然这个索引应该是零,但是你你在传的时候要反复的传嘛,所以说我们先把当前这个打出来,首先我们判断,如果你这个二。它等于空啊,它如果等于空。或者说,或者说你这个点认识它等于零,那当然这个就意味着你给我传进来的这个数组啊,就是你给我传这个数组,我无法处理。
14:01
因为你这个是没有东西的嘛,那就直接写数组为空,无法遍历。I数组为空。哦,不能变利。啊,不能这个,呃,按二叉树便利了,按照。按照。二叉树。二叉树便利。啊,情绪便利。好,如果如果说这个没有问题的话呢。我们就把这个当前这个,因为因为你前序编辑大家都知道是不是先把自己打出来呀。哎,所以说我现在就输出这个东西了。Print,我把这个输出来输出来的当然很简单,我就直接写个呃,把这个把它下标带进去就可以了。没问题,现在呢,按照前序遍历来说,应该是向先把自己说出来,过后向左。向左。哎,向左递归。递归便利。那向左递轨变地的时候呢,你要做一个判断,因为你想做向左地轨变地就是向左地这个标就是要找它的。
15:08
左边的那个节点是不是,那所以说它左边节点是谁呢?是不是就是这个呀,就是index。呃,然后要乘以一个二加一,是不是这个这个节点。就是。你这个index的左左节点呢。好。这个节点按理说你可以,你可以这样写。你你应该怎么写,这个是你逐渐你首先要考虑一个这个东西有没有越界。所以说你先把它括起来。你括起来过后呢,你要保证它没有超过,就说它还小于我们这个点。但,但鱼不行哦。有人说等等于行吗?等于不就那就那可能就接了,这是小于啊,如果它满足这个条件,是不是我们就可以order。
16:02
然后把这个音,把这个字给它放进去就可以了。是不是这样子就完成了向左边递归的一个过程?那如果说如果说这边左边做完了过后呢,我们还要向右边。向右递归,便利。向右递归变利,向右递归变利的话呢,这个逻辑跟刚才是非常相似的,只是把这个加二。对吧,这边呢,也改成这个二就可以了。好这样子经过一番一般这个便利,那这个这个结果最后就按照我们那个输出来了。好,最后我们来调一下。掉的时候呢,我们可以样写啊六一个。脆,然后把这个耳放进去。返回一个数组,数组这样的一呃数组对应的一个一一把一个数组当成一个数这样的一个对象,然后呢,我们调的时候这样调or。给他点我们的ordering。
17:01
但这样子呢,传的时候写一个零感觉很怪,所以一般的人呢,会把这个方法进行一个重载。因为我重改的话,把这个零写在里面,你就不需要再传参数了,就因为你反正遍历是要把它编历完嘛,所以干脆呢,我们对什么呢,为了方便对我们这个pre order。进行一个什么呀,进行一个重载。那重载我就这样写了啊叫。Order,我里面不不填这个参数。不填这个参数,然后呢,我在这直接调用我们z.play out,把这个零写进去。啊,这样子,我在这调的时候就直接。不要这个方法,这样看起来就更轻,就更舒服一点。更舒服一点,就相当我重载一下,就说我要前去便利,我写个零,感觉好怪啊,是吧,因为你前去便利肯定都是从零走的嘛。好,这边就是前序便利我们的数组,那这个数组出来这个结果同学们刚才我们已经分析过了,这个结果呢,就必须是这样一个结果。
18:06
如果不是,那说明我们这个就写错了,来,同学们,我们跑一下。我运行了啊,同学们走,让一下。OK。那么当我们乱完了过后,我们发现这个结果对吧。1245367正确的。那也就是说,如果我们将来要把一个数组当做一个数来进行遍历,这个也是可以的。那有些同学老师这样做有什么好处吗?就可以用到我们一些优化的东西了,因为你可以当当树来用了吧。我既然可以当树,我就可以当树,我就可以把那个树主当成一个树来增删改查呀。那你原先不是很麻烦的事情,我就可以进行一个处理吗?好,这个就是一个数遍历数组以数数的方式来便利数组的一个前序编列方法,那同学们看我这还有几个要求,大家看我这里写的代码,请同学们课后完成对数组以二叉数的中序后续编辑的代码,这个我做一个作业布置给同学们,晚上同学们呢,把这个做一做好吧。
19:10
好,这个你不要说你做不出来,你这个都已经写到这儿了,做不出来,呃,有点说不过去对吧,好,我把这呢也写到这里来。好,这是我们课后的一个练习。好,然后我们把刚才讲的呢做一个小结,刚才我们讲的是什么呀,我们讲的是顺序存储二叉数的一个概念。好,我们。我们粘一下。顺序存储二叉树。那顺序存算数,我先说了一个基本的概念。对,我先说了一个基本的概念给大家。我说了基本说明对吧,诶这边我们把它整理一下。整理下。好,这是它的基本说明。这是它的基本说明,然后这边有一个示意图。
20:01
这边有个示意图呢,我们也把它拿,诶这个示意图没有这边的好,因为我这边重新画了一个,应该这个看起来更。更清晰一些。OK。这个看起来更清晰一些。好,这是它的示意图,那示意图完了过后呢,我们就写了一段代码来给大家做了一个测试,就是二叉树它的一个顺序,二叉数的一个概念,它总结了几个特点,也把它给同学们板述到这里。二加速的。啊,几个概念,然后它的特点呢,我们也给大家板述一下,有这么四个特点,对吧,是需要同学们注意的。然后这边。有一个代码给他放过来。刚才我们写了一段代码来测试它。好,我把这个呢放到这儿。顺序二叉树的一个便利方式,需求在这儿代码实现。代码实现也给大家放到这。
21:01
好,这是我们数组当做数来编历的一段代码。好,写完了,截取一段视频。
我来说两句