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

1、第六章樹(shù)及二叉樹(shù)一、下面是有關(guān)二叉樹(shù)的表達(dá)，請(qǐng)判斷正誤(V) 1.假設(shè)二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，那么在 n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有n 1個(gè)非空 指針域。(X) 2.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于1。(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ù)(假設(shè)存在的話)所有結(jié)點(diǎn)的關(guān)鍵字 值，且小于其右非空子樹(shù)(假設(shè)存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹(shù)的特點(diǎn))(X) 6.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹(shù)的深度。(應(yīng)2i-1 )(X) 7.二叉樹(shù)中所有結(jié)點(diǎn)，如

2、果不存在非空左子樹(shù)，那么不存在非空右子樹(shù)。(X) 8.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，那么它的第i層上最多能有2i 1個(gè)結(jié) 點(diǎn)。(應(yīng) 2i-1 )(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è)雙親，所以只有 n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn) 的指針，還有n+1個(gè)空指針。)即有后繼鏈接的指針僅n-1個(gè)。(V) 10.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)=n/2 = 6,再

3、求n2=no-仁5()11、哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，所以必為滿二叉樹(shù)。()12、在哈夫曼樹(shù)中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。()13、線索二叉樹(shù)是一種邏輯結(jié)構(gòu)。(V ) 14、深度為K的完全二叉樹(shù)至少有2k-1個(gè)結(jié)點(diǎn)。(V )15、具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，其葉結(jié)點(diǎn)的個(gè)數(shù)為(n+1) /2。(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= n。-1=31 個(gè)分支結(jié)點(diǎn)和_26-1 =32個(gè)葉子。注：滿二叉樹(shù)

4、沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。3. 一棵具有2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為 _9。(注：用 log 2(n) +1= 8.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-1=499。另外，最后一結(jié)點(diǎn)為2i屬于左葉子， 右葉子是空的，所以有1個(gè)非空左子樹(shù)。完全二叉樹(shù)的特點(diǎn)決定不可

5、能有左空右不空的情況， 所以非空右子樹(shù)數(shù)二0.6. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，可能到達(dá)的最大深度為n_，最小深度為_(kāi)2_。答：當(dāng)k=1單叉樹(shù)時(shí)應(yīng)該最深，深度=n 層；當(dāng)k=n-1 n-1叉樹(shù)時(shí)應(yīng)該最淺，深度=2層，但不包括n=0或1時(shí)的特例情況。教材答案是“完全 k叉樹(shù)，未定量。7. 二叉樹(shù)的根本組成局部是：根N、左子樹(shù)L和右子樹(shù)R。因而二叉樹(shù)的遍歷次序 有六種。最常用的是三種：前序法即按 N L R次序，后序法即按 L R N 次序 和中序法也稱對(duì)稱序法，即按 LN R次序。這三種方法相互之間有關(guān)聯(lián)。假設(shè)一棵二叉 樹(shù)的前序序列是BEFCGDH中序序列是FEBGCHD那么它的后序序列必是F E

6、 G H D C B。解：法1:先由條件畫圖，再后序遍歷得到結(jié)果；法2:不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹(shù)。例如，前序遍歷BEFCGD中，根結(jié)點(diǎn)在最前面，是 B;那么后序遍歷中B 一定在最后面。法3:遞歸計(jì)算。如B在前序序列中第一，中序中在中間可知左右子樹(shù)上有哪些元素 那么在后序中必為最后。如法對(duì) B的左右子樹(shù)同樣處理，那么問(wèn)題得解。8. 中序遍歷的遞歸算法平均空間復(fù)雜度為 0n _。答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹(shù)的深度k+1,包括葉子的空域也遞歸了一次。9. 用5個(gè)權(quán)值3, 2, 4, 5, 1 構(gòu)造的哈夫曼Hu

7、ffman樹(shù)的帶權(quán)路徑長(zhǎng)度是 33 _。 解：先構(gòu)造哈夫曼樹(shù)，得到各葉子的路徑長(zhǎng)度之后便可求出WP4+ 5+ 3X 2+ 1+ 2X 3=33(15).(9)-.453'1 2注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一注：原題為選擇題：A. 32B. 33C. 34D. 15)注：合并值應(yīng)排在葉子值之后10、 N個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存放，共有空鏈域個(gè)數(shù)為n+111、深度為6 根層次為1、的二叉樹(shù)至多有26 - 1 個(gè)結(jié)點(diǎn)。12、一棵完全二叉樹(shù)的第5層有3個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)數(shù)是_9_ 三、單項(xiàng)選擇題C 1.不含任何結(jié)點(diǎn)的空樹(shù)。A是一棵樹(shù)；B是一棵二叉樹(shù)；C是一棵樹(shù)也是

8、一棵二叉樹(shù)；D既不是樹(shù)也不是二叉樹(shù)答：以前的標(biāo)答是B,因?yàn)槟菚r(shí)樹(shù)的定義是n?1(C ) 2.二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。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)log 2(n)( B ) log2(n)(C)log2(n)+1( D) log2(n)+1注1: x表示不小于x的最小整數(shù)；x表示不大于x的最大整數(shù)，它們與含義不同! 注2:選(A)是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)幕時(shí)就會(huì)少算一層。似乎log 2(n) +1是對(duì)的

