扫码获取更多资源

●树的抽象数据类型

ADT Tree (

Data:

具有相同类型的数据元素的集合，称为结点集。

Relation：

如果Data为空集，则称为空树；

如果Data仅含一个数据元素，则R为空集，否则R= {H},H是如下二元关系：

(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；

(2)如果D - {root) 乂中,则存在D - { root}的一个划分Dx z D2, - , Dm (m > 0),对任意的j A k(lG H;

(3) 对应于 D - { root}的划分，H - (< root, x1 >, ... / < root, % >}有唯一的一个划分 ， H2Z -,HB(m>0)z 对任意的 j/k (l

是0上的二元关系，("，{'})是一棵符合本定义的树，称为根root的子树。

树的应用非常广泛，在不同的软件系统中树的基本操作也不尽相同。针对具体的应用， 需要重新定义其基本操作。

树的遍历

在ADT Tree定义的基本操作中，最基本的操作就是TraverseTree,即树的遍历。树的 遍历是指从根结点出发，按某种次序依次访问树中的所有结点，使得每个结点均被访问且仅 访问一次。“访问”是一种抽象操作，其含义很广：在实际应用中，访问可以是对结点进行的 各种处理，例如输出结点的信息、修改结点的某些数据等；对应到算法上，访问可以是一条 简单语句，可以是一个复合语句，也可以是一个模块。 假设一棵树中存储着有关学生情况的信息，每个结点含有学号、姓名、性别、年龄等信 息，管理和使用这些信息时可能需要做这样一些工作：

①将每个人的六位学号“15 **** ”改为八位“2015 **** ”；

②打印每位学生的姓名和性别；

③求男学生的总人数和女学生的总人数。

对于①，“访问”的含义是对学号进行修改操作；对于②，“访问”的含义是打印每一个结 点的部分信息；对于③，“访问”的含义只是统计。但不管访问的具体操作是什么，都必须做 到既无重复，又无遗漏。

对于线性结构来说,遍历是一个容易解决的问题，只要按照结构原有的线性顺序，从第 一个元素起依次访问各元素即可。然而在树中却不存在这样一种自然顺序，因为树是非线 性结构，每个结点都可能有多棵子树，因而需要寻找一种规律，以便使二叉树中的结点能够 排列在一个线性队列上，从而便于遍历。

不失一般性，在此将“访问”定义为输出结点的信息，因此通过遍历，可以使树中结点变 成某种意义上的线性序列。

由树的定义可知，一棵树由根结点和m棵子树构成，因此，只要依次遍历根结点和m 棵子树，就可以遍历整棵树。通常有下面三种“搜索路径”。

先序遍历

先序遍历的定义：如果树为空，则空操作返回；否则，访问根结点，然后按照从左到右 的顺序先序遍历根结点的每一棵子树。

例如，对图6-2(a)所示的树进行先序遍历，其结果为：ABDEIFCGHO

后序遍历

后序遍历的定义：如果树为空，则空操作返回；否则，按照从左到右的顺序后序遍历根

结点的每一棵子树，然后访问根结点。

例如，对图6-2(a)所示的树进行后序遍历，结果为：DIEFBGHC Ao

层序遍历

层序遍历的定义：从树的第一层(即根结点)开始，自上而下逐层遍历；在同一层中，按 从左到右的顺序对结点逐个访问。树的层序遍历也称为树的广度遍历。

例如，对图6-2(a)所示的树进行层序遍历，结果为：ABCDEFGHL

联系我们：