二叉树遍历(递归—非递归转换)

1、2022-4-1数据结构二叉树的遍历1 1遍历二叉树制作人：计科系孙玉霞数据结构返回目录返回目录2 遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历6.3 6.3 遍历二叉树遍历二叉树本次课主要内容本次课主要内容返回目录返回目录3 遍历二叉树遍历二叉树v方法方法l先序遍历先序遍历：先访问根结点：先访问根结点, ,然后分别先序遍历左子树、然后分别先序遍历左子树、右子树右子树l中序遍历中序遍历：先中序遍历左子树，然后访问根结点，最后：先中序遍历左子树，然后访问根结点，最后中序遍历右子树中序遍历右子树l后序遍历后序遍历：先后序遍历左、右子树，然后访问根结点：先后序遍历左、右子树，然后访问根

2、结点l按层次遍历按层次遍历：从上到下、从左到右访问各结点：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL返回目录返回目录返回目录返回目录4ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C 二叉树的先序遍历二叉树的先序遍历返回目录返回目录5算法实现： 进入非递归算法递归算法先序遍历过程演示返回目录返回目录6void preorder(BiTree t) if(t!=NULL) printf(%dt,t-data); preorder(t-lchild); preorder(t-rchild); 主程序主程序Pre(

3、 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右是空返回右是空返回pre(T R);先序序列：A B D CTTTTBack返回目录返回目录7非递归算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP

4、-AP-B访问：C(4)返回目录返回目录8pABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)返回目录返回目录9ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)返回目录返回目录10ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDE

5、FGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)返回目录返回目录返回目录返回目录11 二叉树的中序遍历二叉树的中序遍历一、二叉树中序遍历的定义：一、二叉树中序遍历的定义：首先按照中序遍历的顺序访问根结点的左子树；首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。最后按照中序遍历的顺序访问根结点的右子树。中序遍历的结果：中序遍历的结果：HtHABCDEJIFGKLDKJLBEIA FCG 返回目录返回目录12二、二叉树中序遍历的递归实现二、二叉树中序遍历的递归实现

6、#define NULL 0#define NULL 0Typedef structTypedef struct node node char data; char data; struct node struct node * *lchild,lchild,* *rchildrchild; ; * *BiTreeBiTree; ;Void inorder(BiTreeVoid inorder(BiTree t) t) if(t!=NULL) if(t!=NULL) inorder(tlchild inorder(tlchild);); printf(“%c”,t printf(“%c”,td

7、ata)data) inorder(trchild inorder(trchild);); 返回目录返回目录13三、二叉树中序遍历的非递归实现三、二叉树中序遍历的非递归实现tHABCDEJIFGKL需保存的结点：需保存的结点： A B D Htttt=t输出：输出：Ht=tJ KDttt=t=tKtJtLt=t=LttBt剩下的遍历过程由同学们自行完成！剩下的遍历过程由同学们自行完成！返回目录返回目录14在二叉树中序遍历过程中：在二叉树中序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分： 当前正在访问的子树（被指针t指向） 栈中等待访问的子树 当t所指向的子树访问完成后，若栈非空，则取

8、出栈顶元素，访问其根结点，然后再进入其右子树访问（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。返回目录返回目录15二叉树中序遍历的非递归实现算法：二叉树中序遍历的非递归实现算法： typedef struct stack /*栈结构定义栈结构定义*/ BiTree data100; int top; sqstack; void push(sqstack *s,BiTree t) /*进栈进栈*/ s.datas.top+=t; BiTree pop(sqstack *s) /*出栈出栈*

9、/ if (s.top!=0) return(s.data-s.top); else return NULL; 返回目录返回目录16void 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; 返回目录返回目录返回目录返回目录17 二叉树的后序遍历二叉树的后序遍历

10、一、二叉树后序遍历的定义：一、二叉树后序遍历的定义：首先按照后序遍历的顺序访问根结点的左子树；首先按照后序遍历的顺序访问根结点的左子树；然后按照后序遍历的顺序访问根结点的右子树。然后按照后序遍历的顺序访问根结点的右子树。最后访问根结点；最后访问根结点；后序遍历的结果：后序遍历的结果：HKLJDIEBFGCAtHABCDEJIFGKL返回目录返回目录18二、二叉树后序遍历的递归实现二、二叉树后序遍历的递归实现 void postorder(BiTree t) if (t!=NULL) postorder(t-lchild); postorder(t-rchild); printf(%c,t-da

11、ta); 返回目录返回目录19三、二叉树后序遍历的非递归实现三、二叉树后序遍历的非递归实现tHABCDEJIFGKL需保存的结点：需保存的结点： A B D Htttt=t输出：输出：Ht=tKKttt=t=tJtt=Ltt剩下的遍历过程由同学们自行完成！剩下的遍历过程由同学们自行完成！t JttLt=tttDt过程演示返回目录返回目录20在二叉树后序遍历过程中：在二叉树后序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分： 当前正在访问的子树（被指针t指向） 栈中等待访问的子树（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）当t 为空或t

12、所指向的子树访问完成后，若栈非空，则考虑两种情况： 若栈顶元素的右子树尚未访问，则访问其右子树，此 时栈顶元素不能出栈； 若栈顶元素的右子树已被访问，则访问该栈顶元素，并将其出栈；返回目录返回目录21因此为了区分栈顶元素的右子树是否已被访问，可为其设置一因此为了区分栈顶元素的右子树是否已被访问，可为其设置一标志标志tag .tag . tag=0tag=0，表示该栈顶元素的右子树尚未访问，该栈顶元素表示该栈顶元素的右子树尚未访问，该栈顶元素不能出栈，而应该进入其右子树进行访问；不能出栈，而应该进入其右子树进行访问； tag=1tag=1，表示表示该栈顶元素的右子树已被访问，可将该栈顶该栈顶元素

13、的右子树已被访问，可将该栈顶元素出栈，并输出其值；元素出栈，并输出其值； 显然，当一个元素刚进入栈时，其显然，当一个元素刚进入栈时，其tagtag值应该为值应该为0 0，而当，而当进入栈顶元素的右子树访问时，应该将其进入栈顶元素的右子树访问时，应该将其tagtag值改为值改为1 1。（4）只有）只有t所指向的子树访问完成且栈为空时，整个遍历过程所指向的子树访问完成且栈为空时，整个遍历过程才能结束。才能结束。请同学们仔细分析对照后序遍历和中序遍历的区别！请同学们仔细分析对照后序遍历和中序遍历的区别！二叉树后序遍历和中序遍历的主要区别在于二叉树后序遍历和中序遍历的主要区别在于对栈顶元素对栈顶元素的

14、处理的处理，即以上第（，即以上第（3）点。）点。返回目录返回目录22二叉树后序遍历的非递归实现算法：二叉树后序遍历的非递归实现算法：void postorder1(BiTree t) sqstack s; 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; typedef struct stack /*栈结构定义栈结构定义*/ BiTree data100; int tag100; /*为栈中每个元素设置的标记为栈中每个元素设置的标记*/ int top; /*栈顶指针栈顶指针*/ sqstack; 返回目录返回目录23 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; 返回目录返回目录24总结总结: :“遍历遍历”是二叉树各种操作的基础。是二叉树各种操作的基础。由上讨论得知：由上讨论得知： 遍历二叉树是以一定规则将二叉树中的结点排列成一个线遍历二叉树是以一定规则将二叉树中的结点排列成一