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

韩凯

摘要：在研究树的遍历和图的遍历时大多使用非递归算法。本文主要对数据结构进行概述分析二叉树遍历和图的深度优化搜索的非递归推算，理清了在研究树与图的过程中的思路，希望有所启发。

关键词：数据结构;二叉树;图的深度优化搜索;非递归算法

一、概述

数据结构是计算机的专业课程，数据结构一股比较抽象复杂的，二叉树和图的操作算法还是具有代表性的，这两种算法都需要遍历操作为基础，所以只要了解了数据结构中遍历操作法，才能对树和图有深刻认识。

二、二叉树的遍历

（一）二叉树的遍历操作

许多树的应用都是基于树的遍历来实现的，例如查找元素、插入元素等。二叉树主要是根和左右子树三部分，访问是有一定顺序的，所以导致遍历先序、中序和后序三种方法。遍历思想是类似的，先看二叉树是否为空，不是的话就按照先根后左子树最后右子树来访问，二叉树是空的时候不需要操作。二叉树在计算科学中有着重要的作用，如计算机操作系统中的文件管理、编译程序的语法结构和数据库系统信息组织形式等;在生活中，二叉树可以用在密码学中，利用二叉树的先序遍历、后序便利、中序遍历对密码进行加密和解密;在经济中，二叉树可以用来研究期权的定价模型。

二、遍历操作的非递归算法

二叉树的非递归遍历要借助堆栈来实现，具体算法为：

1）设置一个堆栈进行初始化。

2）把根节点所表示的指针入栈。

3）当堆栈非空时，重复执行下列步骤：①出栈会取得一个结点指针，对该结点进行访问;②若该结点的右孩子不是空，则该结点的右子树指针进栈;⑧若该结点的左孩子不是空，则该结点的左子树指针进栈。

二叉树遍历的非递归算法相对于递归算法，减少了函数调用等开销，具有性能优势。

先序遍历：

Int PreOrderl （BiTree T，Int （*Visit） （TElemTypee））

{

STack * S; 11 栈 S 中存储指向树结点的指针。

BiTree P;

......

//如果左子树和右子树均被访问过，则结点退栈，并进行访问。更新pre。else

Pop（S，&p）.

if（！ Visit（p- > data））

retum ER ROR;

pre =p;

}

}

retum oK;

对照非递归算法可以发现：非递归算法应用指针和堆栈，进行出栈和入栈的方法实现了算法，非递归算法程序总体来说较长，编写和调试要费些时间，但因为其一直在调用其他函数进行进栈出栈，所以其占用的空间较少、用时也较短。

三、图的遍历

（一）深度优先搜索

图的深度优先搜索，是研究数据结构图的经典方法。利用深度优先搜索方法，把目标图进行拓扑，对涂上一直点进行数字排列形成拓扑排序表，这种方法在解决图论相关问题是是非常常见的，简单方便又明晰易懂，只是在敲代码的时间上比较久，但是不能以此忽略其解决问题的潜能。图的遍历主要是深度优化搜索和广度优化搜索，这两种遍历方法，装深度优化搜索主要用数据的非递归算法。

（二）深度优先搜索的非递归算法

深度优化利用非递归算法，要记录每一个从起点和所有临接点之间的搜索记录，记录结果按照先出去后进来的原则进行存储，只要把上一个点的搜索情况完成，下一个点

才能够继续。举实例来证明：设连通图G中的边集E={（a，b）， （a，e）， （a，c）， （b，e）， （e，d）， （d，f），（f，c）}，则从顶点a出发可以得到一种深度优先遍历的顶点序列是什么呢？图的深度优化搜索遍历类似于树的前序遍历.首先访问出发点A，并将其标记为已访问过;然后依次从A出发搜索A的每个邻接点B、C、D、E，首先判断B是否曾访问过，若是B未访问过需要以B为新的出发点继续前一个步骤深度优化搜索，直至图中所有和A相连接的点或者是有路径相通点均己被访问为止。图中只要存在一个未进行访问的点，就把此未访问点作为顶点成为新的源头重复之前的步骤进行访问判断，直至所有的点都被访问为止。所以从A点出发，找A的下一个点，A下一个点有B、C、D、E，首先到B，再以b为源点，再看B有没有下一个点，发现B的下一个点是E，再以E为源点，E的下一个点是d，再以D为源点，下一个点是F，再以F的下一个点是C.这样全部的点都得到了，该序列就是该图的深度优化搜索遍历，即ABEDFC。

己访问顶点当前搜索情况的类型定义如下：

struct V exSearchInfo

{ int vexIndex：//已訪问顶点的下标

AreNode * pNext;//指向已访问顶点的下一个要判断的邻接点

圈的深度优先搜索算法如下：

void DFSTraverse（ALGraph G）

{ VexSearchInfo sl[20];

for（v=0;v=G.VEXNUM ;v++）

......

//从最近已访问顶点的邻接点中寻找一个未访问的顶点

if（visited[p-→adjvex]==false） //找到一个未访问的顶点

{//访问此顶点，并存储其当前搜索情况

cout<adjvex]data<<””;

visited[p→adjvex]=true;

temp.vexIndex=p→adjvex; temp. pNext=G.vertices[p→ad-jvex]. firstarc：

sl[num++]=temp;

break：

if（p==NULL） num-;//如果最近已访问顶点的所有邻接点搜索完毕，则删除顶点

搜索情况。

总体上而言，数据结构的非递归算法是比较有效率的，很方便解决问题，但有一个弊端就是它的代码比较长，需要自行管理。树的遍历和图的遍历在数据结构分析中属于比较复杂的结构，而且他们的便利操作是最基本又最重要的操作。研究二叉树和图的深度优化搜索通常使用递归函数，利用递归函数研究是存在一定的困难，便可以采用非递归算法，这种方法简单明确，容易理解同样可以对二叉树和图的深度优化搜索进行描述。

参考文献

[1]詹泽梅.数据结构中遍历操作的非递归算法[J].电脑知识与技术，2017（28）.