6.1　树的定义和基本术语

1.树的定义

树是一种常用的非线性结构，如图6－1所示。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n＝0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n＞1时，其余结点被分成m（m＞0）个互不相交的子集T1，T2，…，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。

·结点：数据元素的内容及其指向其子树根的分支统称为结点。

·结点的度：结点的分支数。

·终端结点（叶子）：度为0的结点。

·非终端结点：度不为0的结点。

·结点的层次：树中根结点的层次为1，根结点子树的根为第2层，依此类推。

·树的度：树中所有结点度的最大值。

·树的深度：树中所有结点层次的最大值。

·有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。

·森林：是m（m≥0）棵互不相交的树的集合。

图6－1 树的示例

在树结构中，结点之间的关系又可以用家族关系描述，定义如下：

·孩子、双亲：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。

·子孙：以某结点为根的子树中的所有结点都被称为是该结点的子孙。

·祖先：从根结点到该结点路径上的所有结点。

·兄弟：同一个双亲的孩子之间互为兄弟。

·堂兄弟：双亲在同一层的结点互为堂兄弟。

2.树的基本运算

常用操作如下：

（1）构造一棵树CreateTree（T）；

（2）清空以T为根的树ClearTree（T）；

（3）判断树是否为空TreeEmpty（T）；

（4）获取给定结点的第i个孩子Child（T，linklist，i）；

（5）获取给定结点的双亲Parent（T，linklist）；

（6）遍历树Traverse（T）。

对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依次从左到右按左右根的顺序访问每棵子树，最后访问根结点。

3.树的存储结构

（1）双亲表示法

树的双亲表示法主要描述的是结构点的双亲关系，如图6－2所示。

图6－2 树的双亲表示及存储结构

类型定义：

这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。

算法实现举例：

（2）孩子表示法

孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜，如图6－3所示。

图6－3 孩子结点关系的链式存储结构

在C语言中，这种存储形式定义如下：

这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。

获取给定结点第i个孩子的操作算法实现：

（3）孩子－兄弟表示法

孩子－兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为：

其中，firstchild为指向该结点第一个孩子的指针，nextsibling为指向该结点的下一个兄弟，elem是数据元素内容，如图6－4所示。

图6－4 树的孩子－兄弟表示及存储结构

在C语言中，这种存储形式定义如下：