1、2020/6/19,數(shù)據(jù)結(jié)構(gòu)二叉樹的遍歷,1,遍歷二叉樹,制作人：計(jì)科系孫玉霞,數(shù)據(jù)結(jié)構(gòu),2,遍歷二叉樹二叉樹的先序遍歷二叉樹的中序遍歷二叉樹的后序遍歷,6.3遍歷二叉樹,本次課主要內(nèi)容,3,遍歷二叉樹方法先序遍歷：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)按層次遍歷：從上到下、從左到右訪問各結(jié)點(diǎn),返回目錄,4,DLR,先序遍歷序列：ABDC,二叉樹的先序遍歷,5,算法實(shí)現(xiàn)：,進(jìn)入非遞歸算法,先序遍歷過程演示,6,voidpreorder(BiTreet)if(t!=NULL)prin

2、tf(%dt,t-data);preorder(t-lchild);preorder(t-rchild);,返回,返回,返回,返回,A,C,B,D,返回,先序序列：ABDC,Back,7,非遞歸算法,8,9,10,返回目錄,11,二叉樹的中序遍歷,一、二叉樹中序遍歷的定義：首先按照中序遍歷的順序訪問根結(jié)點(diǎn)的左子樹；然后訪問根結(jié)點(diǎn)；最后按照中序遍歷的順序訪問根結(jié)點(diǎn)的右子樹。,中序遍歷的結(jié)果：,H,D,K,J,L,B,E,I,A,F,C,G,12,二、二叉樹中序遍歷的遞歸實(shí)現(xiàn),#defineNULL0Typedefstructnodechardata;structnode*lchild,*rchi

3、ld;*BiTree;Voidinorder(BiTreet)if(t!=NULL)inorder(tlchild);printf(“%c”,tdata)inorder(trchild);,13,三、二叉樹中序遍歷的非遞歸實(shí)現(xiàn),B,D,H,t=,輸出：H,t=,J,K,D,t=,t=,K,J,L,t=,t=,L,B,剩下的遍歷過程由同學(xué)們自行完成！,14,在二叉樹中序遍歷過程中：,（2）在遍歷過程中要做的工作始終分成兩部分：當(dāng)前正在訪問的子樹（被指針t指向）棧中等待訪問的子樹當(dāng)t所指向的子樹訪問完成后，若棧非空，則取出棧頂元素，訪問其根結(jié)點(diǎn)，然后再進(jìn)入其右子樹訪問,（1）必須使用棧記錄尚未及時(shí)

4、得到訪問的子樹的根和右子樹（實(shí)際操作時(shí)只需記住子樹的根即可）,（3）只有t所指向的子樹訪問完成且棧為空時(shí)，整個(gè)遍歷過程才能結(jié)束。,15,二叉樹中序遍歷的非遞歸實(shí)現(xiàn)算法：,typedefstructstack/*棧結(jié)構(gòu)定義*/BiTreedata100;inttop;sqstack;voidpush(sqstack*s,BiTreet)/*進(jìn)棧*/s.datas.top+=t;BiTreepop(sqstack*s)/*出棧*/if(s.top!=0)return(s.data-s.top);elsereturnNULL;,16,voidinorder1(BiTreet)/*非遞歸實(shí)現(xiàn)二叉樹中序

5、遍歷*/sqstacks;s.top=0;while(t!=NULL)|(s.top!=0)while(t!=NULL)push(,返回目錄,17,二叉樹的后序遍歷,一、二叉樹后序遍歷的定義：首先按照后序遍歷的順序訪問根結(jié)點(diǎn)的左子樹；然后按照后序遍歷的順序訪問根結(jié)點(diǎn)的右子樹。最后訪問根結(jié)點(diǎn)；,后序遍歷的結(jié)果：,HKLJDIEBFGCA,18,二、二叉樹后序遍歷的遞歸實(shí)現(xiàn)voidpostorder(BiTreet)if(t!=NULL)postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);,19,三、二叉樹后序遍歷的非遞歸實(shí)現(xiàn),B,D

6、,H,t=,輸出：H,t=,K,K,t=,t=,J,t=,L,剩下的遍歷過程由同學(xué)們自行完成！,J,L,t=,D,過程演示,20,在二叉樹后序遍歷過程中：,（2）在遍歷過程中要做的工作始終分成兩部分：當(dāng)前正在訪問的子樹（被指針t指向）棧中等待訪問的子樹,（1）必須使用棧記錄尚未及時(shí)得到訪問的子樹的根和右子樹（實(shí)際操作時(shí)只需記住子樹的根即可）,（3）當(dāng)t為空或t所指向的子樹訪問完成后，若棧非空，則考慮兩種情況：若棧頂元素的右子樹尚未訪問，則訪問其右子樹，此時(shí)棧頂元素不能出棧；若棧頂元素的右子樹已被訪問，則訪問該棧頂元素，并將其出棧；,21,因此為了區(qū)分棧頂元素的右子樹是否已被訪問，可為其設(shè)置一標(biāo)

7、志tag.tag=0，表示該棧頂元素的右子樹尚未訪問，該棧頂元素不能出棧，而應(yīng)該進(jìn)入其右子樹進(jìn)行訪問；tag=1，表示該棧頂元素的右子樹已被訪問，可將該棧頂元素出棧，并輸出其值；顯然，當(dāng)一個(gè)元素剛進(jìn)入棧時(shí)，其tag值應(yīng)該為0，而當(dāng)進(jìn)入棧頂元素的右子樹訪問時(shí)，應(yīng)該將其tag值改為1。（4）只有t所指向的子樹訪問完成且棧為空時(shí)，整個(gè)遍歷過程才能結(jié)束。,請同學(xué)們仔細(xì)分析對照后序遍歷和中序遍歷的區(qū)別！,二叉樹后序遍歷和中序遍歷的主要區(qū)別在于對棧頂元素的處理，即以上第（3）點(diǎn)。,22,二叉樹后序遍歷的非遞歸實(shí)現(xiàn)算法：,voidpostorder1(BiTreet)sqstacks;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;,typedefstructstack/*棧結(jié)構(gòu)定義*/BiTreedata100;inttag100;/*為棧中每個(gè)元素設(shè)置的標(biāo)記*/inttop;/*棧頂指針*/sqstack;,23,while(s.top0),24,總結(jié):“遍歷”是二叉樹各種操作的基礎(chǔ)。由上討論得知：遍歷二叉樹是以一定規(guī)則將二叉樹中的結(jié)點(diǎn)排列成一個(gè)線性序列，得到二叉樹中結(jié)點(diǎn)的先序序列或中序序列或后序序列。這實(shí)質(zhì)上是對一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化。,返