數(shù)據(jù)結(jié)構(gòu)第6章二叉樹(shù)作業(yè)及答案匯總

1、第六章樹(shù)及二叉樹(shù)一、下面是有關(guān)二叉樹(shù)的敘述，請(qǐng)判斷正誤(V)1.若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有n1個(gè)非空指針域。(X)2.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于lo(V)3.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。(X)4.二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。(X)5.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹(shù)(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹(shù)的特點(diǎn))(X)6.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是2»1,其中k是樹(shù)的深度。(應(yīng)2T)(X)7.二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，則不存在非空

2、右子樹(shù)。(X)8.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2：1個(gè)結(jié)點(diǎn)。(應(yīng)2c)(V)9.用二叉鏈表法(link-rlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。(正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹(shù)中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有nT個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針。)即有后繼鏈接的指針僅n-l個(gè)。(V)10,具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)=n/2=6,再求n2=n。-仁5()11、哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，所以必為滿

3、二叉樹(shù)。()12、在哈夫曼樹(shù)中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。()13、線索二叉樹(shù)是一種邏輯結(jié)構(gòu)。(V)14、深度為K的完全二叉樹(shù)至少有2m個(gè)結(jié)點(diǎn)。")15、具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，其葉結(jié)點(diǎn)的個(gè)數(shù)為(n+1)/2o(V)16.前序和中序遍歷用線索樹(shù)方式存儲(chǔ)的二叉樹(shù)，不必使用棧。(X)17、哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的點(diǎn)離根較遠(yuǎn)。二、填空1 .由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有一5一種形態(tài)。2 .一棵深度為6的滿二叉樹(shù)有+化=0+n2=no-1-31一個(gè)分支結(jié)點(diǎn)和_2仆二32一個(gè)葉子。注：滿二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。3 .一棵具有257個(gè)結(jié)點(diǎn)的完全

4、二叉樹(shù)，它的深度為一9。(注：用log2(n)+1=iL8.xx+仁94 .設(shè)一棵完全二叉樹(shù)有700個(gè)結(jié)點(diǎn)，則共有_350個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)二n/2=3505 .設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有_50L個(gè)葉子結(jié)點(diǎn)，有_499一個(gè)度為2的結(jié)點(diǎn)，有一1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有一0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。答：最快方法：用葉子數(shù)二n/2=500,n2=no-l=499o另外,最后一結(jié)點(diǎn)為2i屬于左葉子,右葉子是空的，所以有1個(gè)非空左子樹(shù)。完全二叉樹(shù)的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹(shù)數(shù)二0.6 .一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，可能達(dá)到的最大深度為一n_,最小

5、深度為答：當(dāng)k=1（單叉樹(shù)）時(shí)應(yīng)該最深，深度二n（層）；當(dāng)k=nT（n-1叉樹(shù)）時(shí)應(yīng)該最淺，深度二2（層），但不包括n=0或1時(shí)的特例情況。教材答案是“完全k叉樹(shù)"，未定量。）7 .二叉樹(shù)的基本組成部分是：根（N）、左子樹(shù)（L）和右子樹(shù)（R）。因而二叉樹(shù)的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按LAN次序）和中序法（也稱對(duì)稱序法，即按LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹(shù)的前序序列是BEFCGDH中序序，列是FEBGCHD則它的后序序列必是FEGHDCBo解：法1：先由已知條件畫(huà)圖，再后序遍歷得到結(jié)果；法2：不畫(huà)圖也能快速得出后序序列，

6、只要找到根的位置特征。由前序先確定root,由中序先確定左子樹(shù)。例如，前序遍歷BEFCGD中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計(jì)算。如B在前序序列中第一，中序中在中間（可知左右子樹(shù)上有哪些元素）則在后序中必為最后。如法對(duì)B的左右子樹(shù)同樣處理，則問(wèn)題得解。8 .中序遍歷的遞歸算法平均空間復(fù)雜度為一0（n）_o答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹(shù)的深度k+1,包括葉子的空域也遞歸了一次。9,用5個(gè)權(quán)值3,2,4,5,1）構(gòu)造的哈夫曼（Huffman）樹(shù)的帶權(quán)路徑長(zhǎng)度是一33解：先構(gòu)造哈夫曼樹(shù)，得到各葉子的路徑長(zhǎng)度之后便可求出WPJ（4+5+3）X2+（

