樹和二叉樹練習題答案.doc

第5章樹和二叉樹練習題答案一、下面是有關二叉樹的敘述，請判斷正誤（ ）1. 若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n1個非空指針域。（ ）2.二叉樹中每個結點的兩棵子樹的高度差等于1。 （ ）3.二叉樹中每個結點的兩棵子樹是有序的。 （ ）4.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。 （ ）5.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。 （應當是二叉排序樹的特點）（ ）6.滿二叉樹中所有結點個數(shù)是2k-1-1，其中k是樹的深度。（應2k-1） （ ）7.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。 （ ）8.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i1個結點。（應2i-1）（ ）9.用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區(qū)域中有n+1個為空指針。（正確。用二叉鏈表存儲包含n個結點的二叉樹，結點共有2n個鏈域。由于二叉樹中，除根結點外，每一個結點有且僅有一個雙親，所以只有n-1個結點的鏈域存放指向非空子女結點的指針，還有n+1個空指針。）即有后繼鏈接的指針僅n-1個。（ ）10.具有12個結點的完全二叉樹有5個度為2的結點。二、填空1 由個結點所構成的二叉樹有 5 種形態(tài)。 2. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結點和 26-1 =32 個葉子。注：滿二叉樹沒有度為1的結點，所以分支結點數(shù)就是二度結點數(shù)。3 一棵具有個結點的完全二叉樹，它的深度為 9 。（ 注：用 log2(n) +1= 8.xx +1=94. 設一棵完全二叉樹有700個結點，則共有 350 個葉子結點。5. 設一棵完全二叉樹具有1000個結點，則此完全二叉樹有 500 個葉子結點，有 499 個度為2的結點，有 1 個結點只有非空左子樹，有 0 個結點只有非空右子樹。答：最快方法：用葉子數(shù)n/2500 ，n2=n0-1=499。 另外，最后一結點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數(shù)0.6. 一棵含有n個結點的k叉樹，可能達到的最大深度為 n ，最小深度為 2 。答：當k=1(單叉樹)時應該最深，深度n（層）；當k=n-1（n-1叉樹）時應該最淺，深度2（層），但不包括n=0或1時的特例情況。7. 二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按N L R次序），后序法（即按 L R N 次序）和中序法（也稱對稱序法，即按L N R次序）。這三種方法相互之間有關聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 F E G H D C B 。 解：法1：先由已知條件畫圖，再后序遍歷得到結果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹。例如，前序遍歷BEFCGDH中，根結點在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計算。如B在前序序列中第一，中序中在中間（可知左右子樹上有哪些元素），則在后序中必為最后。如法對B的左右子樹同樣處理，則問題得解。8.中序遍歷的遞歸算法平均空間復雜度為 O(n) 。答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。9. 用5個權值3, 2, 4, 5, 1構造的哈夫曼（Huffman）樹的帶權路徑長度是 33 。解：先構造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL（453）2（12）3=33 (15)(9) (6) （注：兩個合并值先后不同會導致編碼不同，即哈夫曼編碼不唯一） 4 5 3 (3) （注：合并值應排在葉子值之后）1 2三、單項選擇題（ C ）1 不含任何結點的空樹 。（）是一棵樹; （）是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹（ C ）2二叉樹是非線性數(shù)據(jù)結構，所以 。（）它不能用順序存儲結構存儲; （）它不能用鏈式存儲結構存儲; （）順序存儲結構和鏈式存儲結構都能存儲; （）順序存儲結構和鏈式存儲結構都不能使用 （ C ）3. 具有n(n0)個結點的完全二叉樹的深度為 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+1（ A ）4把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是 。（）唯一的 （）有多種（）有多種，但根結點都沒有左孩子 （）有多種，但根結點都沒有右孩子四、簡答題C的結點類型定義如下：struct nodechar data;struct node *lchild, rchild;C算法如下：void traversal(struct node *root)if (root) printf(“%c”, root-data); traversal(root-lchild); printf(“%c”, root-data);traversal(root-rchild);1.設如下圖所示的二叉樹B的存儲結構為二叉鏈表，root為根指針，結點結構為：（lchild,data,rchild）。其中l(wèi)child，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：(1)對下列二叉樹B，執(zhí)行下列算法traversal(root)，試指出其輸出結果；(2)假定二叉樹B共有n個結點，試分析算法traversal(root)的時間復雜度。（共8分）AB D C F G E二叉樹B解：這是“先根再左再根再右”，比前序遍歷多打印各結點一次，輸出結果為：A B C C E E B A D F F D G G特點：每個結點肯定都會被打印兩次；但出現(xiàn)的順序不同，其規(guī)律是：凡是有左子樹的結點，必間隔左子樹的全部結點后再重復出現(xiàn)；如A，B，D等結點。反之馬上就會重復出現(xiàn)。如C，E，F(xiàn)，G等結點。時間復雜度以訪問結點的次數(shù)為主，精確值為2*n，時間漸近度為O(n).2.給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。 D A C FE GB H I2825 3340 60 08 54 553.給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。解：要遵循中序遍歷的軌跡來畫出每個前驅和后繼。中序遍歷序列：55 40 25 60 28 08 33 54282540555560330854NILNIL 2825 33 40 60 08 54 554.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A5.假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設計哈夫曼編碼。使用07的等長二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號對應編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母編號對應編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(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的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結論：哈夫曼編碼優(yōu)于等長二進制編碼五、算法設計題編寫遞歸算法，計算二叉樹中葉子結點的數(shù)目。解：思路：輸出葉子結點比較簡單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子，將其打印出來。法一：核心部分為：DLR(BiTree 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);法