数据结构中遍历操作的非递归算法

詹泽梅

摘要： 二叉树和图是数据结构中非常重要的内容，遍历操作是它们的最基本的操作。由于递归函数执行过程系统开销较大，因此该文研究了遍历操作的非递归算法。论文介绍了二叉树遍历和图的深度优先搜索操作定义，分析了操作的非递归算法解决思路，并给出详细的非递归算法。

关键词：非递归；先序遍历；深度优先搜索；数据结构

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）28-0040-03

Abstract： Binary tree and graph are very important contents in data structure. Traversal operation is the basic operation of them. Because the system overhead of recursive function execution is larger than that of non-recursive function， this paper studies the non-recursive algorithm of traversal operations. The paper introduces the definition of the binary traversal and the depth_first search of graph， analyzes the solutions of these operations， and gives the detailed non-recursive algorithms.

Key words： non-recursion； preorder traversal； depth_first search； data structure

1 概述

数据结构是计算机专业的一门重要专业基础课。该课程介绍的数据结构非常抽象，且算法比较复杂，特别是二叉树和图的操作算法。二叉树和图的很多相关操作是在遍历操作的基础上实现的，因此，理解遍历操作对于树和图两章内容非常重要。

一般，二叉树的遍历和图的深度优先搜索算法通常使用递归算法来描述。递归算法具有结构清晰、描述简单、容易理解的特点。但是递归函数调用的过程既浪费系统存储空间 ， 还消耗系统处理的时间[1]，因此，有必要研究遍历操作的非递归算法。

2 二叉树的遍历

2.1 二叉树的遍历操作

二叉树可分为根D、左子树L、右子树R三部分，对这三部分的访问顺序可按DLR、LDR、LRD三种顺序进行，由此得到三种遍历方法：先序遍历、中序遍历、后序遍历。

先序遍历的思想是[2]：若二叉树为空，则空操作，否则：

（1） 访问根结点；

（2） 先序遍历左子树；

（3） 先序遍历右子树。

中序遍历算法、后序遍历算法的思想与先序遍历算法思想类似，区别在于访问根结点操作的时机不同。中序遍历操作时，根结点的访问在遍历左子树和遍历右子树两个操作中间；后序遍历时，根结点的访问在遍历左子树和遍历右子树两个操作之后。

2.2 遍历操作的非递归算法

遍历二叉树操作的给定条件是根指针，因此遍历二叉树操作从根结点开始。先序遍历二叉树过程中，对根结点、左子树、右子树三部分的操作顺序是访问根结点、遍历左子树、遍历右子树。图1中虚线和数字画出了对一棵非空二叉树先序遍历的操作順序。同样，我们可分析出二叉树中序遍历和后序遍历的操作顺序，如图2、图3。

根据上述三图可将一棵非空二叉树遍历时的状态分为4种：开始遍历、访问根结点、遍历左子树、遍历右子树。遍历过程中，二叉树从一种状态转变为另一种。例如先序遍历，首先处于开始遍历状态，接着转变为访问根结点状态，然后转变为遍历左子树状态，最后转变为遍历右子树状态。我们可以定义一个枚举类型表示二叉树遍历操作的状态。

遍历二叉树的操作中，又有遍历左子树、遍历右子树，它是一个递归定义的操作。如果要用非递归算法来描述，需要记录每一个遍历子树（即二叉树）操作的信息，包括子树根指针和操作状态，以便根据信息对子树进行后续操作。因为递归具有先调用后返回的特点，所以应该用一个先进后出特点的数据结构来记录所有遍历子树操作的信息，例如栈，或者只在末尾进行操作的数组。

最初遍历二叉树时，将该二叉树的遍历操作状态设置为开始遍历状态，并存储该遍历操作信息。遍历操作过程中，根据当前遍历操作状态进行相应状态转变和处理。在处理时，如遇到遍历子树操作，必须存储子树的遍历操作信息，此时信息中遍历操作状态应设置为开始遍历状态。一直根据遍历操作状态进行处理，直到所有遍历操作处理完为止。例如先序遍历，其根据遍历操作信息进行处理的规则如下：

若二叉树为空，则删除该遍历操作信息。

若二叉树的遍历操作状态为开始遍历，则接下来将其状态转变为访问根结点，并执行访问根节点操作。

若二叉树的遍历操作状态为访问根结点，则接下来将其状态转变为遍历左子树，并存储左子树的遍历操作信息。

若二叉树的遍历操作状态为遍历左子树，则接下来将其状态转变为遍历右子树，并存储右子树的遍历操作信息。

若二叉树的遍历操作状态为遍历右子树，则接下来该遍历操作结束，删除该遍历操作信息。

中序遍历和后序遍历的处理与先序遍历类似，只是遍历操作的状态转变顺序不同。对上述先序遍历算法进行简单的修改，就可获得中序遍历和后序遍历的非递归算法。

3 图的遍历

3.1 深度优先搜索

图的遍历方法有两种：深度优先搜索和广度优先搜索。其中，深度优先搜索的算法通常采用递归定义形式。

从某顶点V0出发进行深度优先搜索的算法思想如下：

（1） 访问V0

（2） 对V0的所有邻接点依次判断，若邻接点未访问，则从此邻接点出发进行深度优先搜索。

对图G进行深度优先搜索的算法思想：对图的所有顶点依次判断，若未访问，则从此顶点出发进行深度优先搜索。

3.2 深度优先搜索的非递归算法

由上述算法可以看出，访问一个顶点Vi后，接下来要根据此顶点Vi寻找下一个未访问的顶点。从Vi的所有邻接点中去寻找，只有所有邻接点都被判断完了，从Vi出发进行的深度优先搜索操作才结束。因此，深度搜索过程中要记录每一个已访问顶点的当前搜索情况，包括顶点位置和它的下一个要判断的邻接点的位置。已访问顶点的当前搜索情况应按后进先出的规则存储，因为若访问了一个顶点，则要从此新的顶点开始搜索，新顶点的所有邻接点搜索完了，才能继续以前顶点的搜索。

4 总结

数据结构中树形结构和图状结构是较复杂的结构，他们的遍历操作是最重要的操作。通常，使用递归函数描述二叉树的遍历和图的深度优先搜索，但递归函数执行时的系统开销较大，因此，本文研究了遍历操作的非递归算法，分析了算法思想，给出了非递归算法的详细描述。

参考文献：

[1] 余艳， 刘燕丽.数据结构中递归算法的教学要点及方法探讨[J].电脑知识与技术，2014（2）.

[2] 严蔚敏，吴伟民.数据结构（C语言版）[M].清华大学出版社，2008.endprint