一、树

再对树的存储结构设计以及相关操作(遍历)算法实现之前，需要对树的定义和相关术语要有所了解，下面分别对这些进行简单的介绍

1. 树的定义

树：n (n ≥ 0 )个结点的有限集合，当n = 0时，称为空树;任意一棵非空树T满足以下条件︰

• 有且仅有一个特定的称为根的结点;
• 当n > 1时，除根结点之外的其余结点被分成m ( m > 0）个互不相交的有限集合 T1,T2… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。

互不相交的具体含义是什么?

结点： 结点不能属于多个子树

边： 子树之间不能有关系

如下所示的都是相交的，故不是树

2. 树的基本术语

结点的度： 结点所拥有的子树的个数

树的度： 树中各结点度的最大值

叶子结点： 度为 0 的结点，也称为终端结点

分支结点： 度不为 0 的结点，也称为非终端结点

如下所示的树，

• 结点A有两个子树B,C,故结点A的度为2。
• 树中最大的度为B，即有三个子树，故树的度为3。
• 红色结点的度为0，故红色结点是叶子节点，也叫终端结点。
• 非红色结点的度不为0，故非红色结点的为非终端结点。

孩子： 树中某结点的子树的根结点称为这个结点的孩子结点

双亲： 这个结点称为它孩子结点的双亲结点

兄弟： 具有同一个双亲的孩子结点互称为兄弟

如下所示的图，结点B是结点A的孩子结点，反之，结点A是结点B双亲结点，结点C和结点B互为兄弟

类比法：

• 在线性结构中，逻辑关系表现为前驱——后继
• 在树结构中，逻辑关系表现为双亲——孩子

路径： 结点序列 n1, n2, …, nk 称为一条由 n1 至 nk 的路径，当且仅当满足如下关系：结点 ni是 ni+1 的双亲（1<=i<k）

路径长度： 路径上经过的边的个数

祖先、子孙： 如果有一条路径从结点 x 到结点 y， 则 x 称为 y 的祖先，而 y 称为 x 的子孙

如下所示的图中

• 结点序列A,B,E,H称为一条由A到H的一条路径
• 路径上经过的边为3，故路径长度为3

在树结构中，路径是唯一的

结点所在层数： 根结点的层数为 1；对其余结点，若某结点在第 k 层，则其孩子结点在第 k+1 层

树的深度（高度）： 树中所有结点的最大层数

树的宽度： 树中每一层结点个数的最大值

如下图所示

3. 树的遍历

什么是遍历？线性结构如何遍历？

简言之，遍历是对数据集合进行没有遗漏、没有重复的访问

树的遍历： 从根结点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次

3.1 先序遍历

若树为空，则空操作返回；否则

• 访问根结点
• 从左到右前序遍历根结点的每一棵子树

例如如下图的前序遍历序列为：A，B，D，H，I，E，J，C，F，K，G

3.2 后序遍历

若树为空，则空操作返回；否则

• 从左到右后序遍历根结点的每一棵子树
• 访问根结点

3.3 层序遍历

从树的根结点开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问

4. 树的存储结构

实现树的存储结构，关键是什么?

如何表示树中结点之间的逻辑关系

什么是存储结构?

数据元素及其逻辑关系在存储器中的表示

树中结点之间的逻辑关系是什么?

思考问题的出发点：如何表示结点的双亲和孩子

4.1 双亲表示法

用一维数组存储树中各个结点（一般按层序存储）的数据信息以及该结点的双亲在数组中的下标

4.1.1 代码实现

4.1.1.1 树的存储结构设计

结点数据结构

树的数据结构及初始化

以下给出的代码都是Tree类的成员方法

4.1.1.2 树的建立

树的建立

需要提供一个方法在数组中添加树的结点，由于此时树为空，因此还没有树的结点的双亲，故此方法是只需要添加树的结点的数据域，而不需要添加结点的双亲域，代码如下

当添加完树的结点的数据后，数组就有了树的结点的双亲，因此需要一个函数来添加树的结点的双亲域来找到双亲的位置，代码如下

4.1.1.3 树的递归遍历算法设计（先序，后序)

树的递归遍历

先序遍历

根据树先序遍历的操作定义，访问根结点的操作发生在该结点的子树遍历之前，所以，先序遍历的递归实现只需将输出操作System.out.print放到递归遍历子树之前即可，代码如下

后序遍历

根据树后序遍历的操作定义，访问根结点的操作发生在该结点的子树均遍历完毕，所以，后序遍历的递归实现只需将输出操作System.out.print放到递归遍历子树之后即可，代码如下

4.1.1.4 队列实现层序遍历

层序遍历(队列实现)

在进行层序遍历时,结点访问应遵循“从上至下、从左至右”逐层访问的原则,使得先被访问结点的孩子先于后被访问结点的孩子被访问。