9、?(A ) 4.把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是。(A)唯一的(B)有多種(C)有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子(D)有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子5.從供選擇的答案中，選出應(yīng)填入下面表達(dá)？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。樹(shù)是結(jié)點(diǎn)的有限集合，它A_根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m( m> 0)個(gè)B 的集合T1, T2，-點(diǎn)(1 < i < m。供選擇的答案A:，Tm每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn) T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié) 一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 CB:有0個(gè)或互不相交權(quán)有0個(gè)或多個(gè)允許相交維數(shù)C:答案：AB91，1，6. 從供選擇的答案中

10、，選出應(yīng)填入下面表達(dá)卷的對(duì)應(yīng)欄內(nèi)。二叉樹(shù)£。在完全的二叉樹(shù)中，假設(shè)一個(gè)結(jié)點(diǎn)沒(méi)有有且只有1個(gè) 允許葉結(jié)點(diǎn)相交次數(shù)(或度)有1個(gè)或1個(gè)以上允許樹(shù)枝結(jié)點(diǎn)相交序?內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里，一個(gè)結(jié)點(diǎn)樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的供選擇的答案A:是特殊的樹(shù)的樹(shù)形結(jié)構(gòu)B：左子結(jié)點(diǎn)C，而N的右子女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的B，那么它必定是葉結(jié)點(diǎn)。每棵樹(shù)都能N的左子女是N在原D 。不是樹(shù)的特殊形式是兩棵樹(shù)的總稱有是只有二個(gè)根結(jié)點(diǎn)CD:最左子結(jié)點(diǎn)最左的兄弟答案：A= B=右子結(jié)點(diǎn)左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)最右子結(jié)點(diǎn) 最鄰近的右兄弟最右的兄弟C= D兄弟最鄰近的左兄弟

11、7、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1,那么編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為(A)A、98B 、99C 、50D 、48 答案：ABCDE2，1，1，3M1 M2和M3與森林F&設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是(D)A) M1 B ) M1+M2 C ) M3 D ) 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)為(C)A、48B、49C、50 D 5110、某二叉

