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

《二叉树遍历(递归—非递归转换).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、——遍历二叉树制作人：计科系孙玉霞数据结构7/24/20211数据结构——二叉树的遍历遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历6.3遍历二叉树本次课主要内容2遍历二叉树方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL返回目录3ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC二叉树的先序遍历4算法实现：进入

2、非递归算法递归算法先序遍历过程演示5voidpreorder(BiTreet){if(t!=NULL){printf("%dt",t->data);preorder(t->lchild);preorder(t->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>

3、右是空返回pre(TR);先序序列：ABDCTTTTBack6非递归算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)7pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)8ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：

4、CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)9ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)返回目录10二叉树的中序遍历一、二叉树中序遍历的定义：首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。中序遍历的结果：HtHABCDEJIFGKLDKJLBEIAFCG11二、二叉树中序遍历的递归实现#d

5、efineNULL0Typedefstructnode{chardata;structnode*lchild,*rchild;}*BiTree;Voidinorder(BiTreet){if(t!=NULL){inorder(t–>lchild);printf(“%c”,t–>data)inorder(t–>rchild);}}12三、二叉树中序遍历的非递归实现tHABCDEJIFGKL需保存的结点：ABDHtttt=^t输出：Ht=^tJKDttt=^t=^tKtJtLt=^t=^LttBt剩下的遍历过程由同学们自行完成！13在二叉树中序遍历过程中

6、：（2）在遍历过程中要做的工作始终分成两部分：当前正在访问的子树（被指针t指向）栈中等待访问的子树当t所指向的子树访问完成后，若栈非空，则取出栈顶元素，访问其根结点，然后再进入其右子树访问（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。14二叉树中序遍历的非递归实现算法：typedefstructstack{/*栈结构定义*/BiTreedata[100];inttop;}sqstack;voidpush(sqstack*s,BiTreet)/*

7、进栈*/{s.data[s.top++]=t;}BiTreepop(sqstack*s)/*出栈*/{if(s.top!=0)return(s.data[--s.top]);elsereturnNULL;}15voidinorder1(BiTreet)/*非递归实现二叉树中序遍历*/{sqstacks;s.top=0;while((t!=NULL)

8、

9、(s.top!=0)){while(t!=NULL){push(&s,t);t=t->lchild;}if(s.top!=0){t=pop(&s);printf("%c",t->data)

10、;t=t->rchild;}}}返回目录16二叉树的后序遍历一、二叉树后序遍历的定义：首先按照后序遍