5. 二叉树的遍历¶
5.1. 二叉树的遍历¶
我们常常希望通过"访问"二叉树的每个结点来处理二叉树， 每次访问都执行某个特定操作，比如打印结点的内容。 按某种次序访问全部结点的任何过程都称为一次 遍历 。 把树中每个结点恰好列出一次的遍历， 称为树中结点的一个 枚举 。 有些应用并不要求按任何特定次序访问结点， 只要每个结点恰好被访问一次即可。 而对另一些应用来说， 结点必须按保持某种关系的次序来访问。
5.1.1. 前序遍历¶
例如，我们可能希望保证在访问某个结点的子结点 之前 先访问 该结点本身。 这称为 前序遍历 。 如果想通过复制另一棵树来构建一棵树，那么就很适合使用前序遍历： 先创建结点，再创建它的子结点，这是最简单的做法。
5.1.2. 后序遍历¶
反过来，我们也可能希望只在访问某结点的子结点（及其子树） 之后 才访问该结点。 例如，设想我们在一门没有垃圾回收的语言（如 C++）中工作。 如果想删除一棵树，就需要对它的每个结点调用析构函数。 我们必须先删除结点 A 的子结点，然后才能删除 A， 否则就再也无法访问这些子结点了！ 而要做到这一点，又得先删除子结点的子结点，如此递推下去。 这称为 后序遍历 。
5.1.3. 中序遍历¶
中序遍历 先访问左子结点 （包括其整棵子树），然后访问该结点本身， 最后访问右子结点（包括其整棵子树）。 二叉搜索树 就利用这种遍历按值升序打印所有结点。
5.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();
}
interface BinNode<E> { // Binary tree node ADT
// Get and set the element value
public E value();
public void setValue(E v);
// return the children
public BinNode<E> left();
public BinNode<E> 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
}
static <E> void preorder(BinNode<E> 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 ，
访问右子树中的所有结点。
后序遍历和中序遍历与此类似，
只是根据需要改变结点与其子结点被访问的先后次序。
