第四篇数据结构树.docx

资源描述

第四篇数据结构树.docx

《第四篇数据结构树.docx》由会员分享，可在线阅读，更多相关《第四篇数据结构树.docx（34页珍藏版）》请在冰点文库上搜索。

第四篇数据结构树.docx

第四篇数据结构树

第十章非线性结构—树和图

第九章讨论的线性表（包括栈、队列、与串）属于线性结构。

在这种结构中，不管其存储方式如何，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件（除第一个元素外）和一个后件（除最后一个元素外）。

在实际生活中，可以用线性结构描述数据元素之间逻辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，因此在这类问题中，数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。

一般来说，至少存在一个结点（数据元素）有多于一个前件或后件的数据结构称为非线性结构。

具有非线性结构特征的数据结构有两种

1.⑴树

2.⑵图

§10.1树

例如某学校试图将学生成绩表中的百分制成绩转换成五个等级，其中成绩0～59分为不及格，60～69分为及格，70～79分为中，80～89分为良，90～100分为优。

现有n个学生的百分制成绩，如何将他们的成绩转换成五级分制。

下图揭示了一个百分制成绩的判定转换过程。

对于这样一张简单的表，已经不能用线性结构来表示。

因为表中数据元素可能有两个后件，它们之间的关系已经不是线性的了。

上图中所示的表是一个非线性结构。

由该图可以看出，虽然每一个结点可能有多个后件，但它们的前件却只有一个（第一个结点无前件）。

这种非线性结构称为树，树表示了数据元素之间的层次关系，而这种层次关系仿佛像一棵倒长的树。

下面讨论树的基本概念，其中重点讨论的是二叉树。

一、.树的概念

1、树的定义

树是一种常见的非线性的数据结构。

树的递归定义如下：

树是n（n>0）个结点的有限集，这个集合满足以下条件：

⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；

⑵除根外，其余的每个结点都有且仅有一个前件；

⑶除根外，每一个结点都通过唯一的路径连到根上。

这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；

由上述定义可知，树结构没有封闭的回路。

下图给出了树的几个示例：

2、结点的分类

在树中，一个结点包含一个元素以及所有指向其子树的分支。

结点一般分成三类

⑴根结点：

没有前件的结点。

在树中有且仅有一个根结点。

如上图（b）中的r；

⑵分支结点：

除根结点外，有后件的结点称为分支结点。

如上图（b）中的a，b，c，x，t，d，i。

分支结点亦是其子树的根；

⑶叶结点：

没有后件的结点称为树叶。

如上图（b）中的w，h，e，f，s，m，o，n，j，u为叶结点。

由树的定义可知，树叶本身也是其父结点的子树。

根结点到每一个分支结点或叶结点的路径是唯一的。

例如上图（b）中，从根r到结点i的唯一路径为rcti。

3、有关度的定义

3.⑴结点的度：

一个结点的子树数目称为该结点的度。

在上图（b）中，结点i度为3，结点t的度为2，结点b的度为1。

显然，所有树叶的度为0。

4.⑵树的度：

所有结点中最大的度称为该树的度。

图（b）中的树的度为3。

4、树的深度（高度）

树是分层次的。

结点所在的层次是从根算起的。

根结点在第一层，根的后件在第二层，其余各层依次类推。

即若某个结点在第k层，则该结点的后件均处在第k+1层。

图（b）中的树共有五层。

在树中，父结点在同一层的所有结点构成兄弟关系。

树中最大的层次称为树的深度，亦称高度。

图（b）中树的深度为5。

5、森林

所谓森林，是指若干棵互不相交的树的集合。

如图（b）去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合{Ta，Tb，Tc}就为森林，这三棵子树的具体形态如图（c）。

6、有序树和无序树

按照树中同层结点是否保持有序性，可将树分为有序树和无序树。

如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。

二、树的表示方法和存储结构

1、树的表示方法

树的表示方法一般有两种：

5.⑴自然界的树形表示法：

用结点和边表示树，例如上图采用的就是自然界的树形表示法。

