12.3. 二叉树的遍历¶
12.3.1. 二叉树的遍历¶
我们常常希望通过"访问"二叉树的每个结点来处理二叉树，每次访问都执行某个特定操作，比如打印结点的内容。按某种次序访问全部结点的任何过程都称为一次 遍历 。把树中每个结点恰好列出一次的遍历，称为树中结点的一个 枚举 。有些应用并不要求按任何特定次序访问结点，只要每个结点恰好被访问一次即可。而对另一些应用来说，结点必须按保持某种关系的次序来访问。
12.3.1.1. 前序遍历¶
例如，我们可能希望保证在访问某个结点的子结点 之前 先访问该结点本身。这称为 前序遍历 。如果想通过复制另一棵树来构建一棵树，那么就很适合使用前序遍历：先创建结点，再创建它的子结点，这是最简单的做法。
12.3.1.2. 后序遍历¶
反过来，我们也可能希望只在访问某结点的子结点（及其子树） 之后 才访问该结点。例如，设想我们在一门没有垃圾回收的语言（如 C++）中工作。如果想删除一棵树，就需要对它的每个结点调用析构函数。我们必须先删除结点 A 的子结点，然后才能删除 A，否则就再也无法访问这些子结点了！而要做到这一点，又得先删除子结点的子结点，如此递推下去。这称为 后序遍历 。
12.3.1.3. 中序遍历¶
中序遍历 先访问左子结点 （包括其整棵子树），然后访问该结点本身， 最后访问右子结点（包括其整棵子树）。 二叉搜索树（binary search tree） 就利用这种遍历按值升序打印所有结点。
12.3.1.4. 实现¶
现在我们讨论遍历的几种实现，但首先需要定义一个可供使用的结点 ADT。正如链表由一组链接对象组成，树由一组结点对象组成。下面是二叉树结点的 ADT，名为 BinNode 。后面介绍的一些二叉树结构会用到这个类。它提供的成员函数可以设置或返回元素值、返回指向左子结点的指针、返回指向右子结点的指针，或者指示该结点是否为叶结点。
interface BinNode { // Binary tree node ADT
// Get and set the element value
public int value();
public void setValue(int v);
// return the children
public BinNode left();
public BinNode right();
// return TRUE if a leaf node, FALSE otherwise
public boolean isLeaf();
}
遍历例程自然要写成递归函数。它的输入参数是一个指向结点的指针，我们把这个结点称为 rt ，因为每个结点都可以看作某棵子树的根。对遍历函数的初始调用传入的是指向树的根结点的指针。遍历函数按所需的次序访问 rt 及其子结点（如果有的话）。例如，前序遍历规定 rt 要先于其子结点被访问。这可以很容易地实现如下。
static void preorder(BinNode rt) {
if (rt == null) return; // Empty subtree - do nothing
visit(rt); // Process root node
preorder(rt.left()); // Process all nodes in left
preorder(rt.right()); // Process all nodes in right
}
函数 preorder 首先检查树是否为空（如果为空，遍历即告完成， preorder 直接返回）。否则， preorder 调用 visit 来处理根结点（即打印该值，或执行应用所要求的任何计算）。随后在左子树上递归调用函数 preorder ，它会访问该子树中的所有结点。最后在右子树上调用 preorder ，访问右子树中的所有结点。后序遍历和中序遍历与此类似，只是根据需要改变结点与其子结点被访问的先后次序。
