1、第6章樹和二叉樹自測卷解答一、下面是有關二叉樹的敘述，請判斷正誤（每小題1分，共10分）（V）1.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n1個非空指針域。（x）2二叉樹中每個結點的兩棵子樹的高度差等于1。V ）3二叉樹中每個結點的兩棵子樹是有序的。（X）4.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。（X）5二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。（應2i-1）（X）6二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（X）7對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有21個結點。（應2i-1）（V）8用二叉鏈表法（link-

2、rlink）存儲包含n個結點的二叉樹，結點的2n個指針區域中有n+1個為空指針。（正確。用二叉鏈表存儲包含n個結點的二叉樹，結點共有2n個鏈域。由于二叉樹中，除根結點外，每一個結點有且僅有一個雙親，所以只有n-1個結點的鏈域存放指向非空子女結點的指針，還有n+1個空指針。）即有后繼鏈接的指針僅n-1個。V ）9具有12個結點的完全二叉樹有5個度為2的結點。最快方法：用葉子數=n/2=6,再求n2=n0-仁5二、填空（每空1分，共15分）1. 由3個結點所構成的二叉樹有_5_種形態。2. 一棵深度為6的滿二叉樹有1+n2=0+n2=no-仁31-個分支結點和_26-1=32_個葉子。注：滿二叉樹

3、沒有度為1的結點，所以分支結點數就是二度結點數。3. 一棵具有257個結點的完全二叉樹，它的深度為_9。（注：用|l_log2（n）+1=I.8.XX+1=9設一棵完全二叉樹有700個結點，則共有_350_個葉子結點。答：最快方法：用葉子數=n/2=3505設一棵完全二叉樹具有1000個結點，則此完全二叉樹有_500.個葉子結點，有499個度為2的結點，有_1_個結點只有非空左子樹，有_0個結點只有非空右子樹。答：最快方法：用葉子數=n/2=500,n2=no-1=499。另外，最后一結點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非

4、空右子樹數=0.6【嚴題集6.7】一棵含有n個結點的k叉樹，可能達到的最大深度為_n_，最小深度為_2_。答：當k=1（單叉樹）時應該最深，深度=n（層）；當k=n-1（n-1叉樹）時應該最淺，深度=2（層），但不包括n=0或1時的特例情況。7. 二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也稱對稱序法，即按LNR次序）。這三種方法相互之間有關聯。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是FEGHDCB。解：先由已知條件畫圖，再

5、后序遍歷得到結果;8. 中序遍歷的遞歸算法平均空間復雜度為_0(n)_。答：即遞歸最大嵌套層數，即棧的占用單元數。精確值應為樹的深度k+1,包括葉子的空域也遞歸了一次。9用5個權值3,2,4,5,1構造的哈夫曼(Huffman)樹的帶權路徑長度是_33_。解：先構造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL=(4+5+3)X2+(1+2)X3=33WPL=(4+5+3)X2+(1+2)X3=33(注：兩個合并值先后不同會導致編碼不同，即哈夫曼編碼不唯一)(注：合并值應排在葉子值之后)三、單項選擇題(每小題1分，共11分)(C)1.不含任何結點的空樹。(A)是一-棵樹；(E)是一-棵二叉樹

6、；(C)是一棵樹也是一棵二叉樹；(D)既不是樹也不是二叉樹(C)2.二叉樹是非線性數據結構，所以。(A)它不能用順序存儲結構存儲；(E)它不能用鏈式存儲結構存儲；(C)順序存儲結構和鏈式存儲結構都能存儲；(D)順序存儲結構和鏈式存儲結構都不能使用(C)3.具有n(n>0)個結點的完全二叉樹的深度為。(A)log2(n)(B)一log2(n)(C)_log2(n)+1(D)log2(n)+1(A)4.把一棵樹轉換為二叉樹后，這棵二叉樹的形態是。(A)唯一的(B)有多種(C)有多種，但根結點都沒有左孩子(D)有多種，但根結點都沒有右孩子4. 從供選擇的答案中，選出應填入下面敘述?內的最確切的

7、解答，把相應編號寫在答卷的對應欄內。樹是結點的有限集合，它A_根結點，記為T。其余的結點分成為m(m>0)個B的集合T1，T2，Tm，每個集合又都是樹，此時結點T稱為的父結點，稱為T的子結點(Ki<m)。一個結點的子結點個數為該結點的C。供選擇的答案二叉樹_A_。在完全的二叉樹中，若一個結點沒有_B，則它必定是葉結點。每棵樹都能惟一地轉A:有0個或1個有0個或多個有且只有1個有1個或1個以上B:互不相交允許相交允許葉結點相交允許樹枝結點相交C:權維數度序答案:ABC=1，1，36.從供選擇的答案中，選出應填入下面敘述?內的最確切的解答，把相應編號寫在答卷的對應欄內。換成與它對應的二

