二叉树遍历的非递归实现
二叉树遍历的非递归实现
前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。当给出二叉树的链式存储结构以后,用具有递归功能的程序设计语言很方便就能实现上述算法。然而,并非所有程序设计语言都允许递归;另一方面,递归程序虽然简洁,但可读性一般不好,执行效率也不高。因此,就存在如何把一个递归算法转化为非递归算法的问题。解决这个问题的方法可以通过对三种遍历方法的实质过程的分析得到。
如图6.3(b)所示的二叉树,对其进行先序、中序和后序遍历都是从根结点A开始的,且在遍历过程中经过结点的路线是一样的,只是访问的时机不同而已。图6.9中所示的从根结点左外侧开始,由根结点右外侧结束的曲线,为遍历图6.3(b)的路线。沿着该路线按△标记的结点读得的序列为先序序列,按*标记读得的序列为中序序列,按⊕标记读得的序列为后序序列。
然而,这一路线正是从根结点开始沿左子树深入下去,当深入到最左端,无法再深入下去时,则返回,再逐一进入刚才深入时遇到结点的右子树,再进行如此的深入和返回,直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问,中序遍历是在从左子树返回时遇到结点访问,后序遍历是在从右子树返回时遇到结点访问。
图6.9 遍历图6.3(b)的路线示意图
在这一过程中,返回结点的顺序与深入结点的顺序相反,即后深入先返回,正好符合栈结构后进先出的特点。因此,可以用栈来帮助实现这一遍历路线。其过程如下。
在沿左子树深入时,深入一个结点入栈一个结点,若为先序遍历,则在入栈之前访问之;当沿左分支深入不下去时,则返回,即从堆栈中弹出前面压入的结点,若为中序遍历,则此时访问该结点,然后从该结点的右子树继续深入;若为后序遍历,则将此结点再次入栈,然后从该结点的右子树继续深入,与前面类同,仍为深入一个结点入栈一个结点,深入不下去再返回,直到第二次从栈里弹出该结点,才访问之。 (1)先序遍历的非递归实现
在下面算法中,二叉树以二叉链表存放,一维数组stack[MAXNODE]用以实现栈,变量top用来表示当前栈顶的位置。
void NRPreOrder(BiTree bt) {/*非递归先序遍历二叉树*/
BiTree stack[MAXNODE],p; int top;
if (bt==NULL) return; top=0;

二叉树遍历的非递归实现_IT/计算机_专业资料。二叉树遍历的非递归实现前面给出的二叉树先序、中序和后序三种遍历算法都是递归算法。当给出二叉树的链式存储 结构...
遍历二叉树的非递归实现_IT/计算机_专业资料。递归遍历二叉树很简单,现在来学习一下如何用非递归的方法遍历二叉树吧。维普资讯 http://www.cqvip.com 皇 责师...
邮箱: liuy0711@foxmail.com】 遍历是二叉树各种操作的基础, 上一节给出的遍历算法是递归实现的, 本节给出二叉树遍历 的非递归实现,非递归实现需要使用前面讲到的...
二叉树非递归遍历 C语言实现_IT/计算机_专业资料。二叉树非递归遍历 算法文档内有简要概括#include <stdio.h> #include <stdlib.h> typedef struct BitNode {...
二叉树遍历的非递归实现_计算机软件及应用_IT/计算机_专业资料。二叉树遍历的非递归实现一、递归的定义及特点 递归是指某个函数直接或间接的调用自身。 问题的...
本文通过对二叉树遍历过程的分析, 给出了二叉树遍历的通用非递归算法, 只需一次遍历即可求出三种遍历序列, 算法本身揭示了 二叉树三种遍历的内在关系。 2 二叉树...
遍历二叉树的非递归算法编写的方法:根据树中结点的遍历规律及顺序直接写出其非...; } } } 进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。...
遍历函数 printf("\n 后序遍历: "); //打印提示内容 postOrder(root); //调用后序遍历函数 getch(); } -7- 二叉树的遍历 下面给出的是用非递归算法实现...
用递归和非递归算法实现二叉树的三种遍历_IT/计算机_专业资料。用递归和非递归算法实现二叉树的三种遍历《数据结构与算法》实验报告三 数据结构与算法》实验报告三...
非递归实现二叉树遍历的思想: 1.跟递归遍历二叉树的前提一样, 首先应该创建一个二叉树, 同样使用先序递归的方式 创建二叉树。 2.然后是中序,先序,后序非递归...
热门文档