二叉树遍历(递归—非递归转换)课件.pptVIP

数据结构——遍历二叉树制作人：计科系孙玉霞3/5/2024数据结构——二叉树的遍历1

返回目录6.3遍历二叉树遍历二叉树本次课主要内容二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历2

返回目录?遍历二叉树v方法l先序遍历：先访问根结点,然后分别先序遍历左子树、右子树l中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树l后序遍历：先后序遍历左、右子树，然后访问根结点l按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL返回目录3

?二叉树的先序遍历返回目录DALRADLRDLRCBDBCDLR先序遍历序列：ABDCD4

返回目录算法实现：递归算法先序遍历过程演示进入非递归算法5

TT返回目录voidpreorder(BiTreet){if(t!=NULL)ATT{printf(%d\t,t-data);preorder(t-lchild);preorder(t-rchild);}BC左是空返回左是空返回右是空返回DT}返回左是空返回右是空返回TBTDTprintf(B);AT主程序printf(D);pre(TL);pre(TR);printf(A);pre(TL);pre(TR);返回pre(TL);pre(TR);TPre(T)TC返回Tprintf(C);返回Tpre(TL);pre(TR);先序序列：ABDC返回Back6

返回目录非递归算法ppADGADGBBiCCP-BP-AiEFEFP-A(2)(1)AABBpiP-CP-BiCDGCDGP-BP-Ap=NULLEFEFP-A(3)7(4)访问：C

返回p目录ADGADGBpBCiCiP-DP-AEFP-AEF(5)访问：CB(6)访问：CBAABBiP-EP-DP-AiCDGCDGP-DP-AEFEFp访问：CB访问：CBE(8)(7)8p

返回目录ADGADGBiBP-GP-DP-AiCCP-DP-AEFEF访问：CBE(9)访问：CBEG(10)P=NULLpAABpBpiCDGCDEP-FP-AiEFFP-A访问：CBEGD访问：CBEGDG(11)(12)9

p返回目录ADGADGBBCCiEFiEFP-Ap=NULL(13)访问：CBEGDFA(14)访问：CBEGDFp=NULLABCDGEFi返回目录(15)10访问：CBEGDFA

?二叉树的中序遍历返回目录一、二叉树中序遍历的定义：首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。tA中序遍历的结果：BJCDEFGHDKJLBEIAFCGHIKL11

返回二、二叉树中序遍历的递归实现目#defineNULL0录Typedefstructnode{chardata;structnode*lchild,*rchild;}*BiTree;Voidinorder(BiTreet){if(t!=NULL){inorder(t–lchild);printf(“%c”,t–data)inorder(t–rchild);}}12

返回目录三、二叉树中序遍历的非递归实现t需保存的结点：AtABDLJHKBCtttDEFGtt输出：HDKJLBHJIt=^t=^ttKLt=^t=^t=^t=^剩下的遍历过程由同学们自行完成！13

返回目录在二叉树中序遍历过程中：（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（2）在遍历过程中要做的工作始终分成两部分：当前正在访问的子树（被指针t指向）栈中等待访问的子树当t所指向的子树访问完成后，若栈非空，则取出栈顶元素，访问其根结点，然后再进入其右子树访问（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。14

返回目二叉树中序遍历的非递归实现算法：录typedefstructstack{/*栈结构定义*/BiTreedata[100];inttop;}sqstack;voidpush(sqstack*s,BiTreet)/*进栈*/{s.data[s.top++]=t;}BiTreepop(sqstack*s)/*出栈*/{if(s.top!=0)return(s.data[--s.top]);elsereturnNULL;}15

返回目录voidinorder1(BiTreet)/*非递归实现二叉树中序遍历*/{sqstacks;s.top=0;while((t!=NULL)||(s.top!=0)){wh