假期连载之十
(树形结构—树的基本概念及抽象数据类型)
树形结构的亮点在于其应用广泛。尽管本节仅介绍概念以及理论上的内容，但无论如何都不能忽视对实际应用的渗入，否则将失去其本身研究的意义。
树的基本概念
在计算机科学中，树作为组织信息的重要形式之一，代表了非线性数据结构的一般特征。这里有两种基本的树，一种被称为自由树free tree。
自由树指定义一个二元组Tf=(V,E)，其中V={v1,v2,…,vn}是由n个结点构成的优先集合(n>=0)，称为顶点集合vertex，vi称为顶点，其中1<=i<=n。E={(vi,vj)|vi,vj属于V，且i>=1,j<=n}是由n-1个元素组成的序对集合，称为边集合。E中的元素(vi,vj)为边edge的分支branch。E使得Tf成为一个连通图。综上可知，自由树的概念类似于图，且对其讨论的范围仅限于图论部分的内容，本文不作涉及。
另一种树称为有根树rooted tree。一棵有根树T，简称为树，它是由n>=0个结点的有限集合。当n=0时，T称为空树，否则T是非空树，记作：
Φ, n=0
T={r,T1,…,Tn},n>0
其中r是T的一个特殊结点，称为根root。T1,…,Tn是除r之外其它结点构成的互不相交的m>=0个子集合。每个子集合也是一棵树，称为根的子树subtree。
每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继，m称为r的分支数。
在计算机系统和其它领域中，树的表示方法不尽相同。基本上有以下几种方法：
1、 倒置树结构，即最常用的树形表示方法。
2、 文氏图表示法，使用嵌套集合的形式。
3、 广义表形式，即嵌套括号的表示方法。
4、 凹入表示法，用位置的缩进表示其层次，如目录表的编排格式。
树的一些基本术语
结点node，包含一个数据元素及若干指向其它结点的分支信息。
结点的度degree，是一个结点所拥有的子树的棵数。
叶结点leaf，指度为0的结点，也称为终端结点。
分支结点branch，除叶结点以外的其它结点，也称为非终端结点。
结点层次level，从根结点开始，根结点层次为1，根结点的直接后继层次为2，依次类推。
结点的层序编号No.of node，是指按从上层到下层，同层从左至右的顺序对结点以自然数编号。
树的度degree，树中所有结点度的最大值。
树的高度height，树中所有结点层次的最大值。
有序树ordered tree，在树T中，若各子树Ti之间是有先后次序的，称为有序树。
森林forest，指m>=0棵不相交的树的集合。
同构isomorphism，对于两棵树，通过对结点适当地重命名，就可以使两棵树完全相等，则称这两棵树同构。
为了描述结点之间层次关系，我们还借助人类家族术语进行定义：
子女结点child，一个结点的直接后继称为这个结点的child。
父结点parent，一个结点的直接前驱称为这个结点的parent。
兄弟结点sibling，同一双亲结点的子女结点之间互称为sibling。
祖先结点ancestor，一个结点的祖先结点是指从根结点到该结点路径上的所有结点。
子孙结点descendant，一个结点的直接后继和间接后继称为该结点的子孙结点。
另外，按照结点序号的大小，结点又可以前辈、后辈表示，父结点为兄弟结点的子女结点之间互称为堂兄弟结点。
树的抽象数据类型
ADT Tree
{
数据对象D:一个集合，该集合中的所有元素具有相同特性
数据关系R:见树的定义
基本操作:
InitTree(Tree); //初始化Tree为空树
DestoryTree(Tree); //销毁树
CreateTree(Tree); //创建树Tree
TreeEmpty(Tree); //若Tree为空，返回TRUE，否则返回FALSE
Root(Tree); //返回树Tree的根
Parent(Tree,x); //树Tree存在，x是Tree中的某个结点，若x为非根结点，则返回其父结点，否则返回空
FirstChild(Tree,x); //树Tree存在，x是Tree中的某个结点，若x为非叶结点，则返回其第一个孩子结点，否则返回空
NextSibling(Tree,x); //树Tree存在，x是Tree中的某个结点，若x为不是父结点的最后一个子女结点，则返回其下一个兄弟结点，否则返回空
InsertChild(Tree,p,Child); //树Tree存在，p指向Tree中的某个结点，非空树Child与Tree不相交，将Child插入Tree中，其中p是该子树的根结点
DeleteChild(Tree,p,i); //树Tree存在，p指向Tree中的某个结点1<=i<=d，d为p所指向结点的度，删除Tree中p所指向结点的第i棵子树
TraverseTree(Tree,Visit()); //树Tree存在，Visit()是对结点进行访问的函数，按照某种次序对Tree的每个结点调用Visit()函数最多访问一次，若Visit()失败，则操作失败
}
鉴于树结构重要性，我们将本块内容分成多个连载分别进行讨论，方便读者进行整理。
(未完待续)