00:00
各位同学,我们接着来讲二叉树的下一个内容叫什么呢?叫做顺序存储二叉树,听这个名字,同学们。顺序存储二叉树什么意思呢?先来介绍一下它的概念。从数据存储来看呢,数据存储方式和数的存储方式,它是可以相互转换的。也就是说宿组可以转成数,那么数呢,也可以转成数组,我举一个例子,同学们看,同学们看这个右图。这边有个图呢,这边是一棵树,大家有没有看到是一棵二叉树,很好理解,这个是个什么呀?这个是一个数组,现在呢,我的要求是这样子的。注意,听我的要求,有这么两点,大家看你能不能想办法实现它第一个呢?就是数,数的这种结构呢,我要求以数组的方式来存放,注意听啊,就是数就是二叉树。
01:01
比如说右图的右图的二叉,二叉数的数据或者叫节点吧。节点以什么呢?要求以以数组的数组的A数组的方式来存放。存放,那显然你右图的二叉树如果以数组的方式来存放,那就变成这个德行了,那也就是说你变成什么呢?变成了一。二。三四。五。六七对不对。如这个图,也就是说,相当于我们以这种方式来存放我们的。这个数,但是呢,我有要求,各位同学,但是我有要求,我有什么要求呢?好,我把这个呃给大家写到这啊,我的要求是这样子的,虽然我是以数组的方式来存放。
02:00
这棵这棵树的。呃,节点的,但是呢,我要求在遍历这棵遍历这个数竹的时候,仍然能够保证它是以树的方式来来便利的,比如说前续便历,中续便历和后续便历,能明白我的意思吧,说,但是我要求要求什么呢?要求在便历这个数组的时候,比如这个数我们数组叫R位,好吧,假定我们叫R位。那么在遍历数组二时二瑞时,仍然A仍然仍然可以可以以以什么呢?以这个诶这个地方我这样子处理一下啊。啊,仍然可以。哎,这个地方不好意思,这个稍微的整理一下。要求仍然可以以。以什么呢?可以以这个情绪便利。
03:00
OK,前续便利,对中续便利和后续便利。和后续。便利的方式,方式完成什么呢?完成这个便利,数据的便利,或者叫节点的便利。绝对的便利。就这个意思,话说的再直接一点,就是这个数呢,这个数我们把它以数组的方式存放,但是在遍这个数遍历这个数组的时候呢,它仍然能够体现出这个数的前序、中序和后序遍历,就这样子,这个呢我们就称之为顺序存储二叉树。为什么顺序存储呢?你看数组是不是是一种顺序结构啊?数组是不是用顺序存储结构?那就相当说我把这个数以数组这种顺序存储结构把它保存起来,但是我在变列的时候呢,我仍然可以以前序。
04:00
对不对,以前序以中续以后续的方式来编利,这个就叫这个就称之为顺序存储二导数理解了吗?好,那么我们再来看这有一个问题,你要完成这个任务,你必须对顺序存查存储二叉树的一些特点进行一个理解,和和和这个和这个掌握,你看老师给大家解释一下,比如说我们这个二叉树第一个节点。一。我们认为,呃认为它是零,因为为什么呢?因为当它数组的时候,看到一二,它顺序存储1234567,你这是不是有七个节点,1234567,是不是有七个节点,那你顺数存储就是1234567,那么大家有没有观察到它有什么特点?第一点,我们要知道顺序。二叉树呢,我们通常。
05:01
好,通常只考虑。完全二叉树。二要素,那么第N个大家看第二个特点,大家有没有发现第N个元素的左子节点其实是二乘以N加一,这是什么意思呢?我们举个例子啊,同学们看。假如我现在看的第,我们看第二这个这个二这个节点。二这个节点它左边。是不是着字节点是不是四啊。大家看第二个,这个节点左边是四,而二,如果二这个节点如果放在数组里边,它的下标为一,这个能看清楚吗?啊,我们来看看,如果这样算的话,就是二乘以一加一就是D下边为三是不是啊,看二的,它的着子节点是四,而四呢,在数组里面的确它的下标是三。
06:05
看到没有?所以说第N个元素的左子节点就是二乘以N加一。你再看这个也是一样,你看这个三三这个节点呢,它的它是它如果存储到数据里,数据那个数组里面,它是下标为二的。是不是为二的,那么这个时候你来判断它左边的这个着字节点是五,五怎么算出来呢?是二乘以二再加一是不是就是如果我要,我要去在数组里面去访问三的左止节点就应该是二乘以二加一,就是下边为五的这个数就是六,正好是它的左子节点。那同样道理,第N个元素的右子节点是二乘以N2乘以N加二。也也就是这个意思。啊,相当于说二乘以N加一,但是呢,这样看的更清晰一点,所以说我用的是二乘以N加二,那大家我们再来验证一下啊,随便找一个吧,比如说还是以这个节点为例,假如说三这个节点它存储到数据里面,它是下边为二的。
07:13
是这个地方吧,那么它三的右子节点是下标为六的,这个七是不是是不是这样子呢?但是二乘以二再加一个二等于几啊等于六。是不是刚好就是。就是它的这个下标为六的这个数,其实就是它的右子节点,看清楚没有。所以这个特点大家一定要把它拿下。那么我们再看第N个元素的负节点,是下边为极呢?我们随便找一个吧,我们找这个这个五。五这个元素五这个节点吧,它的下标是四。是不是四,你看这存出下来01234,那它的下标为四,那么它的负节点。
08:02
它的负节点的下标应该为几呢?就应该是N减一乘除以二,我们算一下是不是这样子的啊,我拎出去就是四减去一个一括起来除以二等于几呢?等于三除以二,三除以二取整应该为一刚好。一下标为一的这个节点其实就是它的负节点。所以这几个特点大家一定要把它拿下好,这是给大家说的。几个特点?第二点呢?我们看到这里所说的N,第N个元素是表示二叉数的第几个元素,它是按从零开始编号的,为什么是从零,它要跟数组保持一致?也就是说它要跟数组保持一致,就是老师这讲的啊,这个零,你看第一个元素是零吧,放到我们数,放到数组里面一是不是下边为零。是这样子吧,好,同学们把这个要理解清楚啊,理解清楚好,理解清楚这一个顺序存储二叉树的概念以后呢,下面我们就用代码来跟大家实现顺序存储,存储二叉树的一个功能,或者说呃,一一个代码实现。
我来说两句