一种二叉树非递归遍历算法的C语言实现

摘要：针对二叉树的链式存储结构，分析了二叉树的各种遍历算法，探讨了递归算法的递推消除问题，提出了一种改进的非递归遍历算法并用C语言予以实现。

关键词：二叉树；遍历算法；非递归；C语言实现

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）01-0223-03

1 概述

树形结构是一种非常常见的数据结构，而二叉树又是其中最重要的一种树形结构。二叉树的遍历是指按照一定的规则和次序将二叉树中的每一个结点都访问一次，既不能重复，也不能漏掉。一般而言，对二叉树的遍历有前序遍历、中序遍历、后序遍历和按层遍历等几种方式。在具体的算法设计上，以上遍历方式一般采取递归算法来实现，该文将探讨采用非递归算法来实现二叉树的遍历。

2 二叉树的数据结构描述

二叉树作为一种非线性结构，每个结点最多有一个双亲结点和两个子结点。二叉树可以采用顺序存储结构和链式存储结构。对于完全二叉树而言，采用顺序存储是非常方便并且节省空间的，但是对于大部分的非完全二叉树而言，采用顺序存储将导致空间浪费严重且结构混乱、效率低下。因此，更多的时候，大家都更愿意用链式存储结构来表示二叉树，这样结构更加清晰，尤其是对于左右子树的描述和双亲节点的描述更加方便。该文中拟采用链式结构来表示二叉树。用链式存储结构来表示二叉树，一个结点至少由3个域组成，即数据域、左子结点域和右子结点域（如图1所示）。

3 二叉树的遍历及递归算法实现

3.1 二叉树的遍历

二叉树的遍历就是一个不漏的访问树中的每个结点，同时也不能重复。所谓“访问”，就是指对结点的数据域进行某种操作，比如说读取、删除、更新、求该节点深度等等。对于二叉树中的任意一个部分，都可以把它看作三部分，根节点、左子树、右子树，我们用D表示访问跟结点，用L表示遍历左子树，用R表示遍历右子树，则共有以下6种遍历方式[1]。

1） DLR：先访问根结点，再遍历左子树，然后遍历右子树；

2） DRL：先访问根结点，再遍历右子树，然后遍历左子树；

3） LDR：先遍历左子树，再访问根结点，然后遍历右子树；

4） RDL：先遍历右子树，再访问根结点，然后遍历左子树；

5） LRD：先遍历左子树，再遍历右子树，然后访问根结点；

6） RLD：先遍历右子树，再遍历左子树，然后访问根结点。

为了方便和规范化，通常都规定遍历顺序是先左后右的，所以以上6种遍历算法，经常采用的是DLR（前序遍历）、LDR（中序遍历）和LRD（后序遍历）。在有些情况下，特别是对于完全二叉树的情况，还可以采用按层遍历的方式。该文将以中序遍历（LDR）为例，分析并探讨LDR的递归算法和非递归算法。

3.2 LDR的递归算法

对于中序遍历（LDR）而言，在二叉树的任何一个结点，都执行以下步骤：

1） 判断是否为空，如果为空，遍历结束；

2） 按中序遍历左子树；

3） 访问根结点；

4） 按中序遍历右子树。

其中，步骤（1）是结束条件，步骤（2）和步骤（4）则是一个典型的递归调用过程。依据这个算法思想，写出C语言代码如下：

void InOrder（Tnode root）

//中序遍历二叉树，root 表示二叉树或当前子树的根结点指针

{if（root！=NULL）

{InOrder（rootL_child）；

//中序遍历左子树

visit（rootData）；

//访问当前根节点的数据域

InOrder（rootR_child）；

//中序遍历右子树

}}

其中，visit（ ）为访问函数，对二叉树或当前子树的根结点的数据域进行访问，访问方式可以是读取数据、删除、修改等等各种操作，这里不再赘述。

4 二叉树的非递归算法

4.1 递归算法的缺点与采用非递归算法的必要性

递归算法是一种化繁为简，把复杂问题分解成若干简单问题的求解方式，他对某些复杂问题的求解是非常有效的[2]。但是，递归算法实际上是在顶层把要解决的问题往后推，然后等到递推到最底层，等解决完一个子问题后再往后回溯递归，再返回到最顶层，同时，递归算法的执行需要系统提供隐式栈来支持，这必然会导致递归算法的执行效率较低。并且在以下两种情况下，必须要用非递归算法来代替递归算法。

1） 某些语言环境不支持递归。如Fortran语言中无递归机制。

2） 递归算法是一次性执行的，中间过程对用户是不可见的，而有时需要设置断点，调试程序，或者有其他的特殊要求时，不能采用递归算法[1，2]。

4.2 中序遍历的非递归算法

首先，我们要分析递归算法中进层和退层时的操作。

递归进层时系统需要做三件事：

1） 保留本层参数与返回地址（将所有的实参、返回地址等信息传递给被调用函数保存）；

2） 给下层参数赋值（为被调用函数的局部变量分配存储区）；

3） 将程序转移到被调函数的入口。

递归退层时系统需要做三件事：

1） 保存被调函数的计算结果；

2） 恢复上层参数（释放被调函数的数据区）；

3） 依照被调函数保存的返回地址，将控制转移回调用函数。

同时考虑到递归调用算法需要系统提供隐式栈来执行，所以在将复杂的递归算法改写成非递归算法时，必须引入栈。下面给出基于栈的二叉树中序遍历非递归算法的C语言实现：

void InOrder（Tnode root）

//中序遍历二叉树的非递归算法

{ int top=0；

p=root；

L1：if（p！=NULL） //遍历左子树

{ top+=2；

if（top>m） return； //栈满退出

s[top-1]=p； //本层参数进栈

s[top]=L2； //返回地址进栈

p=pL_child； //给下层参数赋值

goto L1； //转向开始

L2： Visit（pData）； //访问根

top+=2；

if（top>m） return； //栈满溢出

s[top-1]=p； //遍历右子树

s[top]=L3；

p=pR_child；

goto L1；}

L3：if（top！=0）

{ addr=s[top]；

p=s[top-1]； //取出返回地址

top=top-2； //退出本层参数

goto addr；}}

5 结束语

二叉树的遍历是进行二叉树其他操作的基础，如二叉树的线索化、二叉树的构造、二叉树的还原等等，都要用到二叉树的遍历算法。二叉树的遍历算法可以采用递归算法，也可以采用非递归算法。递归算法具有简洁明了的优点，程序代码短，容易理解，但是递归算法的执行效率往往不高，而非递归算法虽然语法上稍显繁琐，但是却有着执行效率高、应用环境广的特点。

参考文献：

[1] 陈卫卫， 王庆瑞. 数据结构与算法[M]. 北京：高等教育出版社， 2010.

[2] 耿国华. 数据结构——用C语言描述[M]. 北京：高等教育出版社， 2011.