棧的應(yīng)用和串圖

1、例例1 1數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換十進制N和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div為整除運算,mod為求余運算) 例如 (1348)10=(2504)8，其運算過程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2除基取余法void conversion( ) InitStack(s); scanf (“%d”,N); while(N) while(! StackEmpty(S) printf(“%d”,e); / conversi

2、onpush(S,N%8);N=N/8;Pop(S,e);例例2 表達式求值表達式求值大家考慮一下：4+2310/5的求值運算過程兩個相繼出現(xiàn)的運算符的優(yōu)先關(guān)系為了用棧來實現(xiàn)計算表達式，我們定義兩個棧，一個是OPTR，用以寄存運算符，一個是OPND，用以寄存操作數(shù)或運算結(jié)果。其基本思想如下：（1）首先置操作數(shù)棧為空棧，表達式起始符為“#”為棧的棧底元素；（2）依次讀入表達式的每個字符，若是操作數(shù)則進OPND棧，若是運算符則和OPTR棧頂 的元素比較優(yōu)先級后再做相應(yīng)的操作，直到表達式求值結(jié)束（即：OPTR的棧頂元素和當(dāng)前讀入的字符均為“#” ）OperandType EvaluateExpres

3、sion()/算術(shù)表達式求值的算符優(yōu)先算法，設(shè)OPTR和OPND分別是運算符棧和運算數(shù)棧，OP為運算符集合InitStack(OPTR); Push(OPTR,”#”);InitStack(OPND);c=getchar();While(c!=#|GetTop(OPTR)!=) if(!In(c,OP)Push(OPND,c); c=getchar();/不是運算符則進入 棧switch(Precede(GetTop(OPTR),c) case : 退棧并將運算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a);Push(OPND, Operat

4、e(a, theta, b); break; /switch/whileRerurn GetTop(OPND);/ EvaluateExpression現(xiàn)在以3（72）演示一下。 選擇題選擇題1. 對于棧操作數(shù)據(jù)的原則是（ ）。A. 先進先出 B. 后進先出 C. 后進后出 D. 不分順序 3. 一個棧的輸入序列為1,2,3n，若輸出序列的第一個元素是n，輸出第i（1=i1時，其余結(jié)點被分成m（m0）個互不相交的子集T1，T2，.，Tm，每個子集又是一棵樹。由此可以看出，樹的定義是遞歸。樹還有其他的表示形式:：1以嵌套集合的形式表示；2以廣義表的形式表示；3 以凹入法表示（類似書的編目）K L

5、 ME F G H I J B C DAA(a)(b)(c)基本術(shù)語基本術(shù)語結(jié)點：結(jié)點： 包含一個數(shù)據(jù)元素及若干指向其子樹根的分支。結(jié)點的度結(jié)點的度 ：結(jié)點擁有的子樹數(shù)，即結(jié)點的分支數(shù)。終端結(jié)點（葉子）：終端結(jié)點（葉子）： 度為0的結(jié)點。非終端結(jié)點非終端結(jié)點 ： 度不為0的結(jié)點。結(jié)點的層次結(jié)點的層次 ： 樹中根結(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推。樹的度：樹的度： 樹中所有結(jié)點度的最大值。樹的深度：樹的深度： 樹中結(jié)點的最大層次。有序樹、無序樹有序樹、無序樹 ： 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。森林：森林： 是m（m0）棵互不相

6、交的樹的集合。在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系又可以用家族關(guān)系描述，定義如下：孩子、雙親孩子、雙親 ： 結(jié)點子樹的根稱為這個結(jié)點的孩子，而這個結(jié)點又被稱為孩子的雙親。子孫子孫： 以某結(jié)點為根的子樹中的所有結(jié)點都被稱為是該結(jié)點的子孫。祖先祖先： 從根結(jié)點到該結(jié)點路徑上的所有結(jié)點。兄弟兄弟： 同一個雙親的孩子之間互為兄弟。堂兄弟堂兄弟： 雙親在同一層的結(jié)點互為堂兄弟。問題1：圖中結(jié)點個數(shù)和分支之間的關(guān)系？問題2：圖中某個結(jié)點的度數(shù)和從它引出引出的分支之間的關(guān)系？假設(shè)B為上圖所表的樹中分支（直線段）的個數(shù)，ni 表示度為i的結(jié)點的個數(shù)，n為結(jié)點總數(shù)，顯然有n=B+1, n=n0+n1+n2nk,B=n0*

7、0+n1*1+n2*2+nk*k,例如：. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ ）A5 B6 C7 D8Dn=B+1, n=n0+n1+n2nk,B=n0*0+n1*1+n2*2+nk*k,B= n0*0+1*4+2*2+3*1+4*1=15,n=B+1=16, 而n=n0+4+2+1+1=n0+8=16,n0=8 6.2.1 二叉樹的定義和基本運算二叉樹的定義和基本運算1. 定義定義定義：二叉樹是另一種樹形結(jié)構(gòu)。它與樹形結(jié)構(gòu)的區(qū)別是：（1）每個結(jié)點最多有兩棵子樹；（2）子樹有左右之分。 二叉樹也可以用遞歸的形式定義。即：二叉樹是n（n0）

8、個結(jié)點的有限集合。當(dāng)n=0時，稱為空二叉樹；當(dāng)n0時，有且僅有一個結(jié)點為二叉樹的根，其余結(jié)點被分成兩個互不相交的子集，一個作為左子集，另一個作為右子集，每個子集又是一個二叉樹。G HD E FB CA例如：二叉樹的二叉樹的5種形態(tài)：種形態(tài)：(a)(b)(c)(d)(e)二叉樹的第二叉樹的第1層只有一個根結(jié)點，所以，層只有一個根結(jié)點，所以，i=1時，時，2i-1=21-1=20=1成立。成立。 假設(shè)對所有的假設(shè)對所有的j，1ji成立，即第成立，即第j層上最多有層上最多有2j-1個結(jié)點成立。個結(jié)點成立。若若j=i-1，則第，則第j層上最多有層上最多有2j-1=2i-2個結(jié)點。由于在二叉樹中，個結(jié)點

9、。由于在二叉樹中，每個結(jié)點的度最大為每個結(jié)點的度最大為2，所以可以推導(dǎo)出第，所以可以推導(dǎo)出第i層最多的結(jié)點個數(shù)層最多的結(jié)點個數(shù)就是第就是第i-1層最多結(jié)點個數(shù)的層最多結(jié)點個數(shù)的2倍，即倍，即2i-2*2=2i-1。2二叉樹的性質(zhì)二叉樹的性質(zhì) 二叉樹具有下列二叉樹具有下列5個重要的性質(zhì)。個重要的性質(zhì)。 【性質(zhì)【性質(zhì)1】 在二叉樹的第在二叉樹的第i層上最多有層上最多有2i-1個結(jié)點（個結(jié)點（i1）。）?！拘再|(zhì)性質(zhì)2】 深度為深度為K的二叉樹最多有的二叉樹最多有2K-1個結(jié)點（個結(jié)點（K1）。）。 qqaaSnn1*1由性質(zhì)由性質(zhì)1可以得出，可以得出，1至至K層各層最多的結(jié)點個數(shù)分別為：層各層最多的

10、結(jié)點個數(shù)分別為：20,21,22,23,.,2K-1。這是一個以。這是一個以2為比值的等比數(shù)列，前為比值的等比數(shù)列，前n項之和的計項之和的計算公式為：算公式為： 其中其中 a1為第一項，為第一項，an為第為第n項，項，q為比值?？梢缘脼楸戎怠？梢缘玫?，該數(shù)列前到，該數(shù)列前K項之和為：項之和為：12212*1202KK【性質(zhì)【性質(zhì)3】 對于任意一棵二叉樹對于任意一棵二叉樹BT，如果度為，如果度為0的結(jié)點個數(shù)為的結(jié)點個數(shù)為n0，度為度為2的結(jié)點個數(shù)為的結(jié)點個數(shù)為n2，則，則n0=n2+1。證明：假設(shè)度為證明：假設(shè)度為1的結(jié)點個數(shù)為的結(jié)點個數(shù)為n1，結(jié)點總數(shù)為，結(jié)點總數(shù)為n，B為二叉樹中的為二叉樹中

11、的分支數(shù)。分支數(shù)。因為在二叉樹中，所有結(jié)點的度均小于或等于因為在二叉樹中，所有結(jié)點的度均小于或等于2，所以結(jié)點總數(shù)，所以結(jié)點總數(shù)為：為： n=n0+n1+n2 （1）再查看一下分支數(shù)。在二叉樹中，除根結(jié)點之外，每個結(jié)點都有一再查看一下分支數(shù)。在二叉樹中，除根結(jié)點之外，每個結(jié)點都有一個從上向下的分支指向，所以，總的結(jié)點個數(shù)個從上向下的分支指向，所以，總的結(jié)點個數(shù)n與分支數(shù)與分支數(shù)B之間的關(guān)之間的關(guān)系為：系為：n=B+1。又因為在二叉樹中，度為又因為在二叉樹中，度為1的結(jié)點產(chǎn)生的結(jié)點產(chǎn)生1個分支，度為個分支，度為2的結(jié)點產(chǎn)生的結(jié)點產(chǎn)生2個分支，所以分支數(shù)個分支，所以分支數(shù)B可以表示為：可以表示為：

12、B=n1+2n2。 將此式代入上式，得：將此式代入上式，得： n=n1+2n2+1 （2） 用（用（1）式減去（）式減去（2）式，并經(jīng)過調(diào)整后得到：）式，并經(jīng)過調(diào)整后得到：n0=n2+1。滿二叉樹：滿二叉樹： 如果一個深度為如果一個深度為K的二叉樹擁有的二叉樹擁有2K-1個結(jié)點，則將它稱為滿二叉樹。個結(jié)點，則將它稱為滿二叉樹。 8 9 10 11 12 13 14 154 5 6 72 31 完全二叉樹：有一棵深度為完全二叉樹：有一棵深度為h，具有，具有n個結(jié)點的二個結(jié)點的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右的順序分

13、別進行編號，且該二按從上到下，從左到右的順序分別進行編號，且該二叉樹中的每個結(jié)點分別與滿二叉樹中編號為叉樹中的每個結(jié)點分別與滿二叉樹中編號為1n的結(jié)點的結(jié)點位置一一對應(yīng)，則稱這棵二叉樹為位置一一對應(yīng)，則稱這棵二叉樹為完全二叉樹完全二叉樹。不是完全二叉樹不是完全二叉樹 【性質(zhì)性質(zhì)4】 具有具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為 log2n +1。其中，。其中， log2n 的結(jié)果是不大于的結(jié)果是不大于log2n的最大整的最大整數(shù)。數(shù)。 證明：假設(shè)具有證明：假設(shè)具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為K，則根據(jù)性質(zhì)則根據(jù)性質(zhì)2可以得出：可以得出： 2K-1-1

14、n2K-1 將不等式兩端加將不等式兩端加1得到：得到： 2K-1n2K 將不等式中的三項同取以將不等式中的三項同取以2為底的對數(shù)，并經(jīng)過化簡為底的對數(shù)，并經(jīng)過化簡后得到：后得到： K-1log2nn，則結(jié)點，則結(jié)點i沒有左孩子；否則其左孩子結(jié)沒有左孩子；否則其左孩子結(jié)點的編號為點的編號為2i。 （3）如果）如果2i+1n，則結(jié)點，則結(jié)點i沒有右孩子；否則其右孩沒有右孩子；否則其右孩子結(jié)點的編號為子結(jié)點的編號為2i+1。 下面我們利用數(shù)學(xué)歸納法證明這個性質(zhì)。下面我們利用數(shù)學(xué)歸納法證明這個性質(zhì)。 我們首先證明（我們首先證明（2）和（）和（3）。）。 當(dāng)當(dāng)i=1時，若時，若n3，則根的左、右孩子的編

15、號分別是，則根的左、右孩子的編號分別是2，3；若；若n3，則根沒有右孩子；若，則根沒有右孩子；若nn，且且2(i+1)=n時，結(jié)點時，結(jié)點i+1只有左孩子，而沒有右孩子；當(dāng)只有左孩子，而沒有右孩子；當(dāng)2(i+1)n，結(jié)點，結(jié)點i+1既沒有左孩子也沒有右孩子。既沒有左孩子也沒有右孩子。 以上證明得到（以上證明得到（2）和（）和（3）成立。）成立。 下面利用上面的結(jié)論證明（下面利用上面的結(jié)論證明（1）。）。 對于任意一個結(jié)點對于任意一個結(jié)點i，若，若2in，則左孩子的編號為，則左孩子的編號為2i，反過來結(jié)點反過來結(jié)點2i的雙親就是的雙親就是i，而，而 2i/2 =i；若；若2i+1n，則右，則右孩

16、子的編號為孩子的編號為2i+1，反過來結(jié)點，反過來結(jié)點2i+1的雙親就是的雙親就是i，而，而 (2i+1)/2 =i，由此可以得出（，由此可以得出（1）成立。）成立。 6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 二叉樹也可以采用兩種存儲方式：順序存儲結(jié)構(gòu)和二叉樹也可以采用兩種存儲方式：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。鏈式存儲結(jié)構(gòu)。1. 1. 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)適用于完全二叉樹。其存儲形式為：這種存儲結(jié)構(gòu)適用于完全二叉樹。其存儲形式為：用一組連續(xù)的存儲單元按照完全二叉樹的每個結(jié)點編號用一組連續(xù)的存儲單元按照完全二叉樹的每個結(jié)點編號的順序存放結(jié)點內(nèi)容。下面是一棵二叉樹及其相應(yīng)的存

17、的順序存放結(jié)點內(nèi)容。下面是一棵二叉樹及其相應(yīng)的存儲結(jié)構(gòu)。儲結(jié)構(gòu)。84 5 6 72 313 32 2 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu) 在順序存儲結(jié)構(gòu)中，利用編號表示元素的位置及元在順序存儲結(jié)構(gòu)中，利用編號表示元素的位置及元素之間孩子或雙親的關(guān)系，因此對于非完全二叉樹，素之間孩子或雙親的關(guān)系，因此對于非完全二叉樹，需要將空缺的位置用特定的符號填補，若空缺結(jié)點較需要將空缺的位置用特定的符號填補，若空缺結(jié)點較多，勢必造成空間利用率的下降。在這種情況下，就多，勢必造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈式存儲結(jié)構(gòu)。應(yīng)該考慮使用鏈式存儲結(jié)構(gòu)。 常見的二叉樹結(jié)點結(jié)構(gòu)如下所示：常見的二叉樹結(jié)點結(jié)構(gòu)如下

18、所示： 其中，其中，lchild和和rchild是分別指向該結(jié)點左孩子和右孩是分別指向該結(jié)點左孩子和右孩子的指針，子的指針，data是數(shù)據(jù)元素的內(nèi)容。在是數(shù)據(jù)元素的內(nèi)容。在C語言中的類型定語言中的類型定義為：義為： typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchlid; BiTNode,*BiTree;G HD E FB CA G H D E F B CABT一棵二叉樹及相應(yīng)的鏈式存儲結(jié)構(gòu)一棵二叉樹及相應(yīng)的鏈式存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)的特點是尋找孩子結(jié)點容易，雙親比較困難。因此，若需要頻繁地尋找雙親，可以給每個