12、樹(shù)結(jié)點(diǎn)的中序序列為A、B、CDE、F、G后序序列為B、DC、A、F、G E，那么其左子樹(shù)中結(jié)點(diǎn)數(shù)目為(C)A) 3B ) 2C ) 4D) 5四、簡(jiǎn)答題(每題4分，共20分)1. 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？答：度為2的樹(shù)從形式上看與二叉樹(shù)很相似，但它的子樹(shù)是無(wú)序的，而二叉樹(shù)是有序的。即， 在一般樹(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 nodechar data;struct node *lchild, rchild;(

13、lchild,data,rchild )。其中 Ichild ，rchild 分別為指向 左右孩子的指針，data為字符型，root為根指針，試答復(fù) 以下問(wèn)題：1. 對(duì)以下二叉樹(shù)B,執(zhí)行以下算法traversal(root) ，試指C算法如下：void traversal(struct node *root) if (root)printf(“ c -,>doa);traversal(root->lchild); prin tf ( “ c , rood ata); traversal(root->rchild);出其輸出結(jié)果；2. 假定二叉樹(shù)B共有n個(gè)結(jié)點(diǎn)，試分析算法tra

14、versal(root)CF G的時(shí)間復(fù)雜度。(共8分)二叉樹(shù)BE解：這是“先根再左再根再右，比前序遍歷多打印各結(jié)點(diǎn)一次，輸出結(jié)果為：A B C C E E B A D F F D G G特點(diǎn)：每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次；但出現(xiàn)的順序不同，其規(guī)律是：但凡有左子樹(shù)的結(jié)點(diǎn)，必間隔左子樹(shù)的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；女口A, B, D等結(jié)點(diǎn)。反之馬上就會(huì)重復(fù)出現(xiàn)。如C, E，F(xiàn)，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

15、 , F,試畫出二叉樹(shù)B,并簡(jiǎn)述由任意二叉樹(shù) B的前序遍歷序列和中序遍歷序列求二叉樹(shù) B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素 集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定 root的左右孩子。將他們分別作為新的root，不斷遞歸，那么所有元素都將被唯一確定，問(wèn)題得解B H I4. 給定如下圖二叉樹(shù)T,請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹(shù) 解：要遵循中序遍歷的軌跡來(lái)畫出每個(gè)前驅(qū)和后繼。中序遍歷序列：55 40 25 60 282808 33 5425 3340 600854334 60 68 0354 545555、一棵二叉

16、樹(shù)，其中序序列 DBCAFGE后序序列DCBGFEA構(gòu)造該二叉樹(shù) 解：i6、葉子結(jié)點(diǎn)值2, 3, 5, 6, 造哈夫曼樹(shù)，計(jì)算其帶權(quán)路徑長(zhǎng)度 解：9, 11,7、給定權(quán)值8 , 12, 4, 5, 26, 16,構(gòu)造一棵帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)，9,并計(jì)算其帶權(quán)路徑長(zhǎng)度解：WPL=8 X 3+4 X 4+5 X 4+16 X 2+9 X 3+12 X 3+26 X 2=207注:哈夫曼樹(shù)的左右子樹(shù)可以互換。8. P60 4-26 試寫出如下圖的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答：DLR A B D F J G K C E H I L MLDR: B F J D G K A C

17、 H E L I MLRD J F K G D B H L M I E C A答：注意全部兄弟之間都要連線包括度為 2的兄弟，并注意原有連線結(jié)點(diǎn)一律歸入 左子樹(shù)，新添連線結(jié)點(diǎn)一律歸入右子樹(shù)。把如下圖的樹(shù)轉(zhuǎn)化成二叉樹(shù)。A B>、C z K. F-HDLG丿、M J 10畫出和以下二叉樹(shù)相應(yīng)的森林。答：注意根右邊的子樹(shù)肯定是森林, 而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。(100)(4°)-(60)192132 '-(28) (17)-( 11)»*"""""710 6-(5)2 31"字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111

18、00 10.072000.193111100.02411100.06510 10.326111110.037010.21k11010.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.06 51000.3261010.0371100.2181110.106.11、假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19 ,0.02 , 0.06 , 0.32 , 0.03 , 0.21 , 0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比擬兩種方案的優(yōu)缺點(diǎn) 解：方案1;哈夫曼編碼

