admin 管理员组

文章数量: 1087135


2024年9月14日发(作者：greatview)

维普资讯

２００６年第６期　福建　电脑　１２１　

二叉树遍历的通用非递归算法　

徐凤生１李立群２马夕荣２　

（１．德州学院计算机系。山东德州２５３０２３　２．山东省农业管理干部学院，山东济南２５０１００）　

【摘要】：对二又树的遍历过程进行了深入的分析，给出了求先序序列、中序序列和后序序列的通用非递归算法。该算　

法只需对二叉树遍历一次即可求出三种遍历序列．算法本身揭示了二又树三种遍历的内在关系。　

【关键字】：递归；栈；算法；遍历　

递归算法．实现从１出发沿虚线进行遍历到２结束的过程。既然　

二叉树是数据结构中最常见的存储形式．在二叉树的应用　这种遍历是一次就能完成的过程．就应该能够写出一个三种遍　

中．常常要求在树中查找具有某种特征的结点，或者对树中全部　

历的通用的非递归算法。分析上述过程可以发现。只需要设置一　

结点逐一进行某种处理。这就提出了“二叉树遍历”的问题．即如　

个拽．即可一次遍历得到二叉树的三种遍历序列。下面说明栈的　

何按某条搜索路径对树中各结点寻访．使得每个结点都被访问　

变化情况：　

１．前言　

首先，（先序访问根结点Ａ），Ａ和１进栈（１表示结点Ａ的　

到且仅被访问一次。遍历算法是树与二又树的基础。由二又树的　

递归定义，约定按照先左（子树）后右（子树）的遍历顺序，可以得　

右子树还未访问），（先序访问Ａ的左子树的根结点Ｂ），Ｂ和ｌ　

进栈．由于Ｂ的左子树为空，所以Ｂ和１出栈，（中序访问Ｂ），Ｂ　

Ｏ表示开始遍历结点Ｂ的右子树）．由于Ｂ的右子树　

先序遍历算法：若二叉树为空。则空操作；否则，（１）访问根　

和Ｏ进栈（

为空。Ｂ和Ｏ出栈，（后序访问Ｂ）．Ａ和１出栈。（中序访问Ａ），Ａ　

结点；（２）先序遍历左子树；（３）先序遍历右于树。　

到以下三种遍历方法：　

Ｃ和１进栈，由　

中序遍历算法：若二叉树为空。则空操作；否则，（１）中序遍　

和Ｏ进栈．（先序访　Ａ的右子树的根结点Ｃ），

于Ｃ的左子树为空，Ｃ和ｌ出栈．（中序访问Ｃ）。Ｃ和Ｏ进栈，由　

历左于树；（２）访问根结点；（３）中序遍历右子树。　

后序遍历算法：若二叉树为空。则空操作；否则，（１）后序遍　于Ｃ的右子树为空。Ｃ和０出栈．（后序访问Ｃ）．Ａ和Ｏ出栈，　

历右子树；（２）后序遍历左子树；（３）访问根结点。　

在遍历算法中．递归是普遍的．递归算法具有结构简练、清　

晰、可读性强等优点，但递归算法在执行过程会耗费太多的时问　

和空问。为了追求算法的时空效率，必须将递归算法转化为非递　

上ＩＪ算法。问胚才能得到解决。而要弄清递归算法，则必须清楚算　

法执行过程中栈的变化情况．这样才能设计出较好的非递归算　

法。ｌ侄目前见到的资料中．大多将先序遍历和中序遍历与后序遍　

历分别讨论。本文通过对二叉树遍历过程的分析．给出了二叉树　

（后序访问Ａ），此时栈已空，遍历过程结束。　

从上面可知，每个结点进栈、出栈都是两次。若进栈前访问　

该结点，则得到先序序列ＡＢＣ；若在第一次出栈时济问该结点，　

则得到中序序列ＢＡＣ：若在第二次出栈时访问该结点，则得到后　

序序列ＢＣＡ。因此．只需对二叉树遍历一次即可得到三种遍历序　

列　这里的关键是设置了一个标志位．用来说明该结点的右子树　

是否已访问．以此表示该结点是第一次出栈还是第二次出栈。　

２　

遍历的通用非递归算法。只需一次遍历即可求出三种遍历序列，　

算法本身揭示了二叉树三种遍历的内在关系。设二叉树与栈的　