7、1+2）X3=33（15）/（9）妙、注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一）453，（3）（注：合并值應(yīng)排在葉子值之后）12（注：原題為選擇題：A,32B.33C.34D.15）10 .N個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存放，共有空鏈域個(gè)數(shù)為n+111 .深度為6（根層次為1、的二叉樹(shù)至多有匚J,個(gè)結(jié)點(diǎn)。12 .已知一棵完全二叉樹(shù)的第5層有3個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)數(shù)是_9o三、單項(xiàng)選擇題（c）1.不含任何結(jié)點(diǎn)的空樹(shù)（A）是一棵樹(shù)；（C）是一棵樹(shù)也是一棵二叉樹(shù)；（B）是一棵二叉樹(shù)；（D）既不是樹(shù)也不是二叉樹(shù)答：以前的標(biāo)答是B,因?yàn)槟菚r(shí)樹(shù)的定義是n111(C)2,二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，

8、所以。A、它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；E、它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)；C、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；D、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用(C)3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。(A)log2(n)(B)log2(n)(C)ILlog2(n)+1(D)log2(n)+l注1：x表示不小于x的最小整數(shù)；x表示不大于x的最大整數(shù)，它們與口含義不同！注2：選(A)是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)幕時(shí)就會(huì)少算一層。似乎log2(n)+1是對(duì)的？(A)4.把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是o(A)唯一的有多種有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子(D)有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子5

9、.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。樹(shù)是結(jié)點(diǎn)的有限集合，它A_根結(jié)點(diǎn)，記為T(mén)。其余的結(jié)點(diǎn)分成為m(m>0)個(gè)區(qū)的集合T1,T2,-，Tm每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為T(mén)i的父結(jié)點(diǎn)，Ti稱為T(mén)的子結(jié)一個(gè)點(diǎn)(1<i<mo結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的C供選擇的答案A：有0個(gè)或B：互不相交C：權(quán) 答案：AB91, 1,有0個(gè)或多個(gè)允許相交維數(shù)有且只有1個(gè) 允許葉結(jié)點(diǎn)相交次數(shù)(或度)有1個(gè)或1個(gè)以上允許樹(shù)枝結(jié)點(diǎn)相交序6.從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。二叉樹(shù)瓢 在完全的二叉樹(shù)中，若

10、一個(gè)結(jié)點(diǎn)沒(méi)有B-,則它必定是葉結(jié)點(diǎn)。每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里，一個(gè)結(jié)點(diǎn)N的左子女是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的C，而N的右子女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的供選擇的答案A：是特殊的樹(shù)不是樹(shù)的特殊形式是兩棵樹(shù)的總稱有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)D 小七土占CD：最左子結(jié)點(diǎn)最左的兄弟答案：A二B二右子結(jié)點(diǎn)左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)最右子結(jié)點(diǎn)最鄰近的右兄弟最右的兄弟兄弟最鄰近的左兄弟7、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為L(zhǎng)則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為(A)A>98B>99C>50D、48答案：ABCD

11、E2,1,1,3&設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為MlM2和M3與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是(D)A)MlB)M1+M2C)M3D)M2+M39、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1,則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為(0A、48B、49C、50D5110、某二叉樹(shù)結(jié)點(diǎn)的中序序列為A、B、CDE、F、G后序序列為B、DC、A、F、GE,則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為(C)A)3B)2C)4D)5四、簡(jiǎn)答題(每小題4分，共20分)1. 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？答：度為2的樹(shù)從形式上看與二

12、叉樹(shù)很相似，但它的子樹(shù)是無(wú)序的，而二叉樹(shù)是有序的。即，在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而在二叉樹(shù)中即使是一個(gè)孩子也有左右之分。2.設(shè)如下圖所示的二叉樹(shù)B的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，root為根指針，結(jié)點(diǎn)結(jié)構(gòu)為：c的結(jié)點(diǎn)類型定義如下：struct node(char data;struct node * Ichild, rchild;);C算法如下：void traversal(struct node *root) if(root)printf (" %c” >doa);traversal(root->lchild); printf( "%c&qu

13、ot; ->data);traversal(root->rchild);)(ichild,data,rchild)o其中Ichild9rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問(wèn)題：1 .對(duì)下列二叉樹(shù)B,執(zhí)行下列算法traversal(root),試指出其輸出結(jié)果；2 .假定二叉樹(shù)B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)CF G的時(shí)間復(fù)雜度。(共8分)二叉樹(shù)BE解：這是“先根再左再根再右”，比前序遍歷多打印各結(jié)點(diǎn)一次，輸出結(jié)果為：ABCCEEBADFFDGG特點(diǎn)：每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次；但出現(xiàn)的順序不同，其規(guī)律是：凡是有

