[計(jì)算機(jī)軟件及應(yīng)用]棧的應(yīng)用和串圖

1、例1數(shù)制轉(zhuǎn)換,十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題,其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div為整除運(yùn)算,mod為求余運(yùn)算) 例如 (1348)10=(2504)8，其運(yùn)算過程如下： n n div 8 n mod 8 1348 16

2、8 4 168 21 0 21 2 5 2 0 2,除基取余法,void conversion( ) { InitStack(s); scanf (“%d”,N);

3、 while(N){ } while(! StackEmpty(S)){ printf(“%d”,e); } } // conversion,push(S,N%8);,N=N/8;,Pop(S,e);,例2 表達(dá)式求值大家考慮一下：4+2×3－10/5的求值運(yùn)算過程兩個(gè)相繼出現(xiàn)的運(yùn)算符

4、的優(yōu)先關(guān)系,為了用棧來(lái)實(shí)現(xiàn)計(jì)算表達(dá)式，我們定義兩個(gè)棧，一個(gè)是OPTR，用以寄存運(yùn)算符，一個(gè)是OPND，用以寄存操作數(shù)或運(yùn)算結(jié)果。,其基本思想如下：（1）首先置操作數(shù)棧為空棧，表達(dá)式起始符為“#”為棧的棧底元素；,（2）依次讀入表達(dá)式的每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧頂 的元素比較優(yōu)先級(jí)后再做相應(yīng)的操作，直到表達(dá)式求值結(jié)束（即：OPTR的棧頂元素和當(dāng)前讀入的字符均為“#” ）,,OperandType Ev

5、aluateExpression()//算術(shù)表達(dá)式求值的算符優(yōu)先算法，設(shè)OPTR和OPND分別是運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合InitStack(OPTR); Push(OPTR,”#”);InitStack(OPND);c=getchar();While(c!=‘#’||GetTop(OPTR)!=‘＃’){ if(!In(c,OP)){Push(OPND,c); c=getchar();}//不是運(yùn)算符則進(jìn)入 棧

6、,switch(Precede(GetTop(OPTR),c)){ case ‘<’: //棧頂元素的優(yōu)先級(jí)低,Push(OPTR, c); c=getchar(); break;,case ‘=’: //脫括號(hào)并接受下一個(gè)字符；,Pop(OPTR,x);c=getchar(); break;,case ‘>’: 退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR, theta);

7、 Pop(OPND, b); Pop(OPND, a);,Push(OPND, Operate(a, theta, b)); break; }//switch,}//whileRerurn GetTop(OPND);}// EvaluateExpression現(xiàn)在以3×（7－2）演示一下。,選擇題1. 對(duì)于棧操作數(shù)據(jù)的原則是（ ）。先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不

8、分順序 3. 一個(gè)棧的輸入序列為1,2,3…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（ ）。A. 不確定 B. n-i+1 C. i D. n-i4. 若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（ ）。 A. i-j-1 B. i-j C.

9、 j-i+1 D. 不確定的5. 若已知一個(gè)棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是( )。 A. i B. n-i C. n-i+1 D. 不確定,B,B,D,D,2. 在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否( ① ),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否( ② )。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧

10、的最大容量為( ③ )。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 ( ④ )分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)( ⑤ )時(shí)，才產(chǎn)生上溢。 ①, ②: A. 空 B. 滿 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D.

11、n/2 ④: A. 長(zhǎng)度 B. 深度 C. 棧頂 D. 棧底 ⑤: A. 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn).B. 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn). C. 兩個(gè)棧的棧頂在?？臻g的某一位置相遇. D. 兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.,B,B,A,D,C,10. 某堆棧的輸入序列為a, b，c ，d,下面的四個(gè)序列中，不可能是它

12、的輸出序列的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b11. 設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則下面得不到的序列為（ ）。A．fedcba B. bcafed C. dcefba D. cabdef12. 設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的

13、過程中允許出棧），下列得不到的出棧排列是( )。A．XYZ B. YZX C. ZXY D. ZYX13. 輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為（ ）A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push

14、,pop D. push,pop,push,push,pop,pop,D,D,C,B,14. 若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是( )。A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1 C. top:=top-1; V [top]:=x D. V [to

15、p]:=x; top:=top-115. 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個(gè)棧( i =1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（ ）。A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2]16. 棧在（ ）中應(yīng)用。遞歸調(diào)用