结构如下（用Ｃ语言描述）：　

ｔｙｐｅｄｅｆ　ｓｌ￣ｌｅｌ　ＢｉＴＮ￣ｅｆ　

ｃｈａｒ　ｄａｔａ；　

８ｕ　ｎｉＴＮｏｄｅ＊ｌｅｈｉｌｄ．‘ｒｅｈｉｌｄ；　

ｌＢｒｒＮｏｄｅ．‘Ｂｉ＇Ｉ’ｒｅ－ｅ；　

ｔｙｐｅｄｅｆ　８ｈ　ｍ　ｅｌｅｍｌｙｐｅｌ　

ＢｉＴｒｅｅＩ；　

ｉｎｔ　ｒ．＇／／ｒ用于标盎ｔ的右予树是否已遍所．嚣已靖所为０，否则为１　

）ｅｌｅｍｔｙｐｅ；　

ｔｙｐｅａｌｅｒ　ｓｔｉ－ｕｅ｜ｓｈｕｚｕｌ　

ｃｈａｒ　ｄａｔａ；　

曰　

圉１三种遍历示意团　

ｉｎｔ　ｘｈ；／／ｘｈ为ｌ表示此时的ｄａ　为先序越历时的元誊．ｘｌｌ为２＿丧　此时的ｄａｌＨ为中序　

遍历时的元索．ｘＩｌ为３寝示此时的ｄａｔａ为后序温历时的元豢　

｝　ｕ　Ｉｌ１ｉｄＭ　ｌ　ｕｌｉｄＭ且ｘ】存放追所日Ｉｊ访问的元霉，用ｘｈ的值区分各种遍历结果　

ｉｙｐ￣ｌｅｆ￣ｌｒａｔ：ｌ　

ｅｌｅｍｔｙｐｅ　ｂａｓｅ；　

ｅｌｅｍｔｙ￣　ｔｏｐ；　

３二叉树遍历的通用非递归算法　

二叉树遍历的通用非递归算法描述如下：　

（１）韧始化栈ｓ；ｓｕｍ＝Ｏ；　

（２）ｆ０ｒ（ｐ．￡＝Ｔ：ｐ．　’．ｔ￣．ｐ．ｔ－＞ｂｈｉｌｄ）　

Ｉ　

）￣ｓｔａｃｋ；　

２．二叉树的遍历过程分析　

二叉树中的每个结点只有两个分支（左和右）。这是我们解　

决问题的关键所在　以图１为例对二叉树的遍历过程进行分析，　

我们不难发现．三种遍历的本质区别在于访问根结点和遍历左、　

右子树的先后顺序不同　图中用带箭头的虚线表示了这三种遍　

ｘｕｌｉｅ［ｓｕｍ］．ｄａｔａ＝ｐ．ｔ－＞ｄａｔａ；，／先序ｖｉｓｌｔ（ｐ．ｔ一＞ｄａｔａ）　

ｘｕｌｉｅ［ｓｕｍ］．ｘｈ＝ｌ：　

ＳＵｍ＋＋：　

ｐ．ｒ＝ｌ　表示ｐ，ｔ的右予树还来访问　

ｐｕｓｈ（￥．ｐ）；／／ｐ进拽　

｝　

（３）若栈ｓ非空．则　

历算法的递归执行过程。其中，向下的箭头表示更深一层的递归　

调用．向上的箭头表示从递归调用退出返回。虚线旁边的三角　

形、圆形和方形内的字符分别表示在先序、中序和后序遍历二叉　

树中访阃结点时输出的信息。由此。只要沿虚线从１出发到２结　

束．将沿途所见的三角形（或圆形、或方形）内的符号记下，便得　

Ｉ　

ｐｏｐ（Ｓ．ｐ）：ｌｉｐ　Ｉ｛１栈　

．　

遍历二叉树的先序（或中序、或后序）序列。　

要想给出三种遍历算法的非递归程序．就是要设计一个非　

ｘｕｌｉｅ［ｓｕｍ］．ｄａｔａ＝ｐ．ｔ－＞ｄａｔａ；｜｜　碍ｖｉｓｉｔｌｐ．ｔ一＞ｄａｔａ）　

ｘｕｌｉｅ［ｓｕ　ｍＩ．ｘｈ＝３；　

ｓｕｍ＋＋；　ｆ下转第４ｌ页）　

维普资讯

