《二叉树遍历(递归—非递归转换)课件》由会员分享，可在线阅读，更多相关《二叉树遍历(递归—非递归转换)课件（25页珍藏版）》请在金锄头文库上搜索。
1、单击此处编辑母版标题样式单击此处编辑母版副标题样式*1遍历二叉树 制作人：计科系孙玉霞数据结构返回目录 遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历6.3 遍历二叉树本次课主要内容返回目录 遍历二叉树v方法l先序遍历：先访问根结点,然后分别先序遍历左子树、右子树l中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树l后序遍历：先后序遍历左、右子树，然后访问根结点l按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL返回目录返回目录ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C 二叉树的先序遍历返
2、回目录算法实现： 进入非递归算法递归算法先序遍历过程演示返回目录void preorder(BiTree t) if(t!=NULL) printf(%dt,t-data); preorder(t-lchild); preorder(t-rchild); 主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pr
3、e(T R);先序序列：A B D CTTTTBack返回目录非递归算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)返回目录pABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)返回目录ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访
4、问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)返回目录ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)返回目录返回目录 二叉树的中序遍历一、二叉树中序遍历的定义：首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。中序遍历的结果：HtHABCDEJIFGKLDKJLBEIA FCG 返回目录二、二叉树中序遍历的递归实现#define NULL 0Typede
5、f struct node char data; struct node *lchild,*rchild; *BiTree;Void inorder(BiTree t) if(t!=NULL) inorder(tlchild); printf(“%c”,tdata) inorder(trchild); 返回目录三、二叉树中序遍历的非递归实现tHABCDEJIFGKL需保存的结点： A B D Htttt= t输出：Ht= tJ KDttt= t= tKtJtLt= t= LttBt剩下的遍历过程由同学们自行完成！返回目录在二叉树中序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分： 当前
6、正在访问的子树（被指针t指向） 栈中等待访问的子树 当t所指向的子树访问完成后，若栈非空，则取出栈顶元素，访问其根结点，然后再进入其右子树访问（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。返回目录二叉树中序遍历的非递归实现算法： typedef struct stack /*栈结构定义*/ BiTree data100; int top; sqstack; void push(sqstack *s,BiTree t) /*进栈*/ s.datas.top+=t; BiTree pop(s
7、qstack *s) /*出栈*/ if (s.top!=0) return(s.data-s.top); else return NULL; 返回目录void inorder1(BiTree t) /*非递归实现二叉树中序遍历*/ / sqstack s; s.top=0; while(t!=NULL) | (s.top!=0) while (t!=NULL) push(&s,t); t=t-lchild; if (s.top!=0) t=pop(&s); printf(%c ,t-data); t=t-rchild; 返回目录返回目录 二叉树的后序遍历一、二叉树后序遍历的定义：首先按照后序
8、遍历的顺序访问根结点的左子树；然后按照后序遍历的顺序访问根结点的右子树。最后访问根结点；后序遍历的结果：HKLJDIEBFGCAtHABCDEJIFGKL返回目录二、二叉树后序遍历的递归实现 void postorder(BiTree t) if (t!=NULL) postorder(t-lchild); postorder(t-rchild); printf(%c,t-data); 返回目录三、二叉树后序遍历的非递归实现tHABCDEJIFGKL需保存的结点： A B D Htttt= t输出：Ht= tKKttt= t= tJtt= Ltt剩下的遍历过程由同学们自行完成！t JttLt=
9、 tttDt过程演示返回目录在二叉树后序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分： 当前正在访问的子树（被指针t指向） 栈中等待访问的子树（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）当t 为空或t 所指向的子树访问完成后，若栈非空，则考虑两种情况： 若栈顶元素的右子树尚未访问，则访问其右子树，此 时栈顶元素不能出栈； 若栈顶元素的右子树已被访问，则访问该栈顶元素，并将其出栈；返回目录因此为了区分栈顶元素的右子树是否已被访问，可为其设置一标志tag . tag=0，表示该栈顶元素的右子树尚未访问，该栈顶元素不能出栈，而应该进入其右子
10、树进行访问； tag=1，表示该栈顶元素的右子树已被访问，可将该栈顶元素出栈，并输出其值； 显然，当一个元素刚进入栈时，其tag值应该为0，而当进入栈顶元素的右子树访问时，应该将其tag值改为1。（4）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。请同学们仔细分析对照后序遍历和中序遍历的区别！二叉树后序遍历和中序遍历的主要区别在于对栈顶元素的处理，即以上第（3）点。返回目录二叉树后序遍历的非递归实现算法：void postorder1(BiTree t) sqstack s; s.top=0; while (t!=NULL)|(s.top!=0) while (t !=NULL)
11、 s.datas.top=t; s.tags.top=0; s.top+; t=t-lchild; typedef struct stack /*栈结构定义*/ BiTree data100; int tag100; /*为栈中每个元素设置的标记*/ int top; /*栈顶指针*/ sqstack; 返回目录 while (s.top0)& (s.tags.top=1) t=s.datas.top; printf(%c ,t-data); s.top- -; if (s.top0) t=s.datas.top; s.tags.top=1; t=t-rchild; else t=NULL; 返回目录总结:“遍历”是二叉树各种操作的基础。由上讨论得知： 遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。 这实质上是对一个非线性结构进行线性化。返回目录返回目录-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f练习题1：