16、 B. 子程序調(diào)用 C. 表達(dá)式求值 D. A，Ｂ，Ｃ,B,D,C,注：上述算法的匹配過程易于理解，且在某些應(yīng)用場(chǎng)合，如文本編輯等，效率也較高，但是在有些情況下，該算法的效率卻很低。,其主串的指針i在不斷的回溯，如i=3,變?yōu)閕=2,i=7變?yōu)閕=4…其時(shí)間復(fù)雜度可達(dá)到O(n*m).,KMP算法，其時(shí)間復(fù)雜度為：O(n+m),,如果主串i上的字符不匹配的時(shí)候，則主串i上的字符應(yīng)該再與模式串上的那個(gè)字符相比較，也就

17、是說(shuō)，如果出現(xiàn)不匹配的時(shí)候，模式串應(yīng)該“向右滑動(dòng)”多遠(yuǎn)？,,,模式串的next函數(shù)定義如下：,例子：1.求模式串 T=‘a(chǎn) b c a c’的next函數(shù)值 next= 0 1 1 1 22.求模式串 T=‘a(chǎn) b a a b c a c’的next函數(shù)值,,因?yàn)閚ext[3]=1，說(shuō)明主串的第3個(gè)字符a（i=3）應(yīng)該再與模式串的第1個(gè)字符a相比較，故出現(xiàn)了第二趟比較的情況；,因next[5]=2，說(shuō)明

18、主串的第7個(gè)字符a（i=7）應(yīng)該再與模式串的第2個(gè)字符b相比較，故出現(xiàn)了第三趟比較的情況。,注：next[j]僅取決于模式串本身而和相匹配的主串無(wú)關(guān)。下面推導(dǎo)其遞推算法,顯然：next[1]=0;,假設(shè)next[j]=k,則說(shuō)明在模式串中存在：,‘p1p2…pk-1’=‘pj-k+1 pj-k+2…pj-1’,怎么求next[j+1]?,如果pk=pj，則說(shuō)明:,‘p1p2…pk-1 pk’=‘pj-k+1 pj-k+2…pj-1 pj

19、’,于是next[j+1]=k+1=next[j]+1,如果pk!=pj，則這又是一個(gè)模式匹配問題，其中主串和模式串相同,于是模式串應(yīng)該向右滑動(dòng)至pj與pnext[k]相對(duì)齊，繼續(xù)比較，又分兩種情況： pj= pnext[k]和pj與 pnext[k]不相等。,若pj= pnext[k],則next[j+1]=next[k]+1;,若pj!=pnext[k] , 則考察pj和pnext[next[k]] ,,若pj=p next[ne

20、xt[k]] , 則next[j+1]=next[next[k]]+1,若pj!=p next[next[k]] ,則繼續(xù)比較下去,,若pj!=pnext[next[k]]=p1, 即: next[next[k]]=1,,則next[j+1]=1.,例子：T=‘a(chǎn)baabcac’,next[3]=next[2+1], next[2]=1, 而p2!=p1, 所以next[3]=next[1]+1=1,next[4]=next[

21、3+1], next[3]=1, 因?yàn)閜3=p1,所以next[4]=next[3]+1=2,next[5]=next[4+1], next[4]=2, 而p4!=p2, 又next[2]=1, p4=p1,,所以,next[5]=next[2]+1=2.,,next[6]=next[5+1], next[5]=2, 因?yàn)閜5=p2, 所以next[6]=next[5]+1=3.,next[7]=next[6+1], n

22、ext[6]=3, 而p6!=p3, next[3]=1, 又p6!=p1,,所以next[7]=next[1]+1=1,,next[8]=next[7+1], next[7]=1, 因?yàn)閜7=p1, 因此next[8]=next[7]+1=2,上述定義的函數(shù)在某些情況下尚有缺陷，如,在出現(xiàn)這種情況的時(shí)候，即第一個(gè)字符與主串中的相應(yīng)字符不匹配的時(shí)候，因?yàn)槟Ｊ酱八膫€(gè)字符相同，主串中的字符不需要和第2，3，4個(gè)字符比較，所以可

