资源描述：
《二叉树遍历的非递归算法分析与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、软件设计开发本栏目责任编辑:谢媛媛二叉树遍历的非递归算法分析与实现罗帅(湖南农业大学信息科学技术学院,湖南长沙410128)摘要:对二叉树的遍历过程进行了深入的分析,根据二叉树三种遍历的内在关系给出了求先序序列、中序序列和后序序列的非递归算法,该算法只需对二叉树遍历一次即可求出三种遍历序列。关键词:非递归算法;二叉树;栈;遍历中图分类号:TP311文献标识码:A文章编号:1009-3044(2008)04-10678-03TheAnalysisandRealizationofTraversingBinaryTr
2、eeWithNon-recursiveAlgorithmLUOShuai(InformationScienceandTechnologyCollegeofHunanAgriculturalUniversity,Changsha410128,China)Abstract:Thearticleanalysesthetraversingbinarytree.Itdefinesanon-algorithmforpreorder_traversing、inorder_traversingandpos-torder_tra
3、versingbinarytreeaccordingtotheinlinerelationamongthreemethodsoftraversingbinarytree.Withthealgorithmwecanobtainthreesequencesbutneedonlyonetimetotraversethebinarytree.Keywords:non-recursivealgorithm;binarytree;stack;traverse1前言二叉树是数据结构中最常见的存储形式,在二叉树的应用中,常常要
4、求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。这就提出了“二叉树遍历”的问题,即如何按某条搜索路径对树中各结点寻访,使得每个结点都被访问到且仅被访问一次。遍历算法是树与二叉树的基础。由二叉树的递归定义,约定按照先左(子树)后右(子树)的遍历顺序,可以得到以下三种遍历方法:先序遍历算法:若二叉树为空,则空操作;否则,(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。中序遍历算法:若二叉树为空,则空操作;否则,(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。后序遍历算
5、法:若二叉树为空,则空操作;否则,(1)后序遍历右子树;(2)后序遍历左子树;(3)访问根结点。在遍历算法中,递归是普遍的,递归算法具有结构简练、清晰、可读性强等优点,但递归算法在执行过程会耗费太多的时间和空间。为了追求算法的时空效率,必须将递归算法转化为非递归算法,问题才能得到解决。而要弄清递归算法,则必须清楚算法执行过程中栈的变化情况,这样才能设计出较好的非递归算法。在目前见到的资料中,大多将先序遍历和中序遍历与后序遍历分别讨论。本文通过对二叉树遍历过程的分析,给出了二叉树遍历的通用非递归算法,只需一次遍历
6、即可求出三种遍历序列,算法本身揭示了二叉树三种遍历的内在关系。2二叉树的遍历过程分析二叉树中的每个结点只有两个分支(左和右),这是我们解决问题的关键所在。以图1为例对二叉树的遍历过程进行分析,我们不难发现,三种遍历的本质区别在于访问根结点和遍历左、右子树的先后顺序不同。图中用带箭头的虚线表示了这三种遍历算法的递归执行过程。其中,向下的箭头表示更深一层的递归调用,向上的箭头表示从递归调用退出返回。虚线旁边的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历二叉树中访问结点时输出的信息。由此,只要沿虚线从1出
7、发到2结束,将沿途所见的三角形(或圆形、或方形)内的符号记下,便得遍历二叉树的先序(或中序、或后序)序列。要想给出三种遍历算法的非递归程序,就是要设计一个非递归算法,实现从1出发沿虚线进行遍历到2结束的过程。既然这种遍历是一次就能完成的过程,就应该能够写出一个三种遍历的通用的非递归算法。分析上述过程可以发现,只需要设置一个栈,即可一次遍历得到二叉树的三种遍历序列。下面说明栈的变化情况:收稿日期:2008-01-12作者简介:罗帅(1982-),女,湖南长沙人,助教,在读硕士。678电脑知识与技术本栏目责任编辑:
8、谢媛媛软件设计开发图1三种遍历示意图首先,(先序访问根结点A),A和1进栈(1表示结点A的右子树还未访问),(先序访问A的左子树的根结点B),B和1进栈,由于B的左子树为空,所以B和1出栈,(中序访问B),B和0进栈(0表示开始遍历结点B的右子树),由于B的右子树为空,B和0出栈,(后序访问B),A和1出栈,(中序访问A),A和0进栈,(先序访问A的右子树的根结点C),C和1进栈,由于
