6.3二叉树的存储结构在线视频

同学们，大家好

我是云南大学信息学院教师孔兵

这节我们讨论二叉树的存储结构。

我们先看一下二叉树的顺序存储结构

顺序存储是用一组连续的存储单元来存储二叉树的数据元素

因为二叉树是非线性的

在此需要考虑一个问题

就是必须把二叉树的所有结点安排成一个恰当的序列

并且能通过结点在这个序列中的相互位置

暗示出结点之间谁是前驱谁是后继的逻辑关系

就二叉树而言

就是用相对位置来描述双亲和左右孩子的关系

我们先看一下，完全二叉树的顺序存储结构怎么实现

我们以图中的完全二叉树为例

说一下顺序存储的实现

首先对完全二叉树进行编号

有12个节

随后，就按这个编号的次序

把编号为i的结点存入到一维数组的下标为i的单元中

图中可以看到对应存在了1~12号单元

数据结构的存储包括两个方面

元素的存储和关系的表示

结点存在每一个数组单元

这是清楚的

关键是这样的安排的序列

是否能描述结点之间双亲和左右孩子的关系

前面性质5中讨论过

对一棵完全二叉树

可以通过自上而下自左至右的方式

对完全二叉树的结点进行编号

编号后，完全二叉树的结点编号有这样的性质

对于编号为i的结点来说

其双亲如果存在，则双亲的编号是i除2向下取整

其左孩子如果存在，则左孩子是编号为2i

其右孩子如果存在，则右孩子是编号为2i+1

注意刚才我们的存储方式

我们是按照结点的编号存到数组对应下标的

也就是编号为i的元素我们存在数组的第I个下标

那么，我们实际上已经利用性质5暗示了结点之间双亲和孩子的关系

存储在下标i的结点

其双亲是存在下标i/2的结点

其左孩子是存在下标2i的结点

其右孩子是存在下标2i+1的结点

以4号单元的D为例，D的双亲在2号单元

D的左孩子在8号单元，右孩子在9号单元

总结一下，在完全二叉树的顺序存储中

利用性质5

通过结点在存储空间中的位置暗示了结点之间的逻辑关系

这就是顺序映像的办法

从存储情况来看

利用顺序映像存储完全二叉树效果是比较好的

空间利用充分，找双亲和孩子都很方便

那么普通的二叉树采用顺序存储结构怎么样呢

普通的二叉树也可以通过顺序存储的方式实现它的存储

主要问题仍然是如何通过结点的存储位置描述结点之间的关系

参考完全二叉树存储的方法

我们把普通二叉树

通过加虚结点的方式

把它补充成一棵完全二叉树的形态

比如说图1所示的二叉树

可以通过添加4个虚结点的办法

把它变成图2所示的完全二叉树形态

随后，按照完全二叉树的办法对所有结点（包括虚结点）进行编号

按照同样的方式把它存储在一维数组当中

虚结点对应的位置置空

如图3所示

通过这样的方式可以实现普通二叉树的顺序存储

我们注意到在存储空间当中有些空的部分

就是虚结点的位置

从前面的讨论我们可以看出

顺序存储结构

比较适合存储完全二叉树

对普通二叉树来说

可能对存储空间造成极大的浪费

在最坏的情况下，一个深度为h

且只有h个结点的右单支树

需要2h-1个结点存储空间

但是它实际用来存数据元素的空间只有h个

其它都是补的虚结点

可以说都被浪费掉了

另外，若二叉树中有插入和删除操作

那么插入结点或者删除结点以后

很多结点所在的层次会发生改变

这些结点的编号肯定会发生变化

为了用位置暗示结点的关系

这些结点是需要移动的

这种情况下

顺序存储方式也不是很理想

下面我们看一下链式存储结构

线性表中，每个结点附设一个指针

指向其后继，利用指针描述关系

建立所谓单链表

二叉树中，最多有两个后继

我们做一点扩充

在每个结点设两个指针

分别指向两个后继，左孩子和右孩子

存储结构定义为一个结构体

BiTNode

包含三个成员：一个是存储数据元素的data

另外两个是指向自身类型的指针lchild和rchild

它们分别指向存储data左孩子和右孩子的结点

typedef给这个结构体起了个类型名叫BiTNode

取了一个指向结构体的指针类型名BiTree

直观看一下，后面画结点都是这样的

一个结点有3个成员

中间是data，左边是lchild

右边是rchild。另外一种结点有三个指针

增加了一个指向双亲的指针parent

下面我们下面我们看一下链式存储结构的示意图

图1的二叉树，只有4个结点

但是有4层，采用链式结构实现它的存储

需要申请4个结点，每个结点存储一个数据元素

为了描述结点之间的关系

需要用指针。A结点的lchild指针指向存储B的结点

表示B是A的左孩子

A没有右孩子，A结点的rchild指针置空

同理，B结点的lchild指针指向C

C结点的lchild指针指向的D。D是叶子

左右指针都为空。从例子中可以看到

树中有几个结点就申请几个结点的存储空间

另外，插入删除也比较方便

只涉及部分指针的重置

图3是一棵稍微复杂一点的二叉树

其存储结构是图4

随后，我们把这样实现二叉树的存储形式称为二叉链表

这里，大家注意一下，存储根的这个结点

它的作用和单链表中的头结点有点类似

就说我们通过一个BiTree类型的指针T指向根结点

这个指针就代表了这棵树

经常用作基本操作的参数

操作这棵树的时候，都是从根开始

作为所有结点的祖先

从根可以通过左右指针找到树中任何一个结点

另外，在含有n个结点的二叉链表中呢

总有n+1链域是空的

从图中我们可以看到

一个指针实际上描述了一个前驱和后继的关系

也就是描述了树中的一个分支

我们知道n个结点的树中有n-1个分支

每个结点有左右两个链域

共2n个，描述分支只需要n-1个

有n+1链域是空的。在后面的讨论中

我们会把这些空链域用起来，提升遍历二叉树的效率

下面我们看一下三叉链表

和二叉链表比较而言呢

它就是增加了一个指向双亲的指针parent

在需要频繁找双亲的问题当中

这样的设计可能是有价值的

下面我们看一下静态二叉链表

前面我们提到过

在有的程序设计语言当中没有指针

要实现链式存储结构，可以采用静态链表的办法

这里二叉链表同样也可以用静态的方法来实现

用数组的下标来模拟指针

直观的看就是开辟三个一维数组

Data ,lchild, rchild.用这三个数组分别存储结点的元素

及其左右孩子的位置

下面看一个例子。

首先是一个data数组，每个单元用来存储树中一个结点

图1的树中有4个数据元素

把这4个数据元素A，B, C, D

分别存储在data的1~4号单元

另外两个数组是两个整形数组

它们的作用是描述关系

我们看，data中1号单元中存储的是A

2号单元中存储的是B

在逻辑结构中，B是A的左孩子

我们就在lchild数组的和a对应的1号单元当中存储2

这个2就是一个游标

用这个游标指明A的左做孩子存在data的2号单元

也就是描述了，A的左孩子是B

这样一个有序对。A没有右孩子

其对应的rchild数组的1号单元存0

表明其没有右孩子

其它的关系也用同样的方式表示

B的左孩子存储在data的3号单元

C的左孩子存储在data的4号单元

D是叶子, 没有左右孩子，对应游标为0

也可以把三个一维数组合并一下

合并成一个一维数组

数组的每个单元的类型是一个结构体

结构体中包含date, lchild, rchild三个成员，效果是一样的

好同学们，这节课就上到这儿

我们下次课再见