23、以把其next[j]作如下修改：,4．已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（ ）。A．0123 B．1123 C．1231 D．1211,5．串 ‘a(chǎn)babaaababaa’ 的next數(shù)組為（ ）。A．012345678999 B．012121111212 C．011234223456 D．0123012322345,6．字符串‘a(chǎn)babaabab’

24、 的nextval 為（ ）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ),A,C,A,1、樹的定義和基本術(shù)語(yǔ),2、 二叉樹,6.1 樹,6.1.1 樹的定義和基本運(yùn)算1. 定義樹是一種常用的非線性結(jié)構(gòu)。我們可以這樣定義：樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合

25、。若n=0，則稱為空樹；否則，有且僅有一個(gè)特定的結(jié)點(diǎn)被稱為根，當(dāng)n>1時(shí)，其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的子集T1，T2，...，Tm，每個(gè)子集又是一棵樹。由此可以看出，樹的定義是遞歸。,樹還有其他的表示形式:：1以嵌套集合的形式表示；2以廣義表的形式表示；3 以凹入法表示（類似書的編目）,K L M,E F G

26、 H I J,B C D,A,A,(a),(b),(c),基本術(shù)語(yǔ),結(jié)點(diǎn)： 包含一個(gè)數(shù)據(jù)元素及若干指向其子樹根的分支。結(jié)點(diǎn)的度 ：結(jié)點(diǎn)擁有的子樹數(shù)，即結(jié)點(diǎn)的分支數(shù)。終端結(jié)點(diǎn)（葉子）： 度為0的結(jié)點(diǎn)。非終端結(jié)點(diǎn) ： 度不為0的結(jié)點(diǎn)。結(jié)點(diǎn)的層次 ： 樹中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹的根為第2層，以此類推。樹的度： 樹中所有結(jié)點(diǎn)度

27、的最大值。樹的深度： 樹中結(jié)點(diǎn)的最大層次。有序樹、無(wú)序樹 ： 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無(wú)序樹。,森林： 是m（m≥0）棵互不相交的樹的集合。在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系又可以用家族關(guān)系描述，定義如下：孩子、雙親 ： 結(jié)點(diǎn)子樹的根稱為這個(gè)結(jié)點(diǎn)的孩子，而這個(gè)結(jié)點(diǎn)又被稱為孩子的雙親。子孫： 以某結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)都被稱為是該結(jié)點(diǎn)的子孫。祖先： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑

28、上的所有結(jié)點(diǎn)。兄弟： 同一個(gè)雙親的孩子之間互為兄弟。堂兄弟： 雙親在同一層的結(jié)點(diǎn)互為堂兄弟。,問題1：圖中結(jié)點(diǎn)個(gè)數(shù)和分支之間的關(guān)系？,問題2：圖中某個(gè)結(jié)點(diǎn)的度數(shù)和從它引出的分支之間的關(guān)系？,假設(shè)B為上圖所表的樹中分支（直線段）的個(gè)數(shù)，ni 表示度為i的結(jié)點(diǎn)的個(gè)數(shù)，n為結(jié)點(diǎn)總數(shù)，顯然有,n=B+1, n=n0+n1+n2…nk,,B=n0*0+n1*1+n2*2+…nk*k,,例如：. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)

29、個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ ）A．5 B．6 C．7 D．8,D,n=B+1, n=n0+n1+n2…nk,,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 二叉樹,,6.2.1 二叉樹的定義和基本運(yùn)算1

30、. 定義定義：二叉樹是另一種樹形結(jié)構(gòu)。它與樹形結(jié)構(gòu)的區(qū)別是：（1）每個(gè)結(jié)點(diǎn)最多有兩棵子樹；（2）子樹有左右之分。 二叉樹也可以用遞歸的形式定義。即：二叉樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱為空二叉樹；當(dāng)n>0時(shí)，有且僅有一個(gè)結(jié)點(diǎn)為二叉樹的根，其余結(jié)點(diǎn)被分成兩個(gè)互不相交的子集，一個(gè)作為左子集，另一個(gè)作為右子集，每個(gè)子集又是一個(gè)二叉樹。,G H,D

