二叉树遍历递归非递归转换.ppt

二叉树遍历递归非递归转换.ppt

《二叉树遍历递归非递归转换.ppt》由会员分享，可在线阅读，更多相关《二叉树遍历递归非递归转换.ppt（25页珍藏版）》请在冰点文库上搜索。

1,2023/6/12,数据结构二叉树的遍历,遍历二叉树,制作人：

计科系孙玉霞,数据结构,2,遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历,6.3遍历二叉树,本次课主要内容,2,3,遍历二叉树方法先序遍历：

先访问根结点,然后分别先序遍历左子树、右子树中序遍历：

先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：

先后序遍历左、右子树，然后访问根结点按层次遍历：

从上到下、从左到右访问各结点,返回目录,3,4,DLR,先序遍历序列：

ABDC,二叉树的先序遍历,4,5,算法实现：

进入非递归算法,先序遍历过程演示,5,6,voidpreorder（BiTreet）if（t!

=NULL）printf（%dt,t-data）;preorder（t-lchild）;preorder（t-rchild）;,返回,返回,返回,返回,A,C,B,D,返回,先序序列：

ABDC,Back,6,7,非递归算法,7,8,8,9,9,10,返回目录,10,11,二叉树的中序遍历,一、二叉树中序遍历的定义：

首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。

中序遍历的结果：

H,D,K,J,L,B,E,I,A,F,C,G,11,12,二、二叉树中序遍历的递归实现,#defineNULL0Typedefstructnodechardata;structnode*lchild,*rchild;*BiTree;Voidinorder（BiTreet）if（t!

=NULL）inorder（tlchild）;printf（“%c”,tdata）inorder（trchild）;,12,13,三、二叉树中序遍历的非递归实现,B,D,H,t=,输出：

H,t=,J,K,D,t=,t=,K,J,L,t=,t=,L,B,剩下的遍历过程由同学们自行完成！

13,14,在二叉树中序遍历过程中：

（2）在遍历过程中要做的工作始终分成两部分：

当前正在访问的子树（被指针t指向）栈中等待访问的子树当t所指向的子树访问完成后，若栈非空，则取出栈顶元素，访问其根结点，然后再进入其右子树访问,

（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）,（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。

14,15,二叉树中序遍历的非递归实现算法：

typedefstructstack/*栈结构定义*/BiTreedata100;inttop;sqstack;voidpush（sqstack*s,BiTreet）/*进栈*/s.datas.top+=t;BiTreepop（sqstack*s）/*出栈*/if（s.top!

=0）return（s.data-s.top）;elsereturnNULL;,15,16,voidinorder1（BiTreet）/*非递归实现二叉树中序遍历*/sqstacks;s.top=0;while（t!

=NULL）|（s.top!

=0）while（t!

=NULL）push（,返回目录,16,17,二叉树的后序遍历,一、二叉树后序遍历的定义：

首先按照后序遍历的顺序访问根结点的左子树；然后按照后序遍历的顺序访问根结点的右子树。

最后访问根结点；,后序遍历的结果：

HKLJDIEBFGCA,17,18,二、二叉树后序遍历的递归实现voidpostorder（BiTreet）if（t!

=NULL）postorder（t-lchild）;postorder（t-rchild）;printf（%c,t-data）;,18,19,三、二叉树后序遍历的非递归实现,B,D,H,t=,输出：

H,t=,K,K,t=,t=,J,t=,L,剩下的遍历过程由同学们自行完成！

J,L,t=,D,过程演示,19,20,在二叉树后序遍历过程中：

（2）在遍历过程中要做的工作始终分成两部分：

当前正在访问的子树（被指针t指向）栈中等待访问的子树,

（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）,（3）当t为空或t所指向的子树访问完成后，若栈非空，则考虑两种情况：

若栈顶元素的右子树尚未访问，则访问其右子树，此时栈顶元素不能出栈；若栈顶元素的右子树已被访问，则访问该栈顶元素，并将其出栈；,20,21,因此为了区分栈顶元素的右子树是否已被访问，可为其设置一标志tag.tag=0，表示该栈顶元素的右子树尚未访问，该栈顶元素不能出栈，而应该进入其右子树进行访问；tag=1，表示该栈顶元素的右子树已被访问，可将该栈顶元素出栈，并输出其值；显然，当一个元素刚进入栈时，其tag值应该为0，而当进入栈顶元素的右子树访问时，应该将其tag值改为1。

（4）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。

请同学们仔细分析对照后序遍历和中序遍历的区别！

二叉树后序遍历和中序遍历的主要区别在于对栈顶元素的处理，即以上第（3）点。

21,22,二叉树后序遍历的非递归实现算法：

voidpostorder1（BiTreet）sqstacks;s.top=0;while（t!

=NULL）|（s.top!

=0）while（t!

=NULL）s.datas.top=t;s.tags.top=0;s.top+;t=t-lchild;,typedefstructstack/*栈结构定义*/BiTreedata100;inttag100;/*为栈中每个元素设置的标记*/inttop;/*栈顶指针*/sqstack;,22,23,while（s.top0）,23,24,总结:

“遍历”是二叉树各种操作的基础。

由上讨论得知：

遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。

这实质上是对一个非线性结构进行线性化。

返回目录,24,25,先序遍历：

中序遍历：

后序遍历：

层次遍历：

-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,练习题1：

25,