最新二叉树遍历(递归—非递归转换)教学讲义PPT.ppt

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

1、二叉树遍历(递归—非递归转换)遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历6.3遍历二叉树本次课主要内容2遍历二叉树方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL返回目录3非递归算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)7pABCDEF

2、GiP->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访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)9ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)返回目录1

3、0二叉树的中序遍历一、二叉树中序遍历的定义：首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。中序遍历的结果：HtHABCDEJIFGKLDKJLBEIAFCG11二、二叉树中序遍历的递归实现#defineNULL0Typedefstructnode{chardata;structnode*lchild,*rchild;}*BiTree;Voidinorder(BiTreet){if(t!=NULL){inorder(t–>lchild);printf(“%c”,t–>data)inorder(t–>rchild);}}12三、二叉树中序遍历的

4、非递归实现tHABCDEJIFGKL需保存的结点：ABDHtttt=^t输出：Ht=^tJKDttt=^t=^tKtJtLt=^t=^LttBt剩下的遍历过程由同学们自行完成！13在二叉树中序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分：当前正在访问的子树（被指针t指向）栈中等待访问的子树当t所指向的子树访问完成后，若栈非空，则取出栈顶元素，访问其根结点，然后再进入其右子树访问（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。14二叉树中序遍历的非递归实现算法：typedefstr

5、uctstack{/*栈结构定义*/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;}15voidinorder1(BiTreet)/*非递归实现二叉树中序遍历*/{sqstacks;s.top=0;while((t!=NULL)

6、

7、(s.top!=0)){while(t!=NULL){push(&s,t);t

8、=t->lchild;}if(s.top!=0){t=pop(&s);printf("%c",t->data);t=t->rchild;}}}返回目录16二叉树的后序遍历一、二叉树后序遍历的定义：首先按照后序遍历的顺序访问根结点的左子树；然后按照后序遍历的顺序访问根结点的右子树。最后访问根结点；后序遍历的结果：HKLJDIEBFGCAtHABCDEJIFGKL17二、二叉树后序遍历的递归实现voidpostorder(BiTreet){if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%c",t->data

9、);}}18三、二叉树后序遍历的非递归实现tHABCDEJIFGKL需保存的结点：ABDHtttt=^t输出：Ht=^tKKttt=^t=^tJtt=^Ltt’剩下的遍历过程由同学们自行完成！t’J’tt’Lt=^t’ttDt’过程演示19在二叉树后序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分：当前正在访问的子树（被指针t指向）栈中等待访问的子树（1）必须使用栈记录尚未及时得到访问的子