31、 E F,B C,A,,,,,,,,,例如：,二叉樹的5種形態(tài)：,ø,(a),(b),(c),(d),(e),二叉樹的第1層只有一個(gè)根結(jié)點(diǎn)，所以，i=1時(shí)，2i-1=21-1=20=1成立。 假設(shè)對(duì)所有的j，1≤j<i成立，即第j層上最多有2j-1個(gè)結(jié)點(diǎn)成立。若j=i-1，則第j層上最多有2j-1=2

32、i-2個(gè)結(jié)點(diǎn)。由于在二叉樹中，每個(gè)結(jié)點(diǎn)的度最大為2，所以可以推導(dǎo)出第i層最多的結(jié)點(diǎn)個(gè)數(shù)就是第i-1層最多結(jié)點(diǎn)個(gè)數(shù)的2倍，即2i-2*2=2i-1。,2．二叉樹的性質(zhì) 二叉樹具有下列5個(gè)重要的性質(zhì)。 【性質(zhì)1】 在二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。,【性質(zhì)2】 深度為K的二叉樹最多有2K-1個(gè)結(jié)點(diǎn)（K≥1）。,由性質(zhì)1可以得出，1至K層各層最多的結(jié)點(diǎn)個(gè)數(shù)分別為：20,21,22,23,...,2K-1。這是一個(gè)以2為

33、比值的等比數(shù)列，前n項(xiàng)之和的計(jì)算公式為：,其中 a1為第一項(xiàng)，an為第n項(xiàng)，q為比值?？梢缘玫?，該數(shù)列前K項(xiàng)之和為：,,,【性質(zhì)3】 對(duì)于任意一棵二叉樹BT，如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1。,證明：假設(shè)度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，結(jié)點(diǎn)總數(shù)為n，B為二叉樹中的分支數(shù)。,因?yàn)樵诙鏄渲校薪Y(jié)點(diǎn)的度均小于或等于2，所以結(jié)點(diǎn)總數(shù)為：

34、 n=n0+n1+n2 （1）,再查看一下分支數(shù)。在二叉樹中，除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有一個(gè)從上向下的分支指向，所以，總的結(jié)點(diǎn)個(gè)數(shù)n與分支數(shù)B之間的關(guān)系為：n=B+1。,又因?yàn)樵诙鏄渲?，度?的結(jié)點(diǎn)產(chǎn)生1個(gè)分支，度為2的結(jié)點(diǎn)產(chǎn)生2個(gè)分支，所以分支數(shù)B可以表示為：B=n1+2n2。 將此式代入上式，得：

35、 n=n1+2n2+1 （2） 用（1）式減去（2）式，并經(jīng)過調(diào)整后得到：n0=n2+1。,滿二叉樹： 如果一個(gè)深度為K的二叉樹擁有2K-1個(gè)結(jié)點(diǎn)，則將它稱為滿二叉樹。,8 9 10 11 12 13 14 15,4 5 6 7,2 3,1,完全

36、二叉樹：有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹中編號(hào)為1~n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹。,不是完全二叉樹,【性質(zhì)4】 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 ?log2n?+1。其中，?log2n? 的結(jié)果是不大于log2n的最大整數(shù)。 證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為K

37、，則根據(jù)性質(zhì)2可以得出： 2K-1-1<n≤2K-1 將不等式兩端加1得到： 2K-1≤n<2K 將不等式中的三項(xiàng)同取以2為底的對(duì)數(shù)，并經(jīng)過化簡(jiǎn)后得到： K-1≤log2n<K 由此可以得到：?log2n? =K-1。整理后得

38、到：K= ?log2n?+1。,【性質(zhì)5】 對(duì)于有n個(gè)結(jié)點(diǎn)的完全二叉樹中的所有結(jié)點(diǎn)按從上到下，從左到右的順序進(jìn)行編號(hào)，則對(duì)任意一個(gè)結(jié)點(diǎn)i （1≤i≤n），都有： （1）如果i=1，則結(jié)點(diǎn)i是這棵完全二叉樹的根，沒有雙親；否則其雙親結(jié)點(diǎn)的編號(hào)為 ?i/2?。 （2）如果2i>n，則結(jié)點(diǎn)i沒有左孩子；否則其左孩子結(jié)點(diǎn)的編號(hào)為2i。 （3）如果2i+1>n，則結(jié)點(diǎn)i沒有右孩子