14、左子樹(shù)的結(jié)點(diǎn)，必間隔左子樹(shù)的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；女口A,B,D等結(jié)點(diǎn)。反之馬上就會(huì)重復(fù)出現(xiàn)。如C,E,F,G等結(jié)點(diǎn)。時(shí)間復(fù)雜度以訪問(wèn)結(jié)點(diǎn)的次數(shù)為主，精確值為2*n,時(shí)間漸近度為0(n).3 .給定二叉樹(shù)的兩種遍歷序列，分別是：前序遍歷序列：D,A,C,E,B,H,F,G,I；中序遍歷序列：D,C,B,E,H,A,G,I,F,試畫(huà)出二叉樹(shù)B,并簡(jiǎn)述由任意二叉樹(shù)B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法。解：方法是：由前序先確定root,由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的兀素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的r

15、oot,不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解4 .給定如圖所示二叉樹(shù)T,請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù)解:要遵循中序遍歷的軌跡來(lái)畫(huà)出每個(gè)前驅(qū)和后繼。中序遍歷序列：554025602808335446060545455G9, 11,構(gòu)造哈夫曼5、已知一棵二叉樹(shù)，其中序序列DBCAFGE后序序列DCBGFEA構(gòu)造該二叉樹(shù)6、已知葉子結(jié)點(diǎn)值2,3,5,6,樹(shù)，計(jì)算其帶權(quán)路徑長(zhǎng)度。7、給定權(quán)值8,12,4,5,26,構(gòu)造一棵帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度解：80WPL=8X3+4X4+5X4+16X2+9X3+12X3+26X2=207DLRABDFJGKCEHILMLDR:

16、BFJDGKACHELIMLRDJFKGDBHLMIECA（把如圖所示的樹(shù)轉(zhuǎn)化成二叉 樹(shù)。注:哈夫曼樹(shù)的左右子樹(shù)可以互換。8.答：(P604-26)試寫(xiě)出如圖所示的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答：注意全部兄弟之間都要連線(包括度為2的兄弟)，并注意原有連線結(jié)點(diǎn)一律歸入左子樹(shù)，新添連線結(jié)點(diǎn)一律歸入右子樹(shù)。A”Bf、c/、K、F只/DLGJ、MJ10畫(huà)出和下列二叉樹(shù)相應(yīng)的森林。15答：注意根右邊的子樹(shù)肯定是森林，而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。6.11、假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.

17、21,0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w=7, 19, 2, 6, 32,3,21, 10,按哈夫曼規(guī)則:(100)”(4。)-(60)192132 '-(28) (17)-( 11)710 6-(5)2 3方案比較:字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率11100 10. 0710000. 072000. 1920010. 193111100. 0230100. 02411100. 0640110.06 "510 1