树形表示法一般用于分析问题。

6.⑵括号表示法：

先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：

同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。

例如图（b）可写成如下形式

（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））

2、树的存储结构

树的存储结构一般有两种

⑴静态的记录数组。

所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n（n为树的度）的数组，分别存储该结点的每一个儿子的下标

Const

n=树的度；

max=结点数的上限；

Type

node=record{结点类型}

data：

datatype；{数据域}

ch：

array[1‥n]ofinteger；{指向各儿子的下标}

end；

treetype=array[1..max]ofnode；

Var

tree：

treetype；{树数组}

例如图（b）的树，其记录数组如下。

由于未规定同层结点的次序，因此每个结点儿子的下标序列（Tree[i].ch）任意。

其中Tree[i].ch[j]=0说明结点i的第j个儿子不存在。

⑵动态的多重链表。

由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。

所谓多重链表，就是每个结点由数据域和n（n为树的度）个指针域共n+1个域组成，其表示方法如下：

Constn=树的度；

Type

treetype=↑node；{结点类型}

node=record

data：

datatype；{数据域}

array[1‥n]oftreetype；{指向各儿子的指针域}

end；

Var

root：

treetype；{根结点指针}

例如上图（b）中的树，其多重链表如下

显然，取树的度作为每个结点的链域数（即指向儿子结点的指针数）虽使各种算法简化，但会造成存储空间的大量浪费。

因为可能有很多结点中存在空链域。

空链域的个数x为多少呢？

设树的结点数为n度为k。

由于除根外的n-1个结点，每一个结点有且仅有一个前件，因此x+n-1=nk。

X=n*（k-1）+1。

能不能在减少浪费的空链域的前提下，寻找一种既使得每个结点的结构相同、又方便运算的树形式呢。

下面将要看到，用二叉树来表示树，就能达到这个目的。

三、二叉树的概念

二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。

1、二叉树的递归定义和基本形态

二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：

⑴有一个特定的结点称为根；

⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；

由上述定义可以看出，二叉树和树是两个不同的概念

⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；

⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。

我们称二叉树中结点的左后件为左儿子，右后件为右儿子。

前面引入的有关树的一些基本术语对二叉树仍然适用。

下图列出二叉树的五种基本形态：

2、二叉树的两个特殊形态

⑴满二叉树：

如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。

（例如下图（a））可以验证具有n个叶结点的满二叉树共有2n-1个结点。

⑵完全二叉树：

如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图（b））

3、二叉树的三个主要性质

性质1：

在二叉树的第i（≥1）层上，最多有2i-1个结点

证明：

我们采用数学归纳法证明：

当i=1时只有一个根结点，即2i-1=20=1，结论成立。

假设第k（i=k）层上最多有2k-1个结点，考虑i=k+1。

由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点，因此在第k+1层上最多有2．2k-1=2（k+1）-1=2i，结论成立。

综上所述，性质1成立。

性质2：

在深度为k（k≥1）的二叉树中最多有2k-1个结点。

证明：

由性质1，在二叉树第i层上最多有2i-1个结点，显然，第1层‥第k层的最多结点数为

个结点。

证毕。

性质3：

在任何二叉树中，叶子结点数总比度为2的结点多1。

证明：

设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然

n=n0+n1+n2

（1）

由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。

设b为二叉树的前件个数，

n=b+1

（2）

所有这些前件同时又为度为1和度为2的结点的后件。

因此又有

b=n1+2n2（3）

例如下图

除v0没有前件外，v1、v2、v3、v4、v5都有一个前件，b=5。

而v1和v2为v0的后件，v3为v1的后件，

v4和v5为v2的后件，因此b=b=n1+2n2=1+2*2=5。

我们将（3）代入

（2）得出

n=n1+2n2+1（4）

比较

（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1

四、树或森林转换成二叉树

1、普通有序树转换成二叉树

我们在前面中曾讲过，在用多重链表示普通树时，会浪费存储空间。

另外，由于树中各结点的度各不相同，因此对树中各结点的搜索比较困难。

