1. 一般树¶

1.1. 一般树¶

许多组织在本质上都是层级式的，例如军队和大多数企业。设想一家公司，有一位总裁和若干向总裁汇报的副总裁。每位副总裁又有若干直接下属，依此类推。如果我们想用数据结构来为这家公司建模，自然会想到把总裁放在树的根结点，把副总裁放在第 1 层，而他们的下属则随着我们沿组织层级向下，位于树中更低的层。

由于副总裁的人数很可能多于两人，这家公司的组织结构无法用二叉树方便地表示。我们需要改用一种其结点拥有任意数量子结点的树。遗憾的是，当我们允许树中的结点拥有任意数量的子结点时，它们会比二叉树难实现得多。本章将讨论这样的树。为了把它们与二叉树区分开，我们使用术语一般树。

本模块将考察一般树的术语，并定义一种用于一般树的基本 ADT。

1.1.1. 一般树的定义与术语¶

一棵树 \(\mathbf{T}\) 是一个由一个或多个结点组成的有限集合，其中有一个被指定的结点 \(R\) ，称为 \(\mathbf{T}\) 的根。如果集合 \((\mathbf{T} -\{R\})\) 非空，则这些结点被划分为 \(n > 0\) 个不相交的集合 \(\mathbf{T}_0\) 、 \(\mathbf{T}_1\) 、……、 \(\mathbf{T}_{n-1}\) ，其中每一个都是一棵树，而它们各自的根 \(R_1, R_2, ..., R_n\) 都是 \(R\) 的子结点。子集 \(\mathbf{T}_i (0 \leq i < n)\) 被称为 \(\mathbf{T}\) 的子树。这些子树是有序的，即若 \(i < j\) ，则称 \(\mathbf{T}_i\) 排在 \(\mathbf{T}_j\) 之前。按照约定，子树自左向右排列，子树 \(\mathbf{T}_0\) 称为 \(R\) 最左边的子结点。一个结点的出度是该结点的子结点数目。森林是一棵或多棵树的集合。图 18.1.1 给出了由二叉树记法推广而来的更多树记法。

树中的每个结点都恰好有一个父结点，根结点除外，它没有父结点。由这一观察立刻可知，一棵有 \(n\) 个结点的树必定有 \(n-1\) 条边，因为除根结点外，每个结点都有一条边把它与其父结点相连。

1.1.2. 一般树结点的 ADT¶

在讨论一般树的实现之前，我们应当先明确这类实现必须支持哪些操作。任何实现都必须能够初始化一棵树。给定一棵树，我们需要访问该树的根。还必须有某种方式访问一个结点的子结点。在二叉树结点的 ADT 中，这是通过提供显式访问左、右子结点指针的成员函数来实现的。遗憾的是，由于我们事先不知道一般树中某个给定结点会有多少个子结点，无法提供显式函数来访问每一个子结点。必须找到一种适用于未知数量子结点的替代方案。

一种选择是提供一个函数，以所需子结点的下标作为参数。把它与一个返回给定结点子结点数目的函数结合起来，就能支持访问任意结点或处理一个结点的所有子结点。遗憾的是，这种访问方式往往会使结点实现的选择偏向基于数组的方法，因为这些函数更利于对子结点线性表进行随机访问。实践中，基于链表的实现往往更受青睐。

另一种做法是提供对一个结点的第一个（即最左边）子结点的访问，以及提供对一个结点的下一个（即右边）兄弟结点的访问。下面是一般树及其结点的类声明。基于这两个访问函数，一个结点的子结点可以像线性表一样遍历。试图查找最右边兄弟结点的下一个兄弟结点将返回 null 。

// General tree node ADT
public interface GTNode {
  public Object value();
  public boolean isLeaf();
  public GTNode parent();
  public GTNode leftmostChild();
  public GTNode rightSibling();
  public void setValue(Object value);
  public void setParent(GTNode par);
  public void insertFirst(GTNode n);
  public void insertNext(GTNode n);
  public void removeFirst();
  public void removeNext();
}

// General tree ADT
public interface GenTree {
  public void clear();      // Clear the tree
  public GTNode root();     // Return the root
  // Make the tree have a new root, give first child and sib
  public void newroot(Object value, GTNode first, GTNode sib);
  public void newleftchild(Object value); // Add left child
}

1.1.3. 一般树的遍历¶

对于二叉树，有三种传统的树的遍历：前序遍历、后序遍历和中序遍历。对于一般树，前序和后序遍历的定义与二叉树的对应遍历含义相似。一般树的前序遍历先访问树的根，然后自左向右对每棵子树进行前序遍历。一般树的后序遍历先自左向右对根的子树进行后序遍历，然后访问根。中序遍历对于一般树没有自然的定义，因为内部结点没有固定的子结点数目。可以人为发明一种任意的定义—例如先中序遍历最左边的子树，然后访问根，再中序遍历其余的子树—。然而，中序遍历对一般树通常没有用处。

Settings

Saving...

Server Error
Resubmit

要执行前序遍历，必须自左向右访问给定结点（比如 \(R\) ）的每一个子结点。做到这一点的方法是，从 R 最左边的子结点（称为 \(T\) ）开始。从 \(T\) 出发，我们可以移动到 \(T\) 的右兄弟结点，然后再移动到该结点的右兄弟结点，依此类推。