数据结构与算法分析 —— C 语言描述：树的遍历

由于二叉查找树中对信息进行了排序，因而按顺序列出说有的关键字会很简单，递归过程如下：

void
PrintTree( SearchTree T)
{
    if( T != NULL )
    {
        PrintTree( T->Left );
        PrintElement( T->Element );
        PrintTree( T->Right );
    }
}

毫无疑问，该过程能够解决将关键字排序列出的问题。正如我们前面看到的，这类例程当用到树的时候称为中序遍历（由于它依序列出了关键字，因此是有意义的）。中序遍历的一般策略是首先遍历左子树，然后是当前节点，最后遍历右子树。这个算法的有趣部分除它简单的特性外，还在于其总的运行时间是 。这是因为在树的每一个节点处运行的工作都是常数时间的。每一个节点访问依次，而在每一个节点进行的工作是检测是否为 NULL，建立两个过程调用并执行 PrintElement 。由于在每个节点的工作花费常数时间以及总共有 N 个节点，因此运行时间为 。

有时我们需要先处理两棵子树然后才能处理当前节点。例如，为了计算一个节点的高度，我们需要知道它的两棵子树的高度。如下计算高度的例程：

int
Height( Tree T )
{
    if (T == NULL)
        return -1;
    else
        return 1 + Max( Height( T->Left), Height(T->Right));
}

由于检查一些特殊的情况总是有益的（当涉及递归时尤其重要），因此要注意这个例程声明树叶的高度为零，这是正确的。这种一般的遍历顺序叫做后序遍历。因为在每个节点的工作花费常数时间，所以总的运行时间也是 。

第三种常用的遍历方案为先序遍历（preorder traversal）。这里，当前节点在其儿子节点之前处理。这种遍历可以利用节点深度标志每一个节点。

所有这些例程都有一个共有的想法，那就是首先处理 NULL 的情形，然后才是其余的工作。注意，此处缺少一些额外的变量。这些例程仅仅传递了树，并没有声明或是传递任何额外的变量。程序越紧凑，一些愚蠢的错误出现的可能就越小。

第四种遍历用得很少，叫做层序遍历（level-order-traversal）。在层序遍历中，所有深度为 D 的节点要在深度为 D+1 的节点之前处理。层序遍历与其他类型的遍历不同的地方在于它不是递归实施的；它用到队列，而不使用递归所默示的栈。