39、；否則其右孩子結(jié)點(diǎn)的編號(hào)為2i+1。 下面我們利用數(shù)學(xué)歸納法證明這個(gè)性質(zhì)。 我們首先證明（2）和（3）。 當(dāng)i=1時(shí)，若n≥3，則根的左、右孩子的編號(hào)分別是2，3；若n<3，則根沒有右孩子；若n<2，則根將沒有左、右孩子；以上對(duì)于（2）和（3）均成立。 假設(shè)：對(duì)于所有的1≤j≤i 結(jié)論成立。即：結(jié)點(diǎn)j的左孩子編號(hào)為2j；右孩子編號(hào)

40、為2j+1。,2i +2,2i 2i+1 2i+2 2i+3 i+1 2i 2i+1,i,i i+1,由完全二叉樹的結(jié)構(gòu)可以看出：結(jié)點(diǎn)i+1或者與結(jié)點(diǎn)i同層且緊鄰i結(jié)點(diǎn)的右側(cè)，或者i位于某層的最右端，i+1位于下一層的最左端。 可以看出，i+1的左、右孩子緊鄰在結(jié)點(diǎn)i的孩子后面，由于結(jié)

41、點(diǎn)i 的左、右孩子編號(hào)分別為2i和2i+1，所以，結(jié)點(diǎn)i+1的左、右孩子編號(hào)分別為2i+2和2i+3，經(jīng)提取公因式可以得到：2(i+1)和2(i+1)+1，即結(jié)點(diǎn)i+1的左孩子編號(hào)為2(i+1)；右孩子編號(hào)為2(i+1)+1。 又因?yàn)槎鏄溆蒼個(gè)結(jié)點(diǎn)組成，所以，當(dāng)2(i+1)+1>n，且2(i+1)=n時(shí)，結(jié)點(diǎn)i+1只有左孩子，而沒有右孩子；當(dāng)2(i+1)>n，結(jié)點(diǎn)i+1既沒有左孩子也沒有右孩子。,以

42、上證明得到（2）和（3）成立。 下面利用上面的結(jié)論證明（1）。 對(duì)于任意一個(gè)結(jié)點(diǎn)i，若2i≤n，則左孩子的編號(hào)為2i，反過來(lái)結(jié)點(diǎn)2i的雙親就是i，而 ?2i/2?=i；若2i+1≤n，則右孩子的編號(hào)為2i+1，反過來(lái)結(jié)點(diǎn)2i+1的雙親就是i，而 ?(2i+1)/2? =i，由此可以得出（1）成立。,6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹也可以采用兩種存儲(chǔ)方式：順序存

43、儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1. 順序存儲(chǔ)結(jié)構(gòu) 這種存儲(chǔ)結(jié)構(gòu)適用于完全二叉樹。其存儲(chǔ)形式為：用一組連續(xù)的存儲(chǔ)單元按照完全二叉樹的每個(gè)結(jié)點(diǎn)編號(hào)的順序存放結(jié)點(diǎn)內(nèi)容。下面是一棵二叉樹及其相應(yīng)的存儲(chǔ)結(jié)構(gòu)。,8,4 5 6 7,2 3,1,,,,,,,,,3．2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在順序存儲(chǔ)結(jié)構(gòu)中，利用編號(hào)表示元素的位置及

44、元素之間孩子或雙親的關(guān)系，因此對(duì)于非完全二叉樹，需要將空缺的位置用特定的符號(hào)填補(bǔ)，若空缺結(jié)點(diǎn)較多，勢(shì)必造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 常見的二叉樹結(jié)點(diǎn)結(jié)構(gòu)如下所示：,其中，lchild和rchild是分別指向該結(jié)點(diǎn)左孩子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。在C語(yǔ)言中的類型定義為： typedef struct BiTNode{

45、 TElemType data; struct BiTNode *lchild,*rchlid; }BiTNode,*BiTree;,G H,D E F,B C,A,,,,,,,,,^ G ^ ^ H ^,^

46、 D ^ E ^ F ^,B ^ C,A,BT,,,,,,,,,一棵二叉樹及相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),這種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是尋找孩子結(jié)點(diǎn)容易，雙親比較困難。因此，若需要頻繁地尋找雙親，可以給每個(gè)結(jié)點(diǎn)添加一個(gè)指向雙親結(jié)點(diǎn)的指針域，其結(jié)點(diǎn)結(jié)構(gòu)如下所示。,,注：在具體的應(yīng)用中采用什么存儲(chǔ)結(jié)構(gòu)，除根據(jù)二叉樹的形態(tài)之外還應(yīng)考慮需進(jìn)行何種操作。,5. 在下述結(jié)論中，正確的是（ ）①