２００６年第６期　福建　电脑　４１　

３．１集成框架　

行转换的模式．并不存储具体的数据．具体实现时。为给每个异构　

ｘＭＬ能够表达半结构化数据．将多个应用程序所生成的数　

数据源提供一个其包装器（ｗｒａｐｐｅｒ），由它负责为该相应的数据　

据统一到虚拟ＸＭＬ文件并传送到客户机上．被解析出来的ＸＭＬ　源提供存取机制．它定义了关系模型和ＤＯＭ对象数据模型之问　

数据可以被编辑或者操纵．因此．把ＸＭＬ作为数据描述和转换工　

的映射．如图２所示．　

具来构造数据集成的中间层．不仅能够适应Ｗｅｂ的发展需要。而　

且还将简化Ｗｅｂ数据源集成系统的实现．我们的集成框架如图　

１所示．　

圈２信息谭屡／　中间件层箱｝勾　

ＸＭＬ模式与关系模式的转换的核心与实质就是按ＸＰＤＬ　

编写的转换规则和转换规则的执行解释方法．下面就依次分别　

介绍从ＸＭＬ模式到关系模式的转换规则的组成部分和执行方　

陋１摹统＾虚捏曩　

法．以及从关系模式到ＸＭＬ模式的转换规则的组成部分和执行　

系统分为四层结构．分别叙述如下：　

方法．从ＸＭＬ模式到关系模式转换的转换规则脚本：由关系模式　

１）应用层．用户界面层．为用户的综合应用提供支持．例如：进　的定义和ＸＭＬ模式到关系模式转换规则的定义组成：从关系模　

式到ＸＭＬ模式转换的转换规则脚本：由关系模式的定义和关系　

行综合数据查询、决策支持和深层次的数据挖掘等服务．　

２）ＸＭＬ接Ｅｌ层．依据特定的转换协议，负责把应用层的应用　模式到ＸＭＬ模式转换规则的定义组成．　

请求传送到ＸＭＬ中间层．一方面。实现保持ＸＭＬ数据的一致性。　

４．结束语　

从简单的读／写到复杂的事务操作：另一方面．接口必须实现必要　

由于ＸＭＬ是一种类似于ＨＴＭＬ被设计用来描述数据的语　

的访问控制策略．防止非法访问．　

言。通过ＸＭＬ我们可以实现异构数据的集成、共享及利用提高　

３）ＸＭＬ中问件层．提供必要的数据转换功能或者工具。进行　

了信息系统的整体效能。当然在做这些工作的时候，我们也应该　

数据与ＸＭＬ格式的相互转换。将数据存储到ＸＭＬ数据空间中。　

注意到应用系统所处行业的规范化以及相关的国际标准．这对　

并且维护ＸＭＬ数据空间与各异构数据源之间的影射关系．　于未来信息系统的发展前景有着非常重要的意义。进一步的工　

４１信息源层．系统所集成数据的来源．它包括各种数据．例如：　

作主要集中在设计一种数据源描述语言．用以描述源数据与集　

数据库、文本数据和其它多媒体数据等。　

３．２系统实现技术　

成模式问的映射．最终完成用户对集成视图的操纵转换成对数　

据源的有效操纵。　

参考文献：　

１．娄渊胜．尹燕敏．王志坚．基于ＣＯＲＢＡ的通用数据存取中间件研究及　

为了完成异构数据库问的通讯．必须实现ＲＤＢＭＳ－－－｝ＸＭ　

ＲＤＢＭＳ的转换．一个具体的ＸＭＬ模式到关系模式的数据转换．　

需要涉及较为复杂的ＸＭＬ格式分析处理相应的数据库操作及　

有效性校验．我们通过对ＸＭＬ的数据模型与关系模型的特征的　

比较，认为两者转换的实质：ｆ１）从ＸＭＬ中的数据（存在方式可以　

是Ｃｏｎｔｅｎｔ、属性值、元索名等１到关系模式中字段的映射；（２】从　

ＸＭＬ中数据的相互位置关系到关系模式中元组与元组的关系　

及元组与字段的关系的映射．在数据管理上．我们采用“虚拟　

ＸＭＬ文件”的思想．即所有数据的变化请求都通过ＸＭＬ中问件　

层进行存取操作．而中问件层只存储所有异构数据和ＸＭＬ问进　

