数据结构第07章.docx

数据结构第07章.docx

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

数据结构第07章

第七章树

树形结构是一类十分重要的非线性结构，它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象，因此在计算机领域里有着广泛应用，如操作系统中的文件管理、编译程序中的语法结构和数据库系统中信息组织形式等。

在现实生活中，同样存在很多可用树形结构描述的对象，如行政组织机构和族谱等。

本章将详细讨论这种数据结构，特别是二叉树结构。

7.1树的基本概念

7.1.1树的定义

一、树的递归定义

树是由n（n＞0）个结点组成的有限集合（记为T）。

在一棵树中满足如下两个条件：

1．有且仅有一个特定的结点，称为根结点；

2．其余的结点可分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1。

其中每个集合又都是一棵树，称这些集合为根结点的子树。

二、说明

1．树的定义是递归的，在树的定义中又用到树的概念。

它刻化了树的固有特性，即一棵树由若干棵子树构成，而子树又由更小的若干棵子树构成，…。

2．一棵树至少有一个结点，因为在定义中，结点数n大于0；（有的教材n可以为0，当n＝0时，称T为空树）。

3．树是一种非线性数据结构，具有以下特点：

它的的每一结点都可以有不止一个直接后继；除根外的所有结点，都有且只有一个直接前趋；这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。

可以看出，数据元素之间存在的关系是一对多，或者多对一的关系，与前面讨论的线性表、栈队和数组线性结构有很大差别。

三、实例

图7.1.1是一棵有14个结点的树，其中A是根结点，其余结点分成三个互不相交的子集；T1＝｛B，E，F，G，L｝，T2＝｛C，H，I｝，T3＝｛D，J，K，M，N｝；T1、T2和T3都是根A的子树，且本身也是一棵树。

对于子树T1，其根为B，其余结点分为三个互不相交的子集；T11＝｛E｝，T12＝｛F，L｝，T13＝｛G｝，T11、T12和T13都是B的子树。

而T11中的E是根，其余结点为空，没有子树；T12的根是E，其余结点成为唯一的子集｛L｝；T13中的G是根，没有子树。

从图中还可以看到，树根结点A没有直接前趋结点，其它13个结点都有一个唯一直接前趋结点，如B，C和D的直接前趋结点为A；E，F和G的直接前趋结点为B等等。

每一结点可以有多个直接后继，如A的直接后继有B，C和D三个结点，D的直接后继有J和K两个结点，而E、L、G、H、I、J、M和N没有直接后继结点。

图中清晰地反映了数据元素之间的层次关系，A在第一层，B、C、D同处在A的下一层。

图7.1.1树的实例

7.1.2树的基本术语

树的许多术语借用了家族树中的一些惯用名词。

1．结点的度与树的度由树的定义可知，树的结点包含一个数据元素及若干指向其子树的分支。

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

树中各结点之度的最大值称为树的度，通常称度为m的树为m次树。

例如，在图7.1.1所表示的树中，A和B的度为3；C、D和K的度为2；F的度为1；其它结点的度为零。

因结点的最大度数为3，所以树的度为3，我们称该树为3次树。

2．分支结点与叶结点度不为零的结点称为非终端结点，又叫分支结点。

度为零的结点称为叶结点或终端结点。

在分支结点中，每个结点的分支数就是该结点的度数。

如对于度为1的结点，其分支数为1，被称之为单分支结点；对于度为2的结点，其分支数为2，被称之为双分支结点，其余类推。

如在图7.1.1所表示的树中，E、G、H、I、J、L，M和N都是叶子结点，A、B、C、D、F和K都是分支结点，其中F为单分支结点，C、D和K为双分支结点，A和B为三分支结点。

3．路径与路径长度对于任意两个结点ki和kj，若树中存在一个结点序列ki，ki1，ki2，…，kin，kj，使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继，则称该结点序列为由ki到kj的一条路径，用路径所通过的结点序列（ki，ki1，ki2，…，kj）表示这条路径。

路径的长度等于路径所通过的结点数目减1（即路径上分支数目）。

可见路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。

显然，从树的根结点到树中其余结点均存在一条路径。

例如在图7.1.1所示的树中，结点A到L有一条路径（A，B，F，L），长度为3；D到M有一条路径（D，K，M），长度为2。

结点B到D之间不存在任何路径。

4．孩子结点、双亲结点和兄弟结点为了形象描绘树的结构中结点的关系，我们常借用家族关系的称呼来作为树的描述性术语。

在一棵树中，每个结点的各子树的根，或者说每个结点的后继，被称作该结点的孩子（或儿子，或子女），相应地，该结点被称作孩子结点的双亲（或父亲，或父母）。

具有同一双亲的孩子互为兄弟。

进一步推广这些关系，可以把每个结点的所有子树中的结点被称作该结点的子孙，从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先。

如在图7.1.1所表示的树中，E、F、G是B的三棵子树的根，则E、F、G就是B的孩子，而B为E、F，G的双亲；E、F，G互为兄弟；D结点的子孙为J、K、M、N结点；M结点的祖先为K、D、A结点。

由孩子结点和双亲结点的定义可知：

在一棵树中，根结点没有双亲结点，叶子结点没有孩子结点，其余结点既有双亲结点也有孩子结点。

5．结点的层数和树的深度树既是一种递归结构，也是一种层次结构，树中的每个结点都处在一定的层数上。

结点的层数从树根开始定义，根结点为第一层（有的教材从第0层开始），它的孩子结点为第二层，以此类推，一个结点所在的层次为其父结点所在的层次加1。

树中结点的最大层数称为树的深度（或高度）。

如在图7.1.1所表示的树中，A结点处于第一层；B、C、D在第二层；E、F、G、H、I、J、K在第三层；L、M、N第四层。

树了中结点的最大层数为4，所以该树的深度为4。

6．有序树和无序树若树中各结点的子树是按照一定的次序从左向右安排的，相对次序不能随意变换的，则称之为有序树，否则称之为无序树。

如对于图7.1.2中的两棵树，若看作为无序树，它们表示同一棵树；按照有序树的概念，它们表示两棵不同的树，因为根结点A的两棵子树的次序不同，一个是B子树在前，C子树在后，而另一个则相反。

图7.1.

2两棵不同的有序树

7．森林n（n＞0）个互不相交的树的集合。

森林的概念与树的概念十分相近，因为只要把树的根结点删掉就成了森林。

如在图7.1.1所表示的树中，若删除根结点A，就可得到一个由B、C和D三棵树组成的森林。

反之，只要给n棵独立的树加上一个结点，并把这n棵树作为该结点的子树，则森林就变成了树。

7.1.3树的逻辑表示方法

树的逻辑表示方法有多种，但不管采用哪种表示方法，都应该能够正确表达出树中数据元素之间的层次关系。

下面是几种常见的逻辑表示方法。

一、树形表示法

用一个圆圈表示一个结点，圆圈内的符号代表该结点的数据信息，结点之间的关系通过连线表示。

虽然每条连线上都不带有箭头（即方向），但它仍然是有向的，其方向隐含着从上向下，即连线的上方结点是下方结点的前驱，下方结点是上方结点的后继。

它的直观形象是一棵倒置的树（树根在上。

树叶在下），如图7.1.1所示。

这种表示方法的特点是形象、直观。

因此在数据结构的书中都采用这种方法。

二、二元组表示法

用有序对＜D，R＞表示一棵树，其中D为树的所有结点构成的集合，R为D上的一个二元关系（即D中结点组成的二元组的集合）。

R中的每个二元组（关系）表示D中二个结点之间的关系（对应树形表示法的一条连线），即二元组中第一个结点是第二个结点的前驱，第二个结点是第一个结点的后继。

如图7.1.1所示的树，若用二元组表示，则D和R分别为：

D＝｛A，B，C，D，E，F，G，H，I，J，K，L，M，N｝

R＝｛〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈B，F〉，〈B，G〉，〈F，L〉，〈C，H〉，〈C，I〉，〈D，J〉，〈D，K〉，〈K，M〉，〈K，N〉｝

这种表示法可以对树进行形式化的描述，但不如树形表示法一目了然。

三、文氏图（或集合图）表示法

每棵树对应一个圆形，圆内包含根结点和子树的圆形，同一个根结点下的各子树对应的圆形是不能相交的。

这种方法表示的树中，结点之间的关系是通过圆形的包含来表示的。

以图7.1.1所示的树为例，其文氏图表示如图7.1.3所示。

四、凹入表示法

每棵树的根对应着一条形，子树的根对应着一个较短的条形，且树根在上，子树的根在下，同一个根下的各子树的根对应的条形长度是一样的。

这种方法表示的树中，结点之间的关系是通过条形的长度和位置表示的，以图7.1.1所示的树为例，其凹入表示如图7.1.4所示。

图7.1.3树的文氏图表示实例图7.1.4树的凹入表示实例

五、嵌套括号（或广义表）表示法

每棵树对应一个由根作为名字的表，表名放在表的左边，表是在一个括号里的各子树对应的表组成的，之间用逗号分开。

这种方法表示的树中，结点之间的关系是通过括号的嵌套表示的。

如图7.1.1所示的树，用嵌套括号表示如下：

A（B（E，F（L），G），C（H，I），D（J，K（M，N）））

嵌套括号表示是树的一种树的线性表示，它可以用一个字符串来给出，在实现树的存储结构中，可作为输入数据。

7.1.4树的性质

一、性质1树中的结点数等于所有结点的度数加1。

证明：

根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数（度数），从而可得树中的结点数等于所有结点的度数加1。

二、性质2度为m的树中第i层上至多有mi-1个结点（i≥1）。

用数学归纳法证明：

对于第一层，因为树中的第一层上只有一个结点，即整个树的根结点，而由i＝1代入mi-1，得mi-1＝m1-1＝m0＝1，也同样得到只有一个结点，显然结论成立。

假设对于第（i－1）层（i＞1）命题成立，即度为m的树中第（i－1）层上至多有mi-2个结点，则根据树的度的定义，度为m的树中每个结点至多有m个孩子，所以第i层上的结点数至多为第（i－1）层上结点数的m倍，即至多为mi-2×m＝mi-1个，这与命题相同，故命题成立。

三、性质3深度为h的m叉树至多有

个结点。

证明：

由性质2可知，第i层上最多结点数为mi-1（i＝1，2，…，h），显然当深度为h的m叉树（即度为m的树）上每一层都达到最多结点数时，整个m叉树具有最多结点数，因此有：

整个树的最多结点数＝每一层最多结点数之和

＝m0＋m1＋m2＋…＋mh-1

＝

当一棵m叉树上的结点数等于（mh-1－1）/（m－1）时，则称该树为满m叉树。

例如，对于一棵深度为5的满二叉树，则结点数为25-1，即31；对于一棵深度为5的满三叉树，则结点数为（35-1）/（3-1），即121。

四、性质4具有n个结点的m叉树的最小深度为logm（n（m－1）＋1）。

证明：

设具有n个结点的m叉树的深度为h，若在该树中前h－1层都是满的，即每一层的结点数都等于mi-1个（1≤i≤h－1），第h层（即最后一层）的结点数可能满，也可能不满，则该树具有最小的深度，其深度h可计算如下：

根据性质3可得：

＜n≤

乘上（m－1）后得：

mh-1＜n（m－1）＋1≤mh

以m为底取对数后得：

h－1＜logm（n（m－1）＋1）≤h

即logm（n（m－1）＋1）≤h＜logm（n（m－1）＋1）＋1

因h只能取整数，所以h＝logm（n（m－1）＋1）

结论得证。

例如，对于二叉树，求最小深度的计算公式为log2（n＋1），若n＝20，则最小深度为5；对于三叉树，求最小深度的计算公式为log3（2n＋1），若n＝20，则最小深度为4。

7.2树的存储结构

树是一种非线性结构，不论采用哪种存储方式，都必须把树中各结点之间存在的非线性关系反映出来，显然用线性表的存储方法来存储树是不合适的。

树的存储方式有顺序存储和链式存储，由于链式存储更容易表现结点之间关系，故采用链式存储方式居多。

在链式存储方式中，又有定长结点表示和不定长结点的表示之分，采用不定长结点的表示可以节省存储开销，但会造成某些运算的不便，采用定长结点的表示的情况正好相反。

采用哪种存储方式主要取决于要对树结构进行什么样的处理。

下面介绍的是树的定长结点表示的链式存储方式中的三种存储结构：

标准形式、逆形式和扩充标准形式。

一、结点的一般形式

在树的链式存储结构中，结点的一般形式如图7.2.1所示。

data

pointers

图7.2.1树的结点的一般形式

其中data部分存放结点的值，在一般情况下，结点的值可以有n（n＞1）个分量，故可以用n个字段存放结点值的n个分量。

在这n个分量中，通常有一个分量能够识别所有结点，称此分量为键（或关键码）。

在今后的讨论中，为方便起见，若没有特别指明，仅考虑结点的键，而略去结点的其它分量。

这样，只要用一个字段存放结点的值就可以了。

pointers是结点的指针部分，它可以由若干个指针组成，每个指针用来体现树中各结点之间所存在的一种特定的非线性关系。

二、树的标准形式存储结构

1．结点的结构其形式如图7.2.2所示。

data

pointers

图7.2.2标准形式存储结构的结点的一般形式

其中，data部分如上所述，而pointers是一组指针，对于一棵度为m的树，pointers有m个字段，存放后继结点的所在地址。

因而，在树的标准形式存储结构中，结点的更一般形式如图7.2.3所示。

data

child0

child1

…

childm-1

图7.2.3度为m的树的按标准形式存储的结点结构

2．C语言中的结点的类型定义

#defineM5/*M为树的度*/

typedefstructnode{chardata;

structnode*child[M];

}NODE；

3．链接方法对于一棵度为m的树中的每一个结点，不管其度t（t≤m）为多少都采用图7.2.3的结构形式存放，并让child0指向第1棵子树的根，child1指向第2棵子树的根，…，childt-1指向第t棵子树的根，如果t＜m，则把没用的字段childt，childt+1，…，childm-1置空，设置一指针指向根结点。

4．实例图7.1.1所示的树，若按标准形式存储，则其结构如图7.2.4所示。

图7.2.4树的标准形式存储结构示例

5．按标准形式存储的一般树的创建程序函数creat_tree（），实现了由树的嵌套括号表示建立一棵按标准形式存储的m次树的功能。

其中参数s为一个字符串并用'\0'标识结束，用以存放嵌套括号表示；m为树的度。

#include

#include

#defineM3/*M为树的度*/+

#defineN100/*N为字符串最大长度*/

structnode{chardata;/*定义树的结点*/

structnode*child[M];

}

typedefstructnodeNODE;

char[N];

intm;

NODE*creat_tree（s,m）

chars[];/*用嵌套括号表示的树的字符串*/

intm;/*m为树的度结点*/

{NODE*stack[N],*p=NULL,*q;/*p指向当前结点，q指向父结点*/

charch;/*存当前处理字符*/

inti,k=0,top=0;/*初始化堆栈及字符位置*/

ch=s[0];/*取一字符为当前处理字符*/

while（ch!

='\0'）/*字符串还未处理结束*/

{if（isalpha（ch））/*若当前字符为字母*/

{p=（NODE*）malloc（sizeof（NODE））;

p->data=ch;/*以当前字符为值建立一新结点*/

for（i=0;i

p->child[i]=NULL;

}

else/*当前字符不是字母*/

switch（ch）

{case'（':

stack[top++]=p;/*当前结点进栈*/

break;

case',':

q=stack[top-1];/*取栈顶结点（不出栈）为父结点*/

i=-1;

while（q->child[++i]!

=NULL）;/*找空的指针域*/

q->child[i]=p;/*把当前结点作为孩子进行链接*/

break;

case'）':

q=stack[--top];/*取栈顶结点（出栈）为父结点*/

i=-1;

while（q->child[++i]!

=NULL）;/*找空的指针域*/

q->child[i]=p;/*把当前结点作为孩子进行链接*/

p=q;/*取父结点为当前结点*/

}

ch=s[++k];/*取下一字符为当前处理字符*/

}

return（p）;/*返回树的根结点的地址*/

}

三、树的逆形式存储结构

1．结点的结构其形式如图7.2.5所示。

data

parent

图7.2.5逆形式存储的结点的结构

其中，data部分如上所述，而parent是一指针，用来指向双亲结点。

因树中结点最多有一个前件，所以parent指针只需要一个字段。

2．C语言中的结点的类型定义

typedefstructr_node{chardata;

structr_node*parent

}R_NODE；

3．链接方法对于树中的每一个结点，都采用图7.2.5的结构形式存放，用parent存放结点的双亲所在地址。

特别地，根结点没有双亲结点，可在根结点的parent字段置空。

并设置一指针指向根结点。

4．实例图7.1.1所示的树，若按逆形式存储，则其结构如图7.2.6所示。

图7.2.6树的逆形式存储结构示例

四、树的扩充标准形式存储结构

1．结点的结构扩充标准形式存储结构是上述两中存储结构的组合，它的结点同时具有述两中存储结构的结点的内容。

对于一棵度为m的树，扩充标准形式存储结构的结点的一般形式如图7.2.7所示。

data

child0

child1

…

childm-1

parent

图7.2.7度为m的树的按扩充标准形式存储的结点结构

其中，data部分如上所述，childi（0＜i＜m）存放后继结点的所在地址，而parent是一指针，用来指向双亲结点。

2．C语言中的结点的类型定义

typedefstructE_node{chardata;

structe_node*child[M];

structe_node*parent

}E_NODE；

3．链接方法对于树中的每一个结点，都采用图7.2.7的结构形式存放，其中，childi（0＜i＜m）的链接方法同标准形式存储结构的链接方法，而parent链接方法同逆形式存储结构的链接方法。