19、結(jié)點添加一個指向雙親結(jié)點的指針域，其結(jié)點結(jié)構(gòu)如下所示。注：在具體的應(yīng)用中采用什么存儲結(jié)構(gòu)，除根據(jù)二叉樹的形態(tài)之注：在具體的應(yīng)用中采用什么存儲結(jié)構(gòu)，除根據(jù)二叉樹的形態(tài)之外還應(yīng)考慮需進行何種操作。外還應(yīng)考慮需進行何種操作。5. 在下述結(jié)論中，正確的是（ ）只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A B C D8若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ ）A9 B11 C15 D不確定 9在一棵三叉樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個

20、，則度為0的結(jié)點數(shù)為（ ）個A4 B5 C6 D7 DBC11具有10個葉結(jié)點的二叉樹中有（ ）個度為2的結(jié)點，A8 B9 C10 Dll12一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）A 250 B 500 C254 D505 E以上答案都不對 16. 有關(guān)二叉樹下列說法正確正確的是（ ）A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個結(jié)點的度為2 D二叉樹中任何一個結(jié)點的度都為217二叉樹的第I層上最多含有結(jié)點數(shù)為（ ）A2I B 2I-1-1 C 2 I-1 D2I -1BEBC18. 一個具有1025個結(jié)點的二叉樹的高h為（ ）A11 B10 C11至

21、1025之間 D10至1024之間19一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有( )結(jié)點A2h B2h-1 C2h+1 Dh+1 20對于有n 個結(jié)點的二叉樹, 其高度為（ ）Anlog2n Blog2n Clog2n+1 D不確定21. 一棵具有 n個結(jié)點的完全二叉樹的樹高度（深度）是（ ）Alog2n+1 Blog2n+1 Clog2n Dlog2n-122深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=k=h) Amk-1 Bmk-1 Cmh-1 Dmh-1CBDAA23在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（ ）A2k-1 B2k C2k-1 Dlog2k+124高度為 K的二叉樹最大的結(jié)點數(shù)為（ ）。A2k B2k-1 C2k -1 D2k-1-125. 一棵樹高為K的完全二叉樹至少有（ ）個結(jié)點A2k 1 B. 2k-1 1 C. 2k-1 D. 2k26. 將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度（ ）A4 B5 C6 D7CCCC二、填空題二、填空題1二叉樹由_(1)_，_(2)_，_(3)_三個基本單元組成。6具有256個結(jié)點的完全二叉樹的深度為_。 7已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有_個葉子結(jié)點。8