在实际应用中，往往将普通树转化成二叉树，这种处理既减少了存储空间的浪费又便于搜索。

假设所讨论的普通树为有序树T，则将其转化成二叉树T’的规则如下：

⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；

⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；

⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；

由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。

例如将下图（a）所示的普通有序树转换成二叉树（下图（b））。

2、森林转换成二叉树

如果m棵互不相交的普遍有序树组成了森林F={T1，…Tm}。

我们可以按下述规则将森林F转换成一棵二叉树b={R，LB，RB}：

⑴若F为空（m=0），则b为空树；

⑵若F非空（m≠0），则b的根R即为森林中第一棵树的根R（T1）；b的左子树LB是从T1的根结点的子树森林F1={T11，T12，…T1k}转换而成的二叉树；其右子树RB是从森林F2={T2，T3，…，Tm}转换成的二叉树。

下图给出了森林转换成二叉树的示例

由此可见，森林转换成二叉树的方法为

⑴将各棵树的根相连；

⑵将森林中的每棵树转换成相应的二叉树；

⑶以第一棵树为轴心，顺时针粗略地旋转900；

五、二叉树的存储结构

二叉树的存储结构有两种形式

⑴顺序存储结构

⑵链式存储结构

1、顺序存储结构

将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。

每个结点的信息包括

⑴一个数据域（data）；

⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。

满二叉树和完全二叉树一般采用顺序存储结构

Constm=树中结点数上限；

Type

node=record{结点类型}

data：

datatype；{数据值}

prt，lch，rch：

0‥m；{父结点、左儿子、右儿子编号}

end；

treetype=array[1‥m]ofnode；{二叉树的顺序表类型}

Var

Tree：

treetype；{二叉树}

例如，采用数组tree存储二叉树（如下图）

2、链式存储结构

对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。

这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。

如果二叉树的存储需求量超过64Kb，则采用后者。

由于二叉树中每个结点通常包括数据元素和两个分支。

因此二叉树对应的二重链表中每个结点应有三个域：

⑴值域：

data

⑵左指针域：

lch

⑶右指针域：

rch

这种链表也称为二叉链表。

二叉链表头指针bt指向二叉树的根结点

Type

bitrpetr=↑bnode；{结点指针类型}

benode=record{结点类型}

data：

datatype；{值域}

lch，rch：

bitreptr；{左指针域和右指针域}

end；

Var

bt：

bitreptr；{头指针}

例如用下图（b）所示的二叉链表存储二叉树（下图（a））

六、树或森林的遍历

1、二叉树的遍历

所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。

在访问到每个结点时，可以取出结点中的信息，亦可以对结点作其它的处理，对于线性结构来说，遍历并非难事，但对二叉树来说，由于它是一种非线性结构，必须要找到一种完全而有规则的遍历方法，通过遍历得到二叉树中各个结点信息的线性序列。

如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!

=6）组合：

LDR、LRD、DLR、DRL、RDL、RLD

若再限定先左后右的次序，则只剩下三种组合

LDR、LRD、DLR

这三种遍历规则分别称为中序遍历。

后序遍历和前序遍历。

下面分别介绍这三种遍历的方法。

在讲解过程中，二叉树的存储采用动态的二重链表形式。

为了方便叙述，我们以下图为例解释三种遍历规则，并且分别以二叉链表和数组两种存储结构给出三种遍历的程序。

⑴前序遍历

前序遍历的规则如下：

若二叉树为空，则退出。

否则

⑴访问处理根结点；

⑵前序遍历左子树；

⑶前序遍历右子树；

例如对于如上图所示的二叉树，前序遍历的过程为：

先访问根结点a，再遍历其左子树，然后遍历其右子树。

在遍历其左子树时，也按照前序规则，即先访问根结点b，然后遍历其左子树，最后遍历右子树，…，依次类推，直到根结点a的左子树的所有结点全部被访问完毕；再以同样的规则访问a的右子树中的所有结点；最后可以得到如下的前序遍历序列（简称前序序列）