47、只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0; ②二叉樹的度為2； ③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。 A．①②③ B．②③④ C．②④ D．①④8．若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A．9 B．11 C．15 D．不確定 9．在一棵三叉樹中度

48、為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（ ）個(gè)A．4 B．5 C．6 D．7,D,B,C,11．具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（ ）個(gè)度為2的結(jié)點(diǎn)，A．8 B．9 C．10 D．ll12．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）A． 2

49、50 B． 500 C．254 D．505 E．以上答案都不對(duì) 16. 有關(guān)二叉樹下列說(shuō)法正確的是（ ）A．二叉樹的度為2 B．一棵二叉樹的度可以小于2 C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為217．二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（ ）A．2I B． 2I-1-1

50、C． 2 I-1 D．2I -1,B,E,B,C,18. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ）A．11 B．10 C．11至1025之間 D．10至1024之間19．一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有( )結(jié)點(diǎn)A．2h B．2h-1 C．2h+1 D．h+1 20．對(duì)于有

51、n 個(gè)結(jié)點(diǎn)的二叉樹, 其高度為（ ）A．nlog2n B．log2n C．?log2n?+1 D．不確定21. 一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（ ）A．?log2n?+1 B．log2n+1 C．?log2n? D．log2n-122．深度為h的滿m叉樹的第k層有（ ）個(gè)結(jié)點(diǎn)。(1=<k=<h) A．mk-1 B．mk-1 C

52、．mh-1 D．mh-1,C,B,D,A,A,23．在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ ）A．2k-1 B．2k C．2k-1 D．?log2k?+124．高度為 K的二叉樹最大的結(jié)點(diǎn)數(shù)為（ ）。A．2k B．2k-1 C．2k -1 D．2k-1-125. 一棵樹高為K的完全二叉樹至少有（ ）個(gè)結(jié)點(diǎn)

53、A．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k26. 將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度（ ）A．4 B．5 C．6 D．7,C,C,C,C,二、填空題1．二叉樹由_(1)__，__(2)_，_(3)__三個(gè)基本單元組成。,6．具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為__

54、____。,7．已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹有______個(gè)葉子結(jié)點(diǎn)。8．深度為k的完全二叉樹至少有___(1)____個(gè)結(jié)點(diǎn)，至多有___(2)____個(gè)結(jié)點(diǎn)。9．深度為H 的完全二叉樹至少有_(1)__個(gè)結(jié)點(diǎn)；至多有_(2)__個(gè)結(jié)點(diǎn)；H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是 (3)__。10．在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是______。11．在完全二叉樹

55、中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是______。,12．一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有__(1)_個(gè)度為1的結(jié)點(diǎn)、有__(2)_個(gè)分支 （非 終端）結(jié)點(diǎn)和__(3)_個(gè)葉子，該滿二叉樹的深度為_(4)__。13．假設(shè)根結(jié)點(diǎn)的層數(shù)為１，具有ｎ個(gè)結(jié)點(diǎn)的二叉樹的最大高度是______。14．在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有N0 =______15．設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為0，則高度為k的

56、二叉樹的最大結(jié)點(diǎn)數(shù)為______,最小結(jié)點(diǎn)數(shù)為______。,17．高度為K的完全二叉樹至少有______個(gè)葉子結(jié)點(diǎn)。 19．已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是______。 20．一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹的高度為______。,參考答案,1.(1)根結(jié)點(diǎn)(2)左子樹(3)右子樹 ；6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1

57、)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用順序存儲(chǔ)二叉樹時(shí)，要按完全二叉樹的形式存儲(chǔ)，非完全二叉樹存儲(chǔ)時(shí)，要加“虛結(jié)點(diǎn)”。設(shè)編號(hào)為i和j的結(jié)點(diǎn)在順序存儲(chǔ)中的下標(biāo)為s 和t ,則結(jié)點(diǎn)i和j在同一層上的條件是?log2s?=?log2t?。11. ?log2i?=?log2j? 12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n? +1 13.n 14