为保证这种“先先”的特性,可应用队列作为辅助结构。首先根结点入队,队头出队,输出出队结点,出队结点的左右孩子分别入队，以此类推，直至队列为空

例如如下图的所示的树

层序遍历的执行过程如下所示

代码如下

4.1.1.5 测试

测试如下图树的先序遍历，后序遍历，层序遍历

测试代码

测试效果

4.1.2 复杂度分析

查找结点的双亲结点的时间复杂度： 数组每一个元素不仅存储的结点的数据，还存储了此结点的双亲在数组的下标，故查找当前结点的双亲结点的时间复杂度为O(1)

查找结点的孩子结点的时间复杂度： 由于数组并没有存储结点的孩子结点信息，要想找到结点的孩子结点，只能遍历数组，最坏情况下，时间复杂度为O(n)

总结： 显然双亲表示法适合与查找双亲结点，不适合与查找孩子结点，下面介绍一种适合查找孩子结点的孩子表示法，即时间复杂度为O(1)

4.2 孩子表示法

树的孩子表示法是一种基于链表+数组的存储方法,即把每个结点的孩子排列起来,看成一个线性表,且以单链表存储,称为该结点的孩子链表,所以n个结点共有n个孩子链表(叶子结点的孩子链表为空表)。

n个孩子链表共有n个头引用(头指针）,这n个头引用又构成了一个线性表,为了便于进行查找操作,可采用顺序存储(数组实现）。

最后,将存放n个头引用的数组和存放n个结点数据信息的数组结合起来,构成孩子链表的表头数组。

在孩子表示法中存在两类结点:孩子结点和表头结点,其结点结构如下图所示(表头数组的建立是以层序序列建立的)

4.2.1 代码实现

4.2.1.1 树的存储结构设计

孩子结点的数据结构

结点(表头结点)的数据结构

树的数据结构及初始化

以下给出的代码都是Tree类的成员方法

4.2.1.2 树的建立

树的建立（按层序序列建立)

4.2.1.3 树的递归遍历算法设计(先序，后序)

树的递归遍历（前序，后序)

树的遍历，只要紧扣定义，就很容易写出算法实现，这里就不再重复阐述定义了，代码如下

4.2.1.4 队列实现层序遍历

层序遍历（队列实现)

4.2.1.5 测试

测试代码

测试效果

4.2.2 复杂度分析

查找结点的孩子结点的时间复杂度: 由于数组除了存放结点的数据，还存放了该结点的孩子结点链表的头结点，因此查找孩子结点的时间复杂度为O(1）

查找结点的双亲结点的时间复杂度: 由于数组并没有存储结点的双亲结点的信息，因此查找结点的双亲结点，只能遍历数组，故时间复杂度为O(n)

总结: 显然孩子表示法适合与查找孩子结点，不适合与查找结点的双亲结点

4.3 孩子兄弟表示法(二叉链表)

链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针

4.3.1 代码实现

4.3.1.1 树的存储结构设计

结点数据结构

树的数据结构

以下给出的代码都是Tree类的成员方法

4.3.1.2 树的建立

4.3.1.3 树的递归算法设计(先序，后序)

先序遍历

紧扣先序遍历的定义，先输出根结点，再输出根结点的孩子，不难写出下面的代码

后序遍历

根据后序遍历的定义，先输出根结点的孩子结点，最后输出根结点，因此可以通过递归找到根结点的第一个孩子结点，若第一个孩子都没有，则该结点无孩子，直接输出该结点即可，最后再找出该结点的兄弟结点

4.3.1.4 队列实现层序遍历

4.1.1.5 测试

测试代码

测试效果

总结:孩子兄弟表示便于实现树的各种操作，例如，若要访问某结点x的第i个孩子，只需从该结点的第一个孩子指针找到第一个孩子后，沿着孩子结点的右兄弟域连续走i - 1步，便可找到结点x的第i个孩子

4.3.2 其他操作算法实现

要求

以孩子兄弟表示法做存储结构，求树中结点 x 的第 i 个孩子。

算法实现

先在链表中进行遍历，在遍历过程中查找值等于 x 的结点，然后由此结点的最左孩子域 firstNode找到值为 x 结点的第一个孩子，再沿右兄弟域 rightNode 找到值为 x 结点的第 i 个孩子并返回指向这个孩子。

代码如下

测试

测试代码

测试效果

要求

以孩子兄弟表示法作为存储结构，编写算法求树的深度。

算法实现

采用递归算法实现。若树为空树，则其深度为 0，否则其深度等于第一棵子树的深度+1 和兄弟子树的深度中的较大者。具体算法如下：

5. 线性结构和树结构的比较

线性结构

• 开始结点（只有一个）：无前驱
• 终端结点（只有一个）: 无后继
• 其它元素：一个前驱,一个后继

关系：一对一

如下所示

树结构

根结点（只有一个）：无双亲

叶子结点(可以有多个)：无孩子

其它结点：一个双亲,多个孩子

关系：一对多

如下所示