＋－—卜－＋－＋－＋－＋－—卜＊＋－＋－—卜－＋一＋－　，＋ｒ－＋－－＋－．．＋－－－＋一十－＋－—　

实现Ｕ］．小型微型计算机系统．２００１。２２（１Ｏ）：２１０—２１２．　

２．靳强勇，李冠宇．张　傻．异构数据集成技术的发展和现状Ⅱ］．计算机工　

程与应用．２００２，３８０１）：１１２　１１４．　

３．李军怀．用明空，耿圜华．张景．ＸＭＬ在异构数据集成中的应用研究Ⅱ】．　

计算机应用．２００２．２２（９）：１０－１２．　

４．柴晓路．Ｘ／ＶｌＬ数据环境下基于关系模式的数据交换方法ＩＤＢ／ＯＵ．　

ｈｔｔｐ：／／ｗｗｗ．ｄｉｇｉｔａｌｅａｒｔｈ．ｔｉｅｒ．ｃｎ／ＧＩＳＲｄａｔｃｄｌＴｌｓ　ｓｕｅｓ／Ｘ／ＶｌＬ／ＸＭＬｄａｔａ．ｈｔｍ　

－＋－＋－＋　＋－＋－＋－＋一十－－ｋ－－－ｌ－－＋－＋－－￣－－＋－＋　

（上接第１２１页）　

ｌ　

ｅ］ｓｅ　

Ｉ　

ｘｕｌｉｅ［ｓｕｍ］．ｄａｔａ＝ｐ．ｔ－＞ｄａｔａ；／／中序ｖｉｓｉｔ（ｐ．ｔ－＞ｄａｔａ）　

ｘｕｌｉｅ［ｓｕｍ］，ｘｈ＝２；　

ｐ．ＦＯ；／，表示开始访问ｐ．ｔ的有子树　

ｐｕｓｈ（Ｓ．ｐ）：／／ｐ进栈　

ｔｏ，（ｐ．ｔ－－－ｐ　ｔ一＞ｔｅｈｉｌｄ；ｐ．Ｉ；ｐ．ｔ－－－ｐ．ｔ－＞ｌｃｈｉｌｄ）　

Ｉ　

例如若输人为ＡＢＣ（（ＤＥ（Ｇ（　（（（，其中（为空格。则数组ｘｕｌｉｅ　

中的值为：　

由上面的数组可以看出．由ｘｕｌｉｅ．ｘｈ值为１的字符依次组成　

的序列即为先序序列．由ｘｕｌｉｅ．ｘｈ值为２的字符依次组成的序列　

即为中序序列．由ｘｕｌｉｅ．ｘｈ值为３的字符依次组成的序列即为后　

序序列。　

本文通过对二叉树遍历过程的分析．给出了求先序序列、中　

序序列和后序序列的通用非递归算法．只需对二叉树遍历一次　

即可求出三种遍历序列．该算法本身揭示了二叉树三种遍历过　

程的内在关系　

参考文献：　

１．严蔚牧。昊伟民蝙著．敷据结构．北京：清华大学出版社，２００２．　

２．尹德辉，孟林。李忠等．二叉树后序遍历的非递归算法讨论．西南民族　

大学学报．２００３．５．　

３．黎远松．一种生成二又树遍历序列的新方法．四川轻化工学院学报。　

２ｏ０３．４．　

ｘｕｌｌｅ［ｓｕｍ］．ｄａｔａ＝ｐ．卜＞ｄ山　，先序ｖｉｓｉｔ￣．ｔ－＞ｄａｔａ）　

ｘｕｌｉｅ［ｓｕｍ］．ｘｈ＝ｌ：　

ＳｕＩ１１＋＋：　

Ｐ．ｒ＝ｌ：　

ｐｕｓｈ（Ｓ，ｐ】；　

ｌ　

Ｊ　

Ｂ　Ｃ　Ｃ　Ｃ　Ｂ　Ｄ　Ｅ　８　Ｇ　Ｇ　Ｇ　Ｅ　Ｄ　Ｆ　Ｆ　Ｆ　Ｄ　Ｂ　＾　＾　

ｌ　ｌ　２　３　２　ｌ　ｌ　２　ｌ　２　３　３　２　ｌ　ｌ　３　３　３　２　３　


本文标签： 遍历 数据 算法 递归

版权声明：本文标题：二叉树遍历的通用非递归算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1726289469a940264.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。