《非遞歸處理?xiàng)！穚pt課件

《《非遞歸處理?xiàng)！穚pt課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、非遞歸處理—棧1.先根：PreOrder(Bnodep)abc1Visit(a)1HoufengWang,ICLofPKU右子樹(shù)進(jìn)棧2Push(right(a))C=right(a)abc2HoufengWang,ICLofPKU左子樹(shù)進(jìn)棧a3Push(left(a))C=right(a)b=left(a)cb3HoufengWang,ICLofPKU棧頂元素出棧，重復(fù)！abc4Top&PopC=right(a)b作為新的子樹(shù)的根，重復(fù)上述步驟4HoufengWang,ICLofPKUPreOrder(BNodet){BNodea;pus

2、h(t);Do{a=top(paseq);//取棧paseq的棧頂元素pop(paseq);//出棧if(a!=NULL){visit(a);push(rightchild(a));//右孩子進(jìn)棧push(lightchild(a));//左孩子進(jìn)棧}//if(a!=NULL)}while(isEmptyStack_seq(paseq))//?？?，結(jié)束。}//PreOrder(BNodet5HoufengWang,ICLofPKU中根（對(duì)稱序）PreOrder(Bnodep)abc1Push(right(a))C=right(a)3Pus

3、h(left(a))C=right(a)aC=left(a)4Top&PopC=right(a)a2Push(a)C=right(a)a6HoufengWang,ICLofPKU如何保證根節(jié)點(diǎn)出棧后不再進(jìn)？特是標(biāo)記：棧內(nèi)每個(gè)元素有兩個(gè)域：structsnode{BNodeelement;chartag;}typedefstructsnodeDataType7HoufengWang,ICLofPKUInOrder(BNodet){DataTypea;a.element=t;a.element.tag=1;push(t);Do{a=top(p

4、aseq);//取棧paseq的棧頂元素pop(paseq);//出棧if(a.element!=NULL){If(a.tag!=1)visit(a.element);else{(右孩子andtag=1)進(jìn)棧(根andtag=0)進(jìn)棧(左孩子andtag=1)進(jìn)棧}}//(a.element!=NULL)}while(isEmptyStack_seq(paseq))//?？?，結(jié)束。}//InOrder(BNodet)8HoufengWang,ICLofPKU后根周游算法方法：見(jiàn)教材，兩種算法（后者以遞歸方式進(jìn)棧）基本思想：Step1:根進(jìn)

5、棧，Step2:棧頂元素出棧，且：分解①退棧元素的Tag=0，則輸出，否則：②退棧的元素再進(jìn)棧（Tag=0）退棧的元素左子節(jié)點(diǎn)進(jìn)棧（Tag=1）退棧的元素右子節(jié)點(diǎn)進(jìn)棧（Tag=1）Step2:重復(fù)Step2,直至棧空根進(jìn)棧(Tag=1)Step19HoufengWang,ICLofPKU后根周游算法如何寫算法？？(練習(xí)！??！)與教材上的算法比較10HoufengWang,ICLofPKU樹(shù)、樹(shù)林轉(zhuǎn)換為二叉樹(shù)將樹(shù)或樹(shù)林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)可以按以下步驟進(jìn)行：(1)在所有相鄰的兄弟結(jié)點(diǎn)之間加一條線；(2)對(duì)每個(gè)非終端結(jié)點(diǎn)，只保留它到其最左子女的

6、連線，刪去它與其它子女之間的連線；(3)以根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定角度（如45度），使其結(jié)構(gòu)層次分明。11HoufengWang,ICLofPKU5.16給出的例子顯示了這一轉(zhuǎn)換過(guò)程。12HoufengWang,ICLofPKU樹(shù)的長(zhǎng)子兄弟表示方法structCSNode;/*樹(shù)中結(jié)點(diǎn)結(jié)構(gòu)*/typedefstructCSNode*PCSNode;/*結(jié)點(diǎn)的指針類型*/structCSNode/*結(jié)點(diǎn)結(jié)構(gòu)定義*/{DataTypeinfo;/*結(jié)點(diǎn)中的元素*/PCSNodelchild;/*結(jié)點(diǎn)的最左子女的指針*/PCSNod

7、ersibling;/*結(jié)點(diǎn)的右兄弟的指針*/};將PCSNodersibling改為：PCSNoderchild;typedefstructCSNode*CSTree;/*樹(shù)類型定義*/13HoufengWang,ICLofPKUabcdefghij14HoufengWang,ICLofPKU設(shè)樹(shù)林F是有序的序列，F(xiàn)=T1，T2，…，Tn，對(duì)應(yīng)于F的二叉樹(shù)B(F)的定義如下：(1)若n=0，則B(F)為空；(2)若n＞0，則B(F)的根是T1的根w1，B(F)的左子樹(shù)是B(T11，T12，…，T1m)，其中T11，T12，…，T1m是T

8、1的子樹(shù)；B(F)的右子樹(shù)是B(T2，…，Tn)形式化描述15HoufengWang,ICLofPKU樹(shù)對(duì)應(yīng)到二叉樹(shù)其根結(jié)點(diǎn)的右子樹(shù)總是為空的。如圖5.17。16HoufengWang,ICL