18、0. 32L 01000. 326111110. 0361010. 037010.2171100.21(811010. 1081110. 10方案1的WPJ2 (0. 19+0. 32+0. 21) +4 (0. 07+0. 06+0. 10)+5 (0. 02+0. 03) =1. 44+0. 92+0. 25=2. 61方案2的WPj3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼六、算法設(shè)計(jì)題1 .編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。解：思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷遞歸算法，凡是左右指針均空者，

19、則為葉子，將其打印出來(lái)。法一：核心部分為：DLR(liuyu*root)/*中序遍歷遞歸函數(shù)*/if(root!=NULL)if(root->lchild=NULL)&&(root->rchild=NULL)sum+;printf(%dn,root->data);DLR(root->lchiId);DLR(root->rchiId);return(0);)法二：intLeafCount_BiTree(BitreeT)/求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目(if(!T)return0;/空樹(shù)沒(méi)有葉子elseif(!T->lchild&&!T

20、->rchiId)return1;/葉子結(jié)點(diǎn)elsereturnLeaf_Count(T->lchiId)+Leaf_Count(T->rchiId);/左子樹(shù)的葉子數(shù)加上右子樹(shù)的葉子數(shù)/LeafCount_BiTree2 .寫(xiě)出求二叉樹(shù)深度的算法，先定義二叉樹(shù)的抽象數(shù)據(jù)類型。解：法一：intdepth(liuyu*root)/*統(tǒng)計(jì)層數(shù)*/intd,p;/*注意每一層的局部變量d,p都是各自獨(dú)立的*/P=0；if(root=NULL)return(p);/*找到葉子之后才開(kāi)始統(tǒng)計(jì)*/elsed=depth(root->lchild);if(d>p)p=d;/*向

21、上回朔時(shí)，要挑出左右子樹(shù)中的相對(duì)大的那個(gè)深度值*/d=depth(root->rchild);if(d>p)p=d;)P=p+1;return(p);)法二：intGet_Depth(BitreeT)/求子樹(shù)深度的遞歸算法(if(!T)return0;else(m=Get_Depth(T->lchiId);n=Get_Depth(T->rchiId);return(m>n?m:n)+1;/Get_Depth3、求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。解：intGet_Sub_Depth(BitreeT,intx)/求二叉樹(shù)中以值為x的結(jié)點(diǎn)為根的子樹(shù)深度if(

22、T->data=x)printf(，z%dnz，,Get_Depth(T);/找到了值為x的結(jié)點(diǎn),求其深度exit1;)elseif(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);/在左右子樹(shù)中繼續(xù)尋找/Get_Sub_Depth4 .編寫(xiě)按層次順序（同一層自左至右）遍歷二叉樹(shù)的算法。解：思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好辦法。這是一個(gè)循環(huán)算法，用while語(yǔ)句不斷循環(huán)，直到隊(duì)空之后自然退出該函數(shù)。技巧之處：當(dāng)根結(jié)點(diǎn)入隊(duì)后

23、，會(huì)自然使得左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又會(huì)立即使得它的左右孩子結(jié)點(diǎn)入隊(duì)，以此產(chǎn)生了按層次輸出的效果。level(liuyu*T)/* liuyu *T, *p, *q100;int f,r;f=0; r=0; /* r=(r+l)%max; qr=T; /* while(f!=r) /*f=(f+l%max);P=qf； /*假設(shè) max 已知*/置空隊(duì)*/根結(jié)點(diǎn)進(jìn)隊(duì)*/隊(duì)列不空*/出隊(duì)*/1printfC%d",p->data);/*打印根結(jié)點(diǎn)*/if(p->lchild)r=(r+l)%max;qr=p->lchild;/*若左子樹(shù)不空，則左子樹(shù)進(jìn)隊(duì)*/

24、if(p->rchild)r=(r+l)%max;qr=p->rchild;/*若右子樹(shù)不空，則右子樹(shù)進(jìn)隊(duì)*/)return(0);)法二：voidLayerOrder(BitreeT)/層序遍歷二叉樹(shù)(InitQueue(Q);/建立工作隊(duì)列EnQueue(Q,T);while(!QueueEmpty(Q)(DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);/LayerOrder5 .編寫(xiě)算法判別給定二叉樹(shù)是否為完全二叉樹(shù)。答：

25、intlsFull_Bitree(BitreeT)判斷二叉樹(shù)是否完全二叉樹(shù)，是則返回1,否則返回0InitQueue(Q);flag=0;EnQueue(Q,T);/建立工作隊(duì)列while(!QueueEmpty(Q)DeQueue(Q,p);if(!p)flag=l;elseif(flag)return0;elseEnQueue(Q,p->lchild);EnQueue(Q,p->rchild);/不管孩子是否為空,都入隊(duì)列/while1return1;/lsFull_Bitree分析：該問(wèn)題可以通過(guò)層序遍歷的方法來(lái)解決與6.47相比，作了一個(gè)修改，不管當(dāng)前結(jié)點(diǎn)是否有左右孩子，都

26、入隊(duì)列.這樣當(dāng)樹(shù)為完全二叉樹(shù)時(shí)，遍歷時(shí)得到是一個(gè)連續(xù)的不包含空指針的序列.反之，則序列中會(huì)含有空指針BiTree In Succ(BiTree q) 已知q是指向中序線索二叉樹(shù)上某個(gè)結(jié)點(diǎn)的指針，本函數(shù)返回指向*q的后繼的指針。r=q->rchild;/應(yīng)改為 r=q ；if (!r->rtag)while(!r->rtag)r=r->rchiId; / 應(yīng) 改 為 while(!r->Ltag) r=r->Lchild;return r; 應(yīng)改為 return r->rchild ；6、閱讀下列算法，若有錯(cuò)，改正之。答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)

27、誤。注：當(dāng)rtag=1時(shí)說(shuō)明內(nèi)裝后繼指針，可直接返回，第一句無(wú)錯(cuò)。當(dāng)rtag二。時(shí)說(shuō)明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計(jì)算。中序遍歷應(yīng)當(dāng)先左再根再右，所以應(yīng)當(dāng)找左子樹(shù)直到葉子處。r=r->lchild;直至ljLTag=l；應(yīng)改為：while(!l>Ltag)r=r->Lchild;7、閱讀下面程序，并回答有關(guān)問(wèn)題。其中BSTree為用二叉鏈表表示的二叉排序樹(shù)類型。(1)簡(jiǎn)要說(shuō)明程序功能。(5分)(2) n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)的深度h是多少？(3分)(3)假設(shè)二叉排序樹(shù)*bst是有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，給出算法的時(shí)間復(fù)雜度。(2分)intProc(BSTree*bst,KeyTypeK)BSTreef,q,s;s=(BSTree)malloc(sizeof(BSTNode);s->key=K;s->Ichild二NULL;s-&