8、叉樹。由樹轉換成的二叉樹里，一個結點N的左子女是N在原樹里對應結點的C而N的右子女是它在原樹里對應結點的D。供選擇的答案A:是特殊的樹不是樹的特殊形式是兩棵樹的總稱有是只有二個根結點的樹形結構B：左子結點右子結點左子結點或者沒有右子結點兄弟CD:最左口點最右子結點最鄰近的右兄弟最鄰近的左兄弟最左的兄弟最右的兄弟答案：A=B=C=D=答案：ABCDE=2，1,1,3四、簡答題(每小題4分，共20分)1.【嚴題集6.2】一棵度為2的樹與一棵二叉樹有何區別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結點只有一個孩子，就無需區分其左右次序，而在二叉

9、樹中即使是一個孩子也有左右之分。2設如下圖所示的二叉樹B的存儲結構為二叉鏈表，root為根指針，結點結構為：(lchild,data,rchild)。其中Ichild，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：1.對下列二叉樹B，執行下列算法traversal(root)，試指出其輸出結果；2.假定二叉樹B共有n個結點，試分析算法traversal(root)的時間復雜度。(共8分)二叉樹B解：這是“先根再左再根再右”，比前序遍歷多打印各結點一次，輸出結果為：ABCCEEBADFFDGG特點：每個結點肯定都會被打印兩次；但出現的順序不同，其規律是

10、：凡是有左子樹的結點，必間隔左子樹的全部結點后再重復出現；女口A，B，D等結點。反之馬上就會重復出現。女口C，E，F，G等結點。C的結點類型定義如下：structnodechardata;structnode*Ichild,rchild;C算法如下:voidtraversal(structnode*root)if(root)printf(traversal(root->lchild);printf(“c”->data);traversal(root->rchild);時間復雜度以訪問結點的次數為主，精確值為2*n，時間漸近度為0(n).3.【嚴題集6.27】給定二叉樹的兩種遍

11、歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F，試畫出二叉樹B，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應前序遍歷序列中的元素集合，可繼續確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。D4.給定如圖所示二叉樹T,請畫出與其對應的中序線索二叉樹。解：要遵循中序遍歷的軌跡來畫出每個前驅和后繼。中序遍歷序列：5540256028083354NI冬

12、406008545/28252833250833NI40608544055555505分,共20分）五、閱讀分析題（每題1試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。答:DLR:ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD:JFKGDBHLMIECA2把如圖所示的樹轉化成二叉樹。答：注意全部兄弟之間都要連線（包括度為2的兄弟），并注意原有連線結點一律歸入左子樹，新添連線結點一律歸入右子樹。ALGIMJ3.【嚴題集6.17】閱讀下列算法，若有錯，改正之。答：這是找結點后繼的程序。共有3處錯誤。注：當rtag=1時說明內裝后繼指針，可直接返回，第一句無錯

13、。當rtag=0時說明內裝右孩子指針，但孩子未必是后繼，需要計算。中序遍歷應當先左再根再右，所以應當找左子樹直到葉子處。r=r->lchild;直到LTag=1;應改為:whiie(!r->Ltag)r=r->Lchiid;BiTreeInSucc(BiTreeq)/已知q是指向中序線索二叉樹上某個結點的指針，/本函數返回指向*q的后繼的指針。r=q->rchild;/應改為r=q;if(!r->rtag)while(!r->rtag)r=r->rchild;/應改為while(!r->Ltag)r=r->Lchild;returnr;應改

14、為returnr->rchild;4.【嚴題集6.21】畫出和下列二叉樹相應的森林。答：注意根右邊的子樹肯定是森林，而孩子結點的右子樹均為兄弟。六、算法設計題(前5題中任選2題，第6題必做，每題8分，共24分)1已知一棵具有n個結點的完全二叉樹被順序存儲于一維數組A中，試編寫一個算法打印出編號為i的結點的雙親和所有的孩子。答：首先，由于是完全二叉樹，不必擔心中途會出現孩子為null的情況。其次分析：結點i的左孩子為2i，右孩子為2i+1;直接打印即可。Printf(“Left_child=”,%d,v2*iRjaha_child=”,%d,v2*i+1.data;);但其雙親是i/2，需

15、先判斷i為奇數還是偶數。若i為奇數，則應當先i-，然后再除以2。lf(i/2!=0)i-;Printf(“Parents=”,%d,vi/2.data;);【嚴題集6.49】編寫算法判別給定二叉樹是否為完全二叉樹。答：intlsFull_Bitree(BitreeT)/判斷二叉樹是否完全二叉樹，是則返回1,否則返回0InitQueue(Q);flag=0;EnQueue(Q,T);/建立工作隊列while(!QueueEmpty(Q)DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;elseEnQueue(Q,p->lchild);EnQueue

16、(Q,p->rchild);/不管孩子是否為空，都入隊列/whilereturn1;/lsFull_Bitree分析:該問題可以通過層序遍歷的方法來解決與6.47相比,作了一個修改，不管當前結點是否有左右孩子，都入隊列這樣當樹為完全二叉樹時，遍歷時得到是一個連續的不包含空指針的序列反之，則序列中會含有空指針2. 【嚴題集6.26】假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為0.07,0.19，07的二進制表示形式是另07的二進制表示形式是另0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設計哈夫曼編碼。使用一種編碼方案。對于上述實例，比較兩種方案的優缺點。解：方案1;哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。字母編號對應編碼1出現頻率1110010.072000.193111100.02411100.0651010.326111110.037010.21811010.10方案比較: