树和二叉树的基本知识.docVIP

PAGE

PAGE2

Jsoi2006春季函授B层次讲义（3）常州市第一中学林厚从NUMPAGES19

PAGE

PAGE2

Jsoi2006春季函授B层次讲义（3）常州市第一中学林厚从PAGE1/NUMPAGES19

树和二叉树的基本知识

树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如把一个家族看作为一棵树，树中的结点为家族成员的姓名及相关信息，树中的关系为父子关系，即父亲是儿子的前驱，儿子是父亲的后继；把一个国家或一个地区的各级行政区划分看作为一棵树，树中的结点为行政区的名称及相关信息，树中的关系为上下级关系，如一个城市包含有若干个区，每个区又包含有若干个街道，每个街道又包含有若干个居委会；把一本书的结构看作是一棵树，树中的结点为书、章、节的名称及相关信息，树中的关系为包含关系。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构；在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。

在树型结构中，二叉树是最常用的结构，它的分支个数确定，又可以为空，具有良好的递归特性，特别适宜于程序设计，因此我们常常将一般树型结构转换成二叉树进行处理。

第一节树

一、树的定义

一棵树（tree）是由n（n0）个元素组成的有限集合，其中：

1．每个元素称为结点(node)；

2．有一个特定的结点，称为根结点或树根（root）；

3．除根结点外，其余结点被分成m（m=0）个互不相交的有限集合T0,T1,T2,……Tm-1，而每一个子集Ti又都是一棵树（称为原树的子树subtree）。

图1

图1就是一棵典型的树结构。从树的定义可以看出：

1．树是递归定义的，这就决定了树的操作和应用大都是采用递归思想来解决；

2．一棵树中至少有1个结点，这个结点就是根结点，如上图中的结点1；

3．只有根结点没有前趋结点，其余每个结点都有唯一的一个前趋结点；

4．所有结点都可以有0或多个后继结点；

二、树的基本概念

下面以图1为例给出树结构中的一些基本概念：

1．一个结点的子树个数，称为这个结点的度（degree），如结点1的度为3，结点3的度为0。度为0的结点称为叶结点（又称树叶leaf，如结点3、5、6、8、9）。度不为0的结点称为分支结点（如结点1、2、4、7）。根结点以外的分支结点又称为内部结点（如结点2、4、7）。树中各结点的度的最大值称为这棵树的度（又称宽度），图1所示这棵树的（宽）度为3。

2．在用上述图形表示的树结构中，对两个用线段（称为树枝）连接的相关联的结点，称上端的结点为下端结点的父结点，称下端的结点为上端结点的子结点，称同一个父结点的多个子结点为兄弟结点。如结点1是结点2、3、4的父结点，结点2、3、4都是结点1的子结点，它们又是兄弟结点，同时结点2又是结点5、6的父结点。称从根结点到某个子结点所经过的所有结点为这个子结点的祖先。如结点1、4、7是结点8的祖先。称以某个结点为根的子树中的任一结点都是该结点的子孙。如结点7、8、9都是结点4的子孙。

3．定义一棵树的根结点的层次（level）为1，其它结点的层次等于它的父结点的层次数加1。如结点2、3、4的层次为2，结点5、6、7的层次为3，结点8、9的层次为4。一棵树中所有结点的层次的最大值称为树的深度（depth），图1所示这棵树的深度为4。

4．若树中各结点的子树是按照一定的次序从左向右安排的，它们之间的次序不能互换，这样的树称之为有序树，否则称之为无序树。所以，树虽然是非线性结构，但也是有序结构。例如，对于下面图2中的两棵树，若看作为无序树，则是相同的；若看作为有序树，则是不同的，因为根结点A的两棵子树的次序不同。又如对于一棵反映了父子关系的家族树，兄弟结点之间是按照排行大小而有序排列的，所以它是一棵有序树。因为任何无序树都可以当作具有任一次序的有序树来处理，所以下面如果不特别指明，均认为树是有序的。

图2

5.对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1。如图1中，结点1和结点8之间存在着一条路径，并可用（1、4、7、8）表示这条路径，该条路径的长度为3。从根结点出发，到树中的其余结点一定存在着一条路径。注意，不同子树上的结点之间不存在路径。但是，如果把树看成是一个图的话(可以把树理解为是图的一个子类)，那么我们就可以继承图的路径的定义，认为