二叉树遍历的非递归算法分析与实现

1、本栏目责任编辑 :谢媛媛 软件设计开发二叉树遍历的非递归算法分析与实现罗 帅(湖南农业大学 信息科学技术学院 , 湖南 长沙 410128摘要 :对二叉树的遍历过程进行了深入的分析 , 根据二叉树三种遍历的内在关系给出了求先序序列、 中序序列和后序序列的非递归 算法 , 该算法只需对二叉树遍历一次即可求出三种遍历序列。关键词 :非递归算法 ; 二叉树 ; 栈 ; 遍历中图分类号 :TP311文献标识码 :A 文章编号 :1009-3044(200804-10678-03The Analysis and Realization of Traversing Binary Tree With Non

2、-recursive AlgorithmLUO Shuai(Information Science and Technology College of Hunan Agricultural University, Changsha 410128, ChinaAbstract:The article analyses the traversing binary tree. It defines a non-algorithm for preorder_traversing 、 inorder_traversing and pos-torder_traversing binary tree acc

3、ording to the inline relation among three methods of traversing binary tree. With the algorithm we can obtain three sequences but need only one time to traverse the binary tree.Key words:non-recursive algorithm; binary tree; stack; traverse1前言二叉树是数据结构中最常见的存储形式 , 在二叉树的应用中 , 常常要求在树中查找具有某种特征的结点 , 或者对树中

4、全部结点 逐一进行某种处理。这就提出了“ 二叉树遍历” 的问题 , 即如何按某条搜索路径对树中各结点寻访 , 使得每个结点都被访问到且仅被 访问一次。遍历算法是树与二叉树的基础。由二叉树的递归定义 , 约定按照先左 (子树 后右 (子树 的遍历顺序 , 可以得到以下三种 遍历方法 :先序遍历算法 :若二叉树为空 , 则空操作 ; 否则 , (1 访问根结点 ; (2 先序遍历左子树 ; (3 先序遍历右子树。中序遍历算法 :若二叉树为空 , 则空操作 ; 否则 , (1 中序遍历左子树 ; (2 访问根结点 ; (3 中序遍历右子树。后序遍历算法 :若二叉树为空 , 则空操作 ; 否则 , (

5、1 后序遍历右子树 ; (2 后序遍历左子树 ; (3 访问根结点。在遍历算法中 , 递归是普遍的 , 递归算法具有结构简练、 清晰、 可读性强等优点 , 但递归算法在执行过程会耗费太多的时间和空 间。 为了追求算法的时空效率 , 必须将递归算法转化为非递归算法 , 问题才能得到解决。 而要弄清递归算法 , 则必须清楚算法执行过 程中栈的变化情况 , 这样才能设计出较好的非递归算法。在目前见到的资料中 , 大多将先序遍历和中序遍历与后序遍历分别讨论。 本文通过对二叉树遍历过程的分析 , 给出了二叉树遍历的通用非递归算法 , 只需一次遍历即可求出三种遍历序列 , 算法本身揭示了 二叉树三种遍历的

6、内在关系。2二叉树的遍历过程分析二叉树中的每个结点只有两个分支 (左和右 , 这是我们解决问题的关键所在。以图 1为例对二叉树的遍历过程进行分析 , 我们 不难发现 , 三种遍历的本质区别在于访问根结点和遍历左、 右子树的先后顺序不同。图中用带箭头的虚线表示了这三种遍历算法的 递归执行过程。 其中 , 向下的箭头表示更深一层的递归调用 , 向上的箭头表示从递归调用退出返回。 虚线旁边的三角形、 圆形和方形 内的字符分别表示在先序、 中序和后序遍历二叉树中访问结点时输出的信息。由此 , 只要沿虚线从 1出发到 2结束 , 将沿途所见的 三角形 (或圆形、 或方形 内的符号记下 , 便得遍历二叉树

7、的先序 (或中序、 或后序 序列。要想给出三种遍历算法的非递归程序 , 就是要设计一个非递归算法 , 实现从 1出发沿虚线进行遍历到 2结束的过程。 既然这种 遍历是一次就能完成的过程 , 就应该能够写出一个三种遍历的通用的非递归算法。分析上述过程可以发现 , 只需要设置一个栈 , 即 可一次遍历得到二叉树的三种遍历序列。下面说明栈的变化情况 :收稿日期 :2008-01-12作者简介 :罗帅 (1982- , 女 , 湖南长沙人 , 助教 , 在读硕士。678电脑知识与技术本栏目责任编辑 :谢媛媛 软件设计开发图 1三种遍历示意图首先 , (先序访问根结点 A , A 和 1进栈 (1表示结

8、点 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进栈 , 由于 C 的左子树为 空 , C 和 1出栈 , (中序访问 C , C 和 0进栈 , 由于 C 的右子树为空 , C 和 0出栈 , (后序访问 C , A 和 0出栈 , (后序访问

9、 A , 此时栈已 空 , 遍历过程结束。从上面可知 , 每个结点进栈、 出栈都是两次。若进栈前访问该结点 , 则得到先序序列 ABC ; 若在第一次出栈时访问该结点 , 则得 到中序序列 BAC ; 若在第二次出栈时访问该结点 , 则得到后序序列 BCA 。 因此 , 只需对二叉树遍历一次即可得到三种遍历序列。 这里 的关键是设置了一个标志位 , 用来说明该结点的右子树是否已访问 , 以此表示该结点是第一次出栈还是第二次出栈。3二叉树遍历的通用非递归算法的实现设二叉树与栈的结构如下 (用 C 语言描述 :typedef struct BiTNodechar data;struct BiTNo

10、de *lchild,*rchild;BiTNode,*BiTree;typedef struct elemtypeBiTree t;int r; /r 用于标志 t 的右子树是否已遍历 , 若已遍历为 0, 否则为 1elemtype;typedef struct Arraychar data;int xh; /xh 为 1表示此时的 data 为先序遍历时的元素 , xh 为 2表示此时的 data 为中序遍历时的元素 , xh 为 3表示此时 的 data 为后序遍历时的元素Array, sequence Max; /sequence Max存放遍历时访问的元素 , 用 xh 的值区分各

11、种遍历结果typedef structelemtype *base;elemtype *top;sqstack;二叉树遍历的通用非递归算法描述如下 :(1 初始化栈 S ; sum=0;(2 for(pt=T; pt; pt=pt->lchildsequence sum.data=pt->data; /先序 visit(pt->datasequence sum.xh=1;sum+;pr=1; /表示 pt 的右子树还未访问push(S,p; /p 进栈(3 若栈 S 非空 , 则679本栏目责任编辑 :谢媛媛 软件设计开发pop(S,p; /p 出栈if(pr=0sequen

12、ce sum.data=pt->data; /后序 visit(pt->datasequence sum.xh=3;sum+;elsesequence sum.data=pt->data; /中序 visit(pt->datasequence sum.xh=2;sum+;pr=0; /表示开始访问 pt 的右子树push(S,p; /p 进栈for(pt=pt->rchild; pt; pt=pt->lchildsequence sum.data=pt->data; /先序 visit(pt->datasequence sum.xh=1;sum+

13、;pr=1;push(S,p;例如若一棵用广义表表示为 A(B(D(#,G,#,C(E,F 的二叉树 , 则其对应数组 sequence 中的值为表 1所示。表 1sequence 数组由上面的数组可以看出 , 由 sequence.xh 值为 1的字符依次组成的序列 ABDGCEF 即为先序序列 , 由 sequence.xh 值为 2的字符 依次组成的序列 DGBAECF 即为中序序列 , 由 sequence.xh 值为 3的字符依次组成的序列 GDBEFCA 即为后序序列。本文通过对二叉树遍历过程的分析 , 给出了求先序序列、 中序序列和后序序列的通用非递归算法 , 只需对二叉树遍历一次即可 求出三种遍历序列 , 该算法本身揭示了二叉树三种遍历过程的内在关系。参考文献 :1严蔚敏 , 吴伟民 . 数据结构 M. 北京 :清华大学出版社 ,2002.2尹德辉 , 孟林 , 李忠 , 等 . 二叉树后序遍历的非递归算法讨论 J. 西南民族大学学报