6.6树的存储在线视频

同学们大家好

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

这节课我们讨论树的存储

数据结构的存储涉及数据元素的存储和关系的表示

树结构的存储我们会介绍三种办法

请同学注意不同方法中如何存储元素，如何描述关系

第一种称为双亲表示法

在前面的课程中，我们讨论过

树中除根结点外，每个结点有一个唯一前驱或者说双亲

它们和每个结点之间是前驱和后继的关系

是一个有序对，图中用一个分支表示两者的关系

双亲表示法就是利用唯一双亲这个特征

实现树的存储

我们结合一个例子来进行说明

图2是一棵树的逻辑结构

图1是这棵树双亲表示法的存储结构

观察图1，双亲表示法是顺序存储结构

利用一个一维数组来实现树的存储。

数组中每个单元是一个结构体，结构体中包含两个成员

一个成员data，用来存储数据元素本身

另外一个成员pArent，是一个指示器

本身是一个整型数

指示器的作用就是指明元素双亲在数组中的存储位置

树结构中总共有10个元素

我们分配数组nodes的0~9号单元存储这10个元素

元素存在成员data中

完成数据元素的存储

随后是描述关系

通过在双亲指示器中存储元素双亲在数组nodes中的位置来描述关系

0号单元的元素R是整棵树的根

对应的双亲指示器中存储-1

表示它没有双亲。1号单元是A

双亲指示器中0，表明A的双亲是存在0号单元的元素R

描述了R和A是前驱和后继的关系

用指前驱的方法描述了R到A这个分支

其它的分支也用同样方法处理

这样就把树中数据元素之间的关系描述出来了

实现了树的存储结构

我们简单看一下，双亲表示法的存储结构定义

首先定义了一个常量

表示一维数组的大小是100

随后，定义数组当中每个数据元素的类型

是一个结构体，包含两个成员

DAte存储数据元素，PArent描述双亲在数组中的位置

结构体取类型名PTNode

第二个结构体是树的存储结构定义

有3个成员，nodes是一维数组

数组元素类型是PTNode

大小是100，就是上一张幻灯片中的数组

另外两个整型成员，r给出树根在数组中的位置

n是树中元素的个数

第二种树的存储结构称为孩子表示法

双亲表示法是用指前驱的方式描述关系

那么孩子表示法就是用指后继的方式来描述关系

孩子表示法有两种考虑

一种是在二叉链表的基础上做扩充

二叉链表结点中有两个指针指向左右孩子

树中结点有多个孩子

可以按照树的度设置每个结点的指针数

如child1到childd

如果树中结点之间的度差别比较大的话

空间的浪费可能比较大

第二种考虑是，根据每个元素可能有多个孩子的情况

用一个结点描述一个孩子

多个描述孩子的结点组成一个单链表

下面结合例子做一个说明

图2是要存储的树，图1是孩子表示法存储的图示

首先仍然是把树中元素存储在一维数组nodes中

每个数组单元是一个结构体

有两个成员，data存数据元素

firstchild是一个指针，指向单链表中描述第一个孩子的结点

树中10个数据元素存在数组0~9号单元的data中

观察一下图中的0号单元，data存有元素A

从逻辑结构上看，结点A有两个孩子D和E

0号单元的firstchild指针指向包括两个结点的单链表

单链表中每个结点包含两个成员

整型数child表示孩子的位置，next指针链接单链表

第1个结点child中是3

说明A有一个孩子存在数组nodes的3号单元

就是数据元素D，第2个结点中是5

A另一个孩子存在数组nodes的5号单元

是E。同学们可以看到，树中元素有几个孩子

其对应的单链表中就有几个结点

指明孩子是存在数组的那个位置

如果没有孩子，比如叶子

它对应的firstchild指针为空

图中还有整型遍历r

用它记录树根在数组中的位置

示例中r=4，表示树根存在4号单元，树根是R

下面我们看一下这种方法存储结构的定义

孩子表示法存储结构的定义稍微复杂一些

分为三个部分，首先是对孩子单链表中结点的定义

定义为一个结构体，有两个成员

整型child用来指明孩子在数组中的存储单元

指针next用来形成孩子结点的链表

指针next用来形成孩子结点的链表

给这个结构体起了类型名ctnode

定义了一个指向结构体的指针类型的名字ChildPrt

第二部分是对一维数组当中每个数组单元类型的定义

也是一个结构体，包含两个成员

data用来存储数据元素本身

firstchild是ChildPrt类型的指针

指向单链表中描述第一个孩子的结点

结构体类型定义为CTBox

第三部分是对一维数组的定义

也是一个结构体，包含三个成员

一维数组nodes，数组元素类型是第二部分定义的CTBox

大小是MAX_TREE_SIZE

另外两个成员是整型数

n给出树中结点的个树

r指明树中根结点在数组当中的位置

图这一章中，这种存储方式会用来存储图结构

我们后面再来讨论

第三种树结构的存储方法

也是最重要的一种方法是孩子兄弟表示法

就形态上来说，孩子兄弟表示法是也是一种二叉链表的表示方法

这点和前面二叉树的二叉链表，形态上是差不多

孩子兄弟表示法中每个结点也是被定义为一个结构体

有三个成员，data存储树中元素

另外两个成员是两个指向自身的指针

firstchild，顾名思义

它指向当前结点的第1个孩子

nextsibling，是指向当前结点的下一个兄弟

兄弟的概念前面介绍过，同一双亲的孩子，称为兄弟

看一个具体的例子

图2是一棵树

孩子兄弟表示法中

我们仍然是为树中每个元素分配一个链表结点存储它

这棵树要分配10结点

每个链表结点的三个成员

左边是firstchild指向当前结点的第1个孩子

右边是nextsibling指向当前结点的下一个兄弟

从根R这个结点开始，对于R来说

它没有兄弟，兄弟指针为空

R的第1个孩子是A，那么孩子指针就指向结点A

A结点，第1个孩子是D

A结点的孩子指针就指向结点D，D是一个叶子

没有孩子，孩子指针为空，但是D有一个兄弟E

它们都是A的孩子，D结点的兄弟指针就指向结点E

E没有孩子，也没有下一个兄弟了，两个指针都为空

回过来看A结点，下一个兄弟是B，A的兄弟指针指向B

B没有孩子，有下一个兄弟C

B的兄弟指针指向C

其它的结点也是用这样的方式来描述元素之间的关系

按照孩子兄弟表示法

任何形态的树都可以这样来实现其存储

用一种统一的方法实现了树的存储

也就是说，用孩子兄弟表示法解决了树结构存储比较复杂性的问题

在孩子兄弟表示法中

树中有的元素之间前驱和后继的关系

没有被直接用指针描述，但隐含描述了

例如R和C的关系，C是R的第3个孩子

可以从R找到第1个孩子A,.然后从A的兄弟指针找到B

在从B的兄弟指针找到C

后续，对这个情况

我们在相应的算法中有适当的处理

同学们，这节课就讲到这

下次再见