abdehicfg

算法如下：

⑵中序遍历

中序遍历的规则如下：

若二叉树为空，则退出；否则

⑴中序遍历左子树；

⑵访问处理根结点；

⑶中序遍历右子树；

若中序遍历上图中的二叉树，可以得到如下的中序序列：

dbheiafcg

算法如下：

⑶后序遍历

后序遍历的规则如下：

若二叉树为空，则退出；否则

⑴后序遍历左子树；

⑵后序遍历右子树；

⑶访问处理根结点；

若后序遍历上图中的二叉树，可以得到如下的后序序列

dhiebfgca

算法如下：

2、普遍有序树的遍历

仿照二叉树的前序遍历和中序遍历，可以定义普遍有序树的两种遍历顺序。

由于普遍有序树中的子女数可能多于两个，因此不好仿照二叉树遍历中序与其女子的对称次序。

下面，给出普遍有序树转化为二叉树的一个例子，看一看，普遍有序树的遍历顺序可借用二叉树的哪一种遍历顺序实现。

⑴先根次序遍历树

先根次序遍历的规则如下：

若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。

例如，对上图（a）中的普遍有序树进行先根遍历，可得到树的先根序列为

rawxdhebfcstimonju

若对上图（b）中的二叉树进行前序遍历，得到的前序序列与之相同。

由此可见，当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。

⑵后根次序遍历树

后根次序遍历的规则如下：

若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。

例如对上图（a）中的普遍有序树进行后根遍历，可得到树的后根序列为

whdexafbsmonijtucr

若对上图（b）中的二叉树进行中序遍历，得到的中序序列与之相同。

由此可见，当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。

【例题

输入一棵普通有序树，输出该树的先根次序和后根次序。

输入：

顶点个数n（1≤n≤200）

以下含n行，其中第i行（1≤i≤n）的元素依次为结点i的数据值ai。

以后各元素为结点i的儿子序列，以0结束。

若ai后仅含一个0，则说明结点i为叶子。

例如对于下图（ａ）的多叉树

对应的输入信息为

’r’2340

’a’560

’b’70

’c’89100

’w’0

’x’11120

’f’0

’s’13140

’t’000

’u’0

’’d’150

’e’0

’i’1617180

’j’0

’h’0

’m’0

’o’0

’h’0

输出：

两行，分别为普通有序树的先根次序和后根次序

分析：

“四、树或森林转换成二叉树”一节中介绍了普通有序树转换成二叉树的规则。

我们在输入普通有序树的同时，按照规则进行转换：

fillchar（tree，sizeof（tree），0）；{二叉树初始化}

readln（n）；{读入普通有序树的结点个数}

fori←1tondo{依次读入普通有序树中每个结点的信息}

begin

read（tree[i]．data）；

read（j）；{读结点i的第一个儿子序号j}

　ifj<>0then{若结点j非叶子}

begin

tree[i]．lch←j；tree[j]．prt←i；{结点j作为结点i的左儿子}

p←j；{从结点j出发转换其它兄弟结点}

repeat

read（j）；{读结点i的下一个儿子序号j}

ifj<>0thenbegin

tree[p]．rch←j；tree[j]．prt←p；{结点j作为结点p的右儿子}

p←j；

end；{then}

untilj=0；{直至处理完结点i的所有儿子信息}

end；{then}

writeln；{准备输入结点i+1的儿子信息}

end；{for}

上述转换算法的时间复杂度为W（n2）。

例如下图

图（ａ）的普通有序树经转换运算后得出的tree数组如下

Data

prt

lch

rch

’r’

’a’

’b’

’c’

’w’

’x’

’f’

’s’

’t’

’u’

’d’

’e’

’i’

’j’

’h’

’m’

’o’

’n’

该数组正好对应图（b）的二叉树。

在得出二叉树tree后，我们分别调用过程preorder

（1）和过程inorder

（1），对其进行前序遍历和中序遍历，得出普通有序树的先根次序和后根次序。

由此得出主程序

输入普通有序树并转换成二叉树tree；

