Java 之道/树
tree ADT data structure
本章介绍了一种新的数据结构，称为树，它的一些用途和两种实现方法。
一个可能的混淆来源是 ADT、数据结构和 ADT 或数据结构实现之间的区别。没有通用的答案，因为在某一级是 ADT 的东西可能反过来是另一个 ADT 的实现。
diagram!implementation
为了帮助理清其中的一些内容，有时在 ADT 及其可能实现之间绘制一个图表以显示其关系是有用的。此图显示了树的两种实现方法
figure=figs/tree_adt.eps
图中的水平线代表 ADT 及其实现之间的抽象屏障。
node tree node cargo embedded reference implementation!Tree binary tree
与列表一样，树由节点组成。一种常见的树是二叉树，其中每个节点都包含对另外两个节点（可能为空）的引用。类定义如下所示
verbatim public class Tree
Object cargo; Tree left, right;
verbatim
与列表节点一样，树节点包含货物：在本例中是一个泛型对象。其他实例变量分别命名为 left 和 right，符合表示树的标准图形方式
figure=figs/tree1.eps
树的顶部（由树引用的节点）称为根。为了符合树的隐喻，其他节点被称为分支，具有空引用的尖端节点被称为叶子。我们可能觉得将根部绘制在顶部，叶子绘制在底部很奇怪，但这不是最奇怪的事情。
root node leaf node parent node child node level
更糟糕的是，计算机科学家将另一个隐喻混杂在一起：家谱。顶端节点有时被称为父节点，它引用的节点被称为其子节点。具有相同父节点的节点称为兄弟节点，等等。
最后，还有一种几何词汇用于描述树。我已经提到了 left 和 right，但也有“向上”（朝向父节点/根节点）和“向下”（朝向子节点/叶子）。另外，所有与根节点距离相同的节点构成了树的一层。
我不知道为什么我们需要三种隐喻来描述树，但事实就是这样。
tree!linked implementation
组装树节点的过程类似于组装列表的过程。我们有一个用于树节点的构造函数，用于初始化实例变量。
verbatim
public Tree (Object cargo, Tree left, Tree right)
this.cargo = cargo;
this.left = left;
this.right = right;
verbatim
我们首先分配子节点
verbatim
Tree left = new Tree (new Integer(2), null, null); Tree right = new Tree (new Integer(3), null, null);
verbatim
我们可以同时创建父节点并将其链接到子节点
verbatim
Tree tree = new Tree (new Integer(1), left, right);
verbatim
此代码产生了上一图所示的状态。
tree!traversal traverse
遍历树的最自然方法是递归。例如，要将树中的所有整数加起来，我们可以编写此类方法
verbatim
public static int total (Tree tree)
if (tree == null) return 0;
Integer cargo = (Integer) tree.cargo;
return cargo.intValue() + total (tree.left) + total (tree.right);
verbatim
这是一个类方法，因为我们希望使用 null 来表示空树，并将空树作为递归的基准情况。如果树为空，则该方法返回 0。否则，它进行两次递归调用以找到其两个子节点的总值。最后，它添加了自己的货物并返回总值。
tree!empty
虽然此方法有效，但在将其适应面向对象设计方面存在一些困难。它不应出现在 Tree 类中，因为它要求货物是 Integer 对象。如果我们在 Tree.java 中做出这种假设，那么我们将失去泛型数据结构的优势。
另一方面，此代码访问了 Tree 节点的实例变量，因此它“知道”它应该知道的比树的实现更多。如果我们稍后更改该实现（我们将这样做），此代码将失效。
在本章的后面，我们将开发解决此问题的方法，允许客户端代码遍历包含任何类型对象的树，而不会破坏客户端代码和实现之间的抽象屏障。在我们到达那里之前，让我们先看看树的应用。
tree!expression expression tree postfix infix
树是表示表达式结构的自然方式。与其他表示法不同，它可以明确地表示计算。例如，中缀表达式 1 + 2 * 3 是模糊的，除非我们知道乘法在加法之前发生。
下图表示相同的计算
figure=figs/tree2.eps
节点可以是操作数，如 1 和 2，也可以是运算符，如 + 和 *。操作数是叶子节点；运算符节点包含对其操作数的引用（所有这些运算符都是二元的，意味着它们正好有两个操作数）。
查看此图，毫无疑问操作顺序是什么：乘法首先发生以计算加法的第一个操作数。
像这样的表达式树有许多用途。我们将要查看的示例是从一种格式（后缀）到另一种格式（中缀）的转换。编译器内部使用类似的树来解析、优化和转换程序。
tree!traversal traverse recursion preorder postorder inorder
我已经指出递归提供了一种遍历树的自然方法。我们可以像这样打印表达式树的内容
verbatim
public static void print (Tree tree)
if (tree == null) return;
System.out.print (tree + " ");
print (tree.left);
print (tree.right);
verbatim
换句话说，要打印一棵树，首先打印根节点的内容，然后打印整个左子树，最后打印整个右子树。这种遍历树的方法称为前序遍历，因为根节点的内容出现在子节点内容之前。
对于示例表达式，输出为 + 1 * 2 3。这与后缀和中缀都不同；这是一种称为前缀的新表示法，其中运算符出现在其操作数之前。
你可能怀疑，如果我们以不同的顺序遍历树，我们将获得不同表示法的表达式。例如，如果我们先打印子树，然后打印根节点
verbatim
public static void printPostorder (Tree tree)
if (tree == null) return;
printPostorder (tree.left);
printPostorder (tree.right);
System.out.print (tree + " ");
verbatim
我们得到后缀表达式 (1 2 3 * +)! 正如之前方法的名称所暗示的那样，这种遍历顺序称为后序遍历。最后，要按中序遍历树，我们先打印左树，然后打印根节点，最后打印右树
verbatim
public static void printInorder (Tree tree)
if (tree == null) return;
printInorder (tree.left);
System.out.print (tree + " ");
printInorder (tree.right);
verbatim
结果为 1 + 2 * 3，这是中缀表达式。
公平地说，我必须指出我省略了一个重要的复杂情况。有时当我们在中缀表达式中编写表达式时，我们必须使用括号来保留操作顺序。因此，中序遍历不足以生成中缀表达式。
然而，经过一些改进，表达式树和三种递归遍历提供了一种通用的方法，用于将表达式从一种格式转换为另一种格式。
encapsulation client provider abstract class class!abstract
正如我之前提到的，我们一直用来遍历树的方式存在问题：它打破了客户端代码（使用树的应用程序）和提供者代码（树实现）之间的界限。理想情况下，树代码应该是通用的；它不应该了解表达式树的任何信息。生成和遍历表达式树的代码不应该了解树的实现。这种设计准则被称为对象封装，以区别于我们在封装一节中看到的封装，我们可能将其称为方法封装。
在当前版本中，树代码了解太多关于客户端的信息。相反，树类应该提供以各种方式遍历树的通用功能。在遍历时，它应该对每个节点执行由客户端指定的运算。
Visitable abstract class!Visitable
为了促进这种利益分离，我们将创建一个新的抽象类，名为 Visitable。存储在树中的项将被要求是可访问的，这意味着它们定义了一个名为 visit 的方法，该方法执行客户端希望对每个节点执行的操作。这样，树就可以执行遍历，而客户端就可以执行节点运算。
以下是我们在客户端和提供者之间插入抽象类需要执行的步骤
枚举
定义一个抽象类，指定提供者代码需要在其组件上调用的方法。
根据新的抽象类编写提供者代码，而不是泛型对象。
定义一个属于抽象类的具体类，并根据客户端的要求实现所需的方法。
编写客户端代码以使用新的具体类。
枚举
接下来的几节将演示这些步骤。
定义抽象类
[edit | edit source]abstract class!defining interface
抽象类定义看起来很像具体类定义，只是它只指定每个方法的接口，而不是实现。Visitable 的定义是
逐字 public interface Visitable
public void visit ();
verbatim
就是这样！关键字 interface 是 Java 中抽象类的关键字。visit 的定义看起来像任何其他方法定义，只是它没有主体。此定义指定任何实现 Visitable 的类都必须具有一个名为 visit 的方法，该方法不接受任何参数并返回 void。
body!method
与其他类定义一样，抽象类定义位于与类同名的文件中（在本例中为 Visitable.java）。
实现抽象类
[edit | edit source]abstract class!implementing Token class class!Token
如果我们使用表达式树来生成中缀，那么访问节点意味着打印其内容。由于表达式树的内容是标记，我们将创建一个名为 Token 的新具体类，该类实现 Visitable
逐字 public class Token implements Visitable
String str;
public Token (String str)
this.str = str;
public void visit ()
System.out.print (str + " ");
verbatim
当我们编译此类定义（位于名为 Token.java 的文件中）时，编译器会检查提供的方法是否满足抽象类指定的条件。如果没有，它将生成错误消息。例如，如果我们拼写错误应该为 visit 的方法的名称，我们可能会得到类似“类 Token 必须声明为抽象类。它没有定义来自接口 Visitable 的 void visit()。”的东西。
下一步是修改解析器，以便将 Token 对象放入树中，而不是字符串。这里有一个小例子
verbatim
String expr = "1 2 3 * +"; StringTokenizer st = new StringTokenizer (expr, " +-*/", true); String token = st.nextToken(); Tree tree = new Tree (new Token (token), null, null));
verbatim
此代码获取字符串中的第一个标记，将其包装在 Token 对象中，然后将 Token 放入树节点中。如果树要求货物是可访问的，它将转换 Token 以成为可访问的对象。当我们从树中移除 Visitable 时，我们将不得不将其强制转换为 Token。
作为练习，编写一个名为 visitPreorder 的 printPreorder 版本，该版本遍历树并按前序在每个节点上调用 visit。
树的数组实现
[edit | edit source]tree!array implementation implementation!Tree ADT!Tree
实现树意味着什么？到目前为止，我们只看到了树的一种实现，一种类似于链表的链接数据结构。但是，我们想要识别的还有其他结构。任何能够执行基本树操作集的东西都应该被识别为树。
那么树操作是什么呢？换句话说，我们如何定义树 ADT？
描述
[构造函数：] 构建一棵空树。
[isEmpty：] 这棵树是空树吗？
[getLeft：] 返回此节点的左孩子。
[getRight：] 返回此节点的左孩子。
[getParent：] 返回此节点的父节点。
[getCargo：] 从此节点返回货物对象。
[setCargo：] 为此节点分配一个货物对象（如果需要，创建该节点）。
描述
在我们看到的实现中，空树由特殊值 null 表示。getLeft 和 getRight 通过访问节点的实例变量来执行，getCargo 和 setCargo 也是如此。我们还没有实现 getParent（你可以考虑如何实现它）。
树的另一种实现使用数组和索引，而不是对象和引用。为了了解它的工作原理，我们将从查看同时使用数组和对象的混合实现开始。
此图显示了一棵类似于我们一直在查看的树，尽管它是横向排列的，根在左边，叶在右边。在底部，有一个引用数组，引用树中的对象。货物对象表示为 null 引用。
图=figs/tree3.eps，宽度=5in
你可能会注意到，数组索引 1 指向根节点，而数组索引 0 是空的。原因很快就会变得清晰。
所以现在我们有一棵树，其中每个节点都有一个唯一的索引。此外，索引已根据特定模式分配给节点，以实现以下结果
枚举
索引为 的节点的左孩子索引为 。
索引为 的节点的右孩子索引为 。
索引为 的节点的父节点索引为 （向下取整）。
枚举
使用这些公式，我们可以仅通过进行算术运算来实现 getLeft、getRight 和 getParent；我们不必使用引用！
由于我们不使用引用，我们可以删除它们，这意味着以前是树节点的东西现在只是货物，没有其他东西。这意味着我们可以将树实现为货物对象的数组；我们根本不需要树节点。
以下是一些实现的示例
verbatim public class Tree
Object[] array; int i;
public Tree ()
array = new Object [128];
i = 1;
public Tree (Object[] array, int i)
this.array = array;
this.i = i;
verbatim
到目前为止没有惊喜。实例变量是对象数组和一个整数，表示在数组中找到新节点的位置。
第一个构造函数使用任意初始大小初始化数组（我们以后可以随时调整它的大小）。第二个构造函数假设对象数组已经存在。构成树的所有节点都将共享同一个数组，并具有不同的 i 值。
我们使用 i 来访问给定节点的货物
verbatim
public Object getCargo ()
if (i >= array.length) return null;
return array[i];
public void setCargo (Object obj)
if (i >= array.length)
array = resize (array);
array[i] = obj;
verbatim
两种方法都必须检查数组的长度。如果 getCargo 尝试访问数组中不存在的元素，它将返回 null 以指示空树。如果 getCargo 超过数组的长度，它将调整数组的大小以腾出空间（有关 resize 的可能实现，请参见 resize 一节）。
要检查节点是否是空树，我们将检查货物是否为 null。
verbatim
public boolean empty ()
return (getCargo() == null);
verbatim
getLeft、getRight 和 getParent 的实现只是算术运算
verbatim
public Tree getLeft ()
return new Tree (array, 2*i);
public Tree getRight ()
return new Tree (array, 2*i + 1);
public Tree parent ()
return new Tree (array, i/2);
verbatim
最后，我们准备构建一棵树。在另一个类（客户端）中，我们将编写
verbatim
Tree tree = new Tree ();
tree.setCargo ("cargo for root");
verbatim
构造函数构建一棵空树。调用 setCargo 会将字符串“根的货物”放入根节点中。
要向根节点添加子节点
verbatim
tree.getLeft().setCargo ("cargo for left");
tree.getRight().setCargo ("cargo for right");
verbatim
在树类中，我们可以提供一个按前序打印树内容的方法。
verbatim
public void print ()
if (isEmpty ()) return;
System.out.println (array[i]);
getLeft().print();
getRight().print();
verbatim
通过将根作为参数传递，我们从客户端调用此方法。
verbatim
tree.print (root);
verbatim
输出为
逐字 货物为根 货物为左 货物为右 逐字
此实现提供了定义树的基本操作。正如我指出的那样，树的链接实现提供了相同的操作，但语法不同。作为练习，修改链接树，使其实现 Tree ADT。
数组实现的一个问题是数组的初始大小是任意的，可能需要调整它的大小。最后一个问题可以通过用 Vector 替换数组来解决。
Vector 类
[edit | edit source]向量
Vector class class!Vector
Vector 是 java.util 包中的内置 Java 类。它是对象数组的实现，具有自动调整自身大小的附加功能，因此我们不必这样做。
Vector 类提供名为 get 和 set 的方法，类似于我们为 Tree 类编写的 getCargo 和 setCargo 方法。你应该通过查阅在线文档来回顾其他 Vector 操作。
在使用 Vector 类之前，你应该了解一些概念。每个 Vector 都有一个容量，它表示分配用于存储值的存储空间量，还有一个大小，它表示实际上在向量中的值数量。
下图是一个简单的向量图，它包含三个元素，但容量为七。
figure=figs/vector.eps
一般来说，在调用 set 或 get 之前，由客户端代码确保向量具有足够的大小。如果尝试访问不存在的元素（在本例中是索引为 3 到 6 的元素），将收到一个 ArrayIndexOutOfBounds 异常。
exception!ArrayIndexOutOfBounds ArrayIndexOutOfBounds
向量方法 add 和 insert 会自动增加向量的尺寸，但 set 不会。resize 方法在向量的末尾添加空元素，以达到给定尺寸。
大多数情况下，客户端不需要担心容量。只要向量的尺寸发生改变，容量就会自动更新。出于性能原因，某些应用程序可能希望控制此功能，这就是为什么存在用于增加和减少容量的额外方法的原因。
由于客户端代码无法访问向量的实现，因此不清楚我们应该如何遍历它。当然，一种可能性是使用循环变量作为向量中的索引。
verbatim
for (int i=0; i<v.size(); i++)
System.out.println (v.get(i));
verbatim
这没什么问题，但还有另一种方法可以用来演示 Iterator 类。向量提供了一个名为 iterator 的方法，该方法返回一个 Iterator 对象，使遍历向量成为可能。
Iterator 类
[edit | edit source]iterator
Iterator class class!Iterator abstract class
Iterator 是 java.util 包中的一个抽象类。它指定了三个方法。
描述
[hasNext:] 此迭代还有更多元素吗？
[next:] 返回下一个元素，如果不存在，则抛出异常。
[remove:] 从集合中删除最后返回的元素。
描述
以下示例使用迭代器遍历并打印向量的元素。
verbatim
Iterator iterator = vector.iterator ();
while (iterator.hasNext ())
System.out.println (iterator.next ());
verbatim
一旦创建了 Iterator，它就成为与原始 Vector 分开的对象。Vector 中的后续更改不会反映在 Iterator 中。事实上，如果在创建 Iterator 后修改 Vector，则 Iterator 将失效。如果再次访问 Iterator，它将导致 ConcurrentModification 异常。
exception!ConcurrentModification ConcurrentModification
在前面的部分中，我们使用 Visitable 抽象类允许客户端遍历数据结构，而无需了解其实现的详细信息。迭代器提供了另一种执行相同操作的方法。在第一种情况下，提供者执行迭代并调用客户端代码来``访问每个元素。在第二种情况下，提供者向客户端提供一个对象，客户端可以使用它来一次选择一个元素（尽管顺序由提供者控制）。
作为练习，编写一个名为 PreIterator 的具体类，它实现 Iterator 接口，并为 Tree 类编写一个名为 preorderIterator 的方法，该方法返回一个 PreIterator，它以先序选择 Tree 的元素。
词汇表
[edit | edit source]binary tree root node leaf node parent node child node level prefix preorder postorder inorder class variable encapsulation
描述
[二叉树:] 一棵树，其中每个节点引用 0、1 或 2 个依赖节点。
[根:] 树中最顶端的节点，其他节点不引用它。
[叶子:] 树中最底部的节点，它不引用其他节点。
[父节点:] 引用给定节点的节点。
[子节点:] 节点引用的节点之一。
[层级:] 与根节点距离相等的节点集。
[前缀表示法:] 一种编写数学表达式的方法，其中每个运算符都出现在其操作数之前。
[先序:] 遍历树的一种方式，在访问子节点之前访问每个节点。
[后序:] 遍历树的一种方式，在访问节点本身之前访问每个节点的子节点。
[中序:] 遍历树的一种方式，先访问左子树，然后访问根节点，最后访问右子树。
[类变量:] 在任何方法之外声明的静态变量。它可以从任何方法访问。
[二元运算符:] 接受两个操作数的运算符。
[对象封装:] 将两个对象的实现尽可能分离的设计目标。两个类都不应该知道另一个类的实现细节。
[方法封装:] 将方法的接口与其实现细节分离的设计目标。
描述