遍历二叉树的递归与非递归算法浅析

摘要：二叉树是数据结构中最常见的一种存储形式，而遍历二叉树又是二叉树中最重要的操作。该文分别以递归和非递归两种不同的算法来分析遍历二叉树的过程，旨在用简单明了的方法来实现二叉树的遍历，且先序、中序、后序三种遍历方式都可通过这两种算法实现。

关键词：二叉树；遍历；递归；非递归

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)24-5941-02

二叉树是数据结构中最常见的一种存储形式，许多实际问题抽象出来的数据结构通常都能够表示为二叉树，其运算和存储结构都较为简练，因此在算法与数据结构中经常使用。而遍历算法又是二叉树最重要的操作。所谓遍历二叉树，就是按照某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，且仅被访问一次。二叉树的遍历分为先序、中序和后序遍历三种方法，如何才能使初学者更好地理解二叉树的遍历算法呢？本文将从递归和非递归两种方法分别讲述二叉树的遍历过程。

1 递归算法

递归是指在定义自身的同时，又出现了对自身的引用。如果一个算法直接或间接调用自己，则称这个算法是一个递归算法。在遍历二叉树时，递归就是将二叉树的元素分为根结点、左结点和右结点，按照左根右、根左右或左右根的顺序依次访问结点并对其做各种处理。为了使初学者更容易理解，我们可以借助二叉树的图示来讲解。对于三种遍历方法：前序、中序、后序，我们将二叉树拆分为根（T）和左（L）、右（R）子树，此时我们发现，无论是哪种遍历方法，左子树均在右子树之前被访问，因此可以将根结点（T）与其左、右子树拆分开来，确定了遍历的顺序，即确定了访问根结点（T）的时间是在左子树之前还是之后。

例如求下图（1）所示二叉树的中序遍历序列。首先，先确定根结点（A）及其左右子树（B）、（C），按照中序遍历LTR的顺序，任一结点在以其为根的子树中的访问顺序为左子树、根结点、右子树。而对于以B、C为根结点的两个子树，还可继续将其拆分为左、右子树，按左中右的顺序，遍历左子树直到其只有一个结点或为空为止，然后遍历右子树，直到其右子树只有一个结点或为空为止。此步骤可借助图1来讲解。

图1

图（1）可拆分为根结点A和图（2）、（3），其中图（2）为根结点A的左子树，图（3）为A的右子树；接下来，图（2）是以B为根结点的二叉树，我们可继续将其拆分为根结点B和图（4）、（5）；同样地，图（3）是以C为根结点的二叉树，可最终将其拆分为根结点C和图（6）、（7）。

首先，按照中序遍历LTR的顺序遍历A的左子树，即图（2）。其中结点B的左子树为D，D没有左子树，因此直接遍历结点D；然后遍历该左子树的根结点B；接下来遍历B的右子树即图（5），其中G为E的左子树，且G本身无左子树，因此直接遍历G，然后遍历其根结点E。此时二叉树根结点A的左子树即图（2）已遍历完毕，遍历的顺序为DBGE。

接下来应该按照中序遍历的顺序访问根结点A，然后继续遍历右子树即图（3）。

图（3）中以C为根结点的二叉树无左子树，因此首先遍历其根结点C，然后遍历其右子树即图（6）；按照LTR的顺序遍历图（6）应依次访问结点HFI，此处注意图（7）为结点I的右子树，I无左子树，因此遍历I的顺序必然在图（7）之前；接下来考虑图（7）的遍历顺序，其中K为J的左子树，因此应优先遍历，访问顺序应为KJ。最终图（3）的访问序列应为HFIKJ。

由此可得到图（1）所示二叉树的中序遍历序列（LTR）为DBGEAHFIKJ。同理，还可根据拆分法得出其先序遍历序列（TLR）为ABDEGCFHIJK，后序遍历序列（LRT）为DGEBHKJIFCA。使用此类借助图示的拆分法讲解二叉树的遍历，可以将遍历二叉树这一比较抽象的问题分解为若干小问题，便于学生理解；同时，学生们掌握了这种方法后，将会更容易理解遍历的递归算法中递归调用和返回的过程。

2 非递归算法

遍历二叉树使用递归算法固然清晰、易理解，但递归算法解题的运行效率较低，递归调用函数的次数过多容易造成栈溢出等缺点，使我们在实际应用中更多地使用非递归算法来设计程序。使用非递归算法遍历二叉树时，首先设置一个栈，并将根结点压入其中。对于二叉树中的任一结点均执行扩展和访问两种操作：所有未扩展、未访问的新节点全部入栈，然后每个结点依次出栈，出栈后扩展它，将它的左右子树的根结点（未扩展、未访问）及它自身（已扩展、未访问）按访问次序压入栈中，当此结点第二次出栈时就可以直接访问它了。

这个过程如下图所示：设A为一个新结点，第一次入栈如图（8）所示；A第一次出栈后，扩展它，将它的左、右子树的根结点分别记为AL、AR，并为A做上标记（用*A表示），则先序、中序、后序遍历分别将A、AL、AR以不同的顺序压入栈中，如图（9）、（10）、（11）。

图2

算法可描述如下：

1）设置栈s，将二叉树的根结点A压入栈中；

2）当栈非空时，弹出栈顶元素A，并判断该结点是否已被扩展：

① 如已扩展则直接访问A；

② 否则，扩展该结点（记为*A），并得到A的左右子树根结点AL和AR，判断AL、AR是否为空：

.为空则不访问；

.不空则按照先序、中序、后序遍历的顺序分别将*A、AL、AR入栈,得到结果如图（9）、（10）、（11）。

3）继续执行步骤2）。

由图可看出，先序遍历二叉树的过程中，在根结点彻底出栈（被扩展、被访问）之前，其左子树是不会出栈的，即不会被访问；同理，中序、后序遍历也能够保证完全按照规定的顺序依次访问结点。

3 总结

现实世界中多种问题都可归纳成为树和森林的模型，而树和森林又可以用二叉链表作媒介同二叉树进行相互转换，因此，学好二叉树对学习程序设计、利用计算机解决实际问题特别重要；二叉树的各种复杂运算大都是建立在其三种遍历之上的，因此，掌握好二叉树的遍历算法是极有必要的。本文分别选取了两种较简单的递归和非递归算法来分析二叉树的三种遍历过程，使初学者更易于理解二叉树的遍历算法。

参考文献：

[1] 严蔚敏,吴伟民.数据结构（C语言版）[M].北京:清华大学出版社,1997:121-131．

[2] 胡元义,邓亚玲,罗作民,等. 数据结构（C语言）实践教程[M].西安:西安电子科技大学出版社,2002:77-85.

[3] 李春葆.数据结构习题与解析[M].2版.北京:清华大学出版社,2004:311．

[4] 吉冬梅.拆分法讲授二叉树遍历教学研究[J].电脑学习,2010(1).

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文