4．实例对于图7.1.1所示的树，若按扩充标准式存储，则其结构如图7.2.8所示。

图7.2.8树的扩充标准形式存储结构示例

7.3树的基本运算

7.3.1树的基本运算概述

树的基本运算有下列几种：

（1）初始化SETNULL（T）置T为空树。

（2）求根结点ROOT（x）或ROOT（T）求结点x所在树的根结点，或者求树T的根结点。

若x不在任何一棵树上或T是空树，则函数值为“空”。

（3）找双亲结点PARENT（T，x）求树T中结点x的双亲结点。

若结点x是T的根结点或x不在树T中，则函数值为“空”。

（4）找孩子结点CHILD（T，x，i）求树T中结点x的第i个孩子结点。

若结点x无第i个孩子，则函数值为“空”。

（5）找兄弟结点RIGHTSIBLING（T，x）求树T中结点x右边的兄弟。

若没有找到，则函数值为“空”。

（6）生成树CREATE（x，F）生成一棵以x结点为根、以森林F为子树森林的树。

（7）插入子树ADDCHILD（T，x，i，S）把结点S为根的树置为树T中结点x的第i棵子树。

若原树中无结点x或结点x的子树个数小于（i－l），则空操作。

（8）删除子树DELCHIID（T，x，i）删除树T中结点x的第i棵子树。

若无结点x或结点x的子树个数小于i，则空操作。

（9）遍历TRAVERSE（T）按某个次序依次访问树中各个结点，并使每个结点只被访问一次。

对于上述的运算，我们不能一一细述，下面以树遍历的实现为例来说明树的处理方法。

7.3.2树的遍历

一、树的遍历概念

使用树结构时，常常需要按某种次序获得树的所有结点，这就是遍历，具体地说，就是按某个次序依次访问树中各个结点，并使每个结点只被访问一次。

对树进行一次遍历就产生树中所有结点的一个线性序列。

二、树的遍历方法

遍历树的目的在于得到树中各结点的一种线性顺序，使非线性的树线性化，从而简化有关的运算和处理。

遍历一个线性结构很容易，只须从开始结点出发顺序扫描每个结点即可。

但是树是一个非线性结构，每个结点可以有多个后继结点，要得到树中各结点的一种线性排列，就不那么容易了。

因此需寻找一种规律来系统地访问树中各结点。

根据树的根结点和各棵子树的关系、树的层次关系及叶子结点的特性，可以的归纳出如下几种常见的遍历方法：

1．树的前序遍历首先访问根结点，然后再按前序遍历根结点的各棵子树。

2．树的后序遍历首先按后序遍历根结点的各棵子树的结点，然后再访问根结点。

3．树的层次遍历首先访问第一层上的根结点；然后访问第二层上的结点；再访问第三层上的结点；再依此访问以下各层的结点。

4．获得树中所有叶子结点如果树中只有一个结点，则此结点就是此树的叶子结点；否则，树中的叶子结点就是根结点的各棵子树的叶子结点。

三、遍历序列的唯一性

对于有序树来说，由于树的子树总是从左到右规定为“第一棵子树”、“第二棵子树”、……，所以访问树中的结点时，总是从左到右遍历各棵子树的。

对于按层次遍历来说，在同一层上，也是从左到右遍历的。

因此，以上各种遍历方法所得到的结点序列是唯一的。

四、实例

根据以上各种遍历方法，可得到图7.1.1所表示的树的各种遍历序列如下：

前序遍历结点序列：

A，B，E，F，L，G，C，H，I，D，J，K，M，N；

后序遍历结点序列：

E，L，F，G，B，H，I，C，J，M，N，K，D，A；

层次遍历结点序列：

A，B，C，D，E，F，G，H，I，J，K，L，，M，N；

树中叶子结点序列：

E，L，G，H，I，J，M，N。

五、遍历方法的实现程序

下面给出用递归和非递归（使用栈）两种实现前序遍历的方法和用队列（非递归）实现层次遍历的方法。

其它遍历方法的实现可参考这些方法。

在下面的程序中，假设给定的树的度是m，树中的结点值是字符，并按照标准形式存贮，树的结点的类型NODE的说明见7.2二。

1．用递归实现前序遍历因为树的前序遍历的定义是递归的，所以用递归的程序实现树的前序遍历是方便的。

下面C语言递归函数pre1_traverse（T，m）是实现对给定的m次树T的前序遍历。

voidpre1_traverse（T,m）

NODE*T;

intm;

{inti;

if（T!

=NULL）

{printf（"%c",T->data）;/*输出根结点的值*/

for（i=0,i