19、先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)那么:方案比擬:方案1的WP2(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 的 WP3(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 .編寫遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。 解：思路：輸出葉子結(jié)點(diǎn)比擬簡(jiǎn)單，用任何一種遍歷遞歸算法，但凡左右指針均空者，那么為 葉子，將其打印出來(lái)。法一：核心局部為：DLR(liu

20、yu *root) /* 中序遍歷 遞歸函數(shù)*/if(root!=NULL) if(root->lchild=NULL)&&(root->rchild=NULL)sum+;printf("%dn",root->data);DLR(root->lchild);DLR(root->rchild); return(0);法二：int LeafCount_BiTree(Bitree T)/ 求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目if(!T) return 0; /空樹(shù)沒(méi)有葉子else if(!T->lchild&&!T->

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

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

23、樹(shù)中以值為 x 的結(jié)點(diǎn)為根的子樹(shù)深度 if(T->data=x) printf("%dn",Get_Depth(T); /找到了值為 x 的結(jié)點(diǎn) , 求其深度exit 1; else if(T->lchild) Get_Sub_Depth(T->lchild,x);if(T->rchild) Get_Sub_Depth(T->rchild,x); / 在左右子樹(shù)中繼續(xù)尋找 /Get_Sub_Depth4. 編寫按層次順序同一層自左至右遍歷二叉樹(shù)的算法。 解：思路：既然要求從上到下，從左到右，那么利用隊(duì)列存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好方法。 這是一個(gè)

24、循環(huán)算法，用 while 語(yǔ)句不斷循環(huán)，直到隊(duì)空之后自然退出該函數(shù)。技巧之處：當(dāng)根結(jié)點(diǎn)入隊(duì)后，會(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+1)%max; qr=T; /* while(f!=r) /*假設(shè)max*/置空隊(duì) */根結(jié)點(diǎn)進(jìn)隊(duì) */隊(duì)列不空 */f=(f+1%max);p=qf; /*出隊(duì) */printf("%d",p->data); /* 打印根結(jié)點(diǎn) */if(p-&g

25、t;lchild)r=(r+1)%max; qr=p->lchild;/*假設(shè)左子樹(shù)不空，那么左子樹(shù)進(jìn)隊(duì) */if(p->rchild)r=(r+1)%max; qr=p->rchild;/*假設(shè)右子樹(shù)不空，那么右子樹(shù)進(jìn)隊(duì) */return(0);法二：void LayerOrder(Bitree T)/ 層序遍歷二叉樹(shù)InitQueue(Q); / 建立工作隊(duì)列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p->lchild) EnQueue(Q,p->lchild);if(p->rch

26、ild) EnQueue(Q,p->rchild);/LayerOrder5. 編寫算法判別給定二叉樹(shù)是否為完全二叉樹(shù)。答：int lsFull_Bitree(Bitree T)判斷二叉樹(shù)是否完全二叉樹(shù),是那么返回1,否那么返回0 InitQueue(Q);flag=0;EnQueue(Q,T); / 建立工作隊(duì)列while(!QueueEmpty(Q) DeQueue(Q,p);if(!p) flag=1;else if(flag) return 0;else EnQueue(Q,p->lchild);EnQueue(Q,p->rchild); /不管孩子是否為空 , 都入

27、隊(duì)列 /whilereturn 1;/lsFull_Bitree分析：該問(wèn)題可以通過(guò)層序遍歷的方法來(lái)解決與6.47相比，作了一個(gè)修改，不管當(dāng)前結(jié)點(diǎn) 是否有左右孩子，都入隊(duì)列.這樣當(dāng)樹(shù)為完全二叉樹(shù)時(shí)，遍歷時(shí)得到是一個(gè)連續(xù)的不包含空 指針的序列.反之，那么序列中會(huì)含有空指針6、閱讀以下算法，假設(shè)有錯(cuò)，改正之。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->rchild; / 應(yīng) 改 為 whi

28、le(!r->Ltag) r=r->Lchild;return r;應(yīng)改為 return r->rchild ;答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)誤。注：當(dāng)rtag= 1時(shí)說(shuō)明內(nèi)裝后繼指針，可直接返回，第一句無(wú)錯(cuò)。當(dāng)rtag= 0時(shí)說(shuō)明內(nèi)裝右孩子指針，但孩 子未必是后繼，需要計(jì)算。中序遍歷應(yīng)當(dāng) 先左再根再右，所以應(yīng)當(dāng)找左子樹(shù)直到葉子處。r=r->lchild; 直到 LTag=1 ;應(yīng)改為:while(!r-> Ltag)r=r-> Lchild;7、閱讀下面程序，并答復(fù)有關(guān)問(wèn)題。其中BSTree為用二叉鏈表表示的二叉排序樹(shù)類型。(1) 簡(jiǎn)要說(shuō)明程序功能。

29、(5分)(2) n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)的深度h是多少？( 3分)(3) 假設(shè)二叉排序樹(shù)*bst是有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，給出算法的時(shí)間復(fù)雜度。(2分)int Proc (BSTree *bst, KeyType K) BSTree f, q, s;s=(BSTree)malloc(sizeof(BSTNode);s-> key = K; s-> lchild = NULL; s-> rchild = NULL;if ( *bst = NULL ) *bst = s; return 1; f = NULL; q = *bst;while( q != NULL ) if ( K <