preorder

（1）；{对二叉树tree进行前序遍历}

inorder

（1）；{对二叉树tree进行中序遍历}

3、森林的遍历

若有多棵互不相交的普通有序树组成森林，则同样可以导出森林的两种遍历规则。

由森林与二叉树之间的转换规则可知，当森林转换成二叉树时，其第一棵树根结点的子树森林转换成左子树，剩余树的森林转换成右子树。

由此得出森林的遍历和转化后二叉树的遍历有对应关系。

下面，给出森林转化为二叉树的一个例子，看一看，森林遍历顺序可借用二叉树的哪一种遍历顺序实现。

⑴先根遍历森林

若森林非空，则可按下述规则遍历之

7.访问森林中第一棵树的根结点；

8.先根遍历第一棵树中根结点的子树森林；

9.先根遍历其余树构成的森林；

若对上图（a）中的森林进行先根遍历，则得到森林的先根序列为abCDEFGHIJ。

森林的先根遍历即为其对应的二叉树的前序遍历。

例如对上图（c）中的二叉树进行前遍历，结果是相同的。

⑵后根遍历森林

若森林非空，则可按下述规则遍历之

1后根遍历森林中第一棵树的根结点的子树森林；

2访问第一棵树的根结点；

3后根遍历其余树构成的森林；

若对上图（a）中的森林进行先根遍历，则得到森林的后根序列为bCDaFEHJIG。

森林的后根遍历即为其对应的二叉树的中序遍历。

例如，对上图（c）中的二叉树进行中序遍历，亦可得出对应森林（上图（a）的后根遍历序列。

七、由二叉树的两种遍历顺序确定树结构

遍历二叉树（如下图）有三种规则：

前序遍历：

根—左子树—右子树；

中序遍历：

左子树—根—右子树；

后序遍历：

左子树—右子树—根；

从上述遍历规则可以看出，前序遍历的第一个字符和后序遍历的最后一个字符为根，中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构，因此二叉树的形态可以由其中序与后序或者前序与中序唯一确定。

但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点，因此这两个遍历顺序可对应多种二叉树的形态。

【例题

输入：

二叉树的中序遍历顺序与后序遍历顺序

输出：

二叉树的前序遍历顺序

输入：

二叉树的中序遍历顺序与前序遍历顺序

输出：

二叉树的后序遍历顺序

分析：

二叉树的形态可以由其中序与后序或者前序与中序唯一确定，因此可以由中序与后序得出前序，由前序与中序得出后序。

1、由二叉树的中序遍历顺序与后序遍历顺序确定树结构

由二叉树的遍历规则可以看出，后序遍历的最后一个字符为根，中序遍历中位于该字符左侧的子串为左子树中序遍历的结果；中序遍历中位于该字符右侧的子串为右子树中序遍历的结果。

设

中序遍历s’=s1’…sk’…sn’

后序遍历s”=s1”……sn”

显然，后序遍历中的sn”为二叉树的根。

按照前序遍历的规则输出sn”。

在中序遍历中与sn”相同的字符为sk’。

若k>1，说明左子树存在，位于sk’左侧的子串s1’…sk-1’为左子树中序遍历的结果，后序遍历中的前缀s1”…sk-1”为左子树后序遍历的结果；若k

按照按照前序遍历的规则分别递归二叉树的左子树和右子树。

例如

中序遍历s’=’dbeafc’后序遍历s”=’debfca’

这棵二叉树的根为a。

左子树中序遍历的结果为’dbe’，左子树后序遍历的结果为’deb’，由此得出二叉树的左根为b，b的左右儿子分别为d和e；右子树中序遍历的结果为’fc’，右子树后序遍历的结果亦为’fc’。

由此得出二叉树的右根为c，c仅有左儿子f，该二叉树由下图所示：

对应的前序遍历为s=’abdecf’。

按照上述遍历规则编写递归程序solve1（s1，s2）。

其中s1和s2分别为二叉树的中序遍历和后序遍历。

Solve1过程计算和输出

展开阅读全文