[計算機軟件及應用]棧的應用和串圖

1、例1數(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 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 表達式求值大家考慮一下：4+2×3－10/5的求值運算過程兩個相繼出現(xiàn)的運算符

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

5、aluateExpression()//算術(shù)表達式求值的算符優(yōu)先算法，設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();}//不是運算符則進入 棧

6、,switch(Precede(GetTop(OPTR),c)){ case ‘<’: //棧頂元素的優(yōu)先級低,Push(OPTR, c); c=getchar(); break;,case ‘=’: //脫括號并接受下一個字符；,Pop(OPTR,x);c=getchar(); break;,case ‘>’: 退棧并將運算結(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. 對于棧操作數(shù)據(jù)的原則是（ ）。先進先出 B. 后進先出 C. 后進后出 D. 不

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

9、 j-i+1 D. 不確定的5. 若已知一個棧的入棧序列是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. 在作進棧運算時,應先判別棧是否( ① ),在作退棧運算時應先判別棧是否( ② )。當棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧

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

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

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

13、過程中允許出棧），下列得不到的出棧排列是( )。A．XYZ B. YZX C. ZXY D. ZYX13. 輸入序列為ABC，可以變?yōu)镃BA時，經(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. 若一個棧以向量V[1..n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是( )。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. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧( 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. 棧在（ ）中應用。遞歸調(diào)用

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

17、是說，如果出現(xià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ù)值,,因為next[3]=1，說明主串的第3個字符a（i=3）應該再與模式串的第1個字符a相比較，故出現(xiàn)了第二趟比較的情況；,因next[5]=2，說明

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

19、’,于是next[j+1]=k+1=next[j]+1,如果pk!=pj，則這又是一個模式匹配問題，其中主串和模式串相同,于是模式串應該向右滑動至pj與pnext[k]相對齊，繼續(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, 因為p3=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, 因為p5=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, 因為p7=p1, 因此next[8]=next[7]+1=2,上述定義的函數(shù)在某些情況下尚有缺陷，如,在出現(xiàn)這種情況的時候，即第一個字符與主串中的相應字符不匹配的時候，因為模式串前四個字符相同，主串中的字符不需要和第2，3，4個字符比較，所以可

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ù)語,2、 二叉樹,6.1 樹,6.1.1 樹的定義和基本運算1. 定義樹是一種常用的非線性結(jié)構(gòu)。我們可以這樣定義：樹是n（n≥0）個結(jié)點的有限集合

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

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

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

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

29、個數(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 二叉樹的定義和基本運算1

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

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

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

33、比值的等比數(shù)列，前n項之和的計算公式為：,其中 a1為第一項，an為第n項，q為比值?？梢缘玫剑摂?shù)列前K項之和為：,,,【性質(zhì)3】 對于任意一棵二叉樹BT，如果度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0=n2+1。,證明：假設度為1的結(jié)點個數(shù)為n1，結(jié)點總數(shù)為n，B為二叉樹中的分支數(shù)。,因為在二叉樹中，所有結(jié)點的度均小于或等于2，所以結(jié)點總數(shù)為：

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

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

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

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

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

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

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é)點i+1或者與結(jié)點i同層且緊鄰i結(jié)點的右側(cè)，或者i位于某層的最右端，i+1位于下一層的最左端。 可以看出，i+1的左、右孩子緊鄰在結(jié)點i的孩子后面，由于結(jié)

41、點i 的左、右孩子編號分別為2i和2i+1，所以，結(jié)點i+1的左、右孩子編號分別為2i+2和2i+3，經(jīng)提取公因式可以得到：2(i+1)和2(i+1)+1，即結(jié)點i+1的左孩子編號為2(i+1)；右孩子編號為2(i+1)+1。 又因為二叉樹由n個結(jié)點組成，所以，當2(i+1)+1>n，且2(i+1)=n時，結(jié)點i+1只有左孩子，而沒有右孩子；當2(i+1)>n，結(jié)點i+1既沒有左孩子也沒有右孩子。,以

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

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

44、元素之間孩子或雙親的關(guān)系，因此對于非完全二叉樹，需要將空缺的位置用特定的符號填補，若空缺結(jié)點較多，勢必造成空間利用率的下降。在這種情況下，就應該考慮使用鏈式存儲結(jié)構(gòu)。 常見的二叉樹結(jié)點結(jié)構(gòu)如下所示：,其中，lchild和rchild是分別指向該結(jié)點左孩子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。在C語言中的類型定義為： 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,,,,,,,,,一棵二叉樹及相應的鏈式存儲結(jié)構(gòu),這種存儲結(jié)構(gòu)的特點是尋找孩子結(jié)點容易，雙親比較困難。因此，若需要頻繁地尋找雙親，可以給每個結(jié)點添加一個指向雙親結(jié)點的指針域，其結(jié)點結(jié)構(gòu)如下所示。,,注：在具體的應用中采用什么存儲結(jié)構(gòu)，除根據(jù)二叉樹的形態(tài)之外還應考慮需進行何種操作。,5. 在下述結(jié)論中，正確的是（ ）①

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

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

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

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

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

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

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

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

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

56、二叉樹的最大結(jié)點數(shù)為______,最小結(jié)點數(shù)為______。,17．高度為K的完全二叉樹至少有______個葉子結(jié)點。 19．已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是______。 20．一個有2001個結(jié)點的完全二叉樹的高度為______。,參考答案,1.(1)根結(jié)點(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. 用順序存儲二叉樹時，要按完全二叉樹的形式存儲，非完全二叉樹存儲時，要加“虛結(jié)點”。設編號為i和j的結(jié)點在順序存儲中的下標為s 和t ,則結(jié)點i和j在同一層上的條件是?log2s?=?log2t?。11. ?log2i?=?log2j? 12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n? +1 13.n 14