數(shù)據(jù)結(jié)構(gòu)-二叉樹練習(xí)題答案

PAGEPAGE10數(shù)據(jù)結(jié)構(gòu)第6章樹和二叉樹下面是有關(guān)二叉樹的敘述，請(qǐng)判斷正誤（√）1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n-1個(gè)非空指針域。n個(gè)結(jié)點(diǎn)的二叉樹有n-1條分支（×）2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。（√）3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。（×）4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。（×）5.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。（應(yīng)當(dāng)是二叉排序樹的特點(diǎn)）（×）6.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。（應(yīng)2k-1）（×）7.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。（×）8.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i-1個(gè)結(jié)點(diǎn)。（應(yīng)2i-1）（√）9.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，即有后繼鏈接的指針僅n-1個(gè)，還有n+1個(gè)空指針。）采用二叉鏈表存儲(chǔ)有2n個(gè)鏈域，空鏈域?yàn)椋?n-（n-1）=n+1（√）10.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)＝[n/2]＝6，再求n2=n0-1=5[n/2]除的結(jié)果四舍五入填空1．由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有5種形態(tài)。2.一棵深度為6的滿二叉樹有n1+n2=0+n2=n0-1=31個(gè)分支結(jié)點(diǎn)和26-1=32個(gè)葉子。注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。(或：總結(jié)點(diǎn)數(shù)為n=2k-1=26-1=63，葉子數(shù)為n0=[n/2]=32，滿二叉數(shù)沒有度為1的結(jié)點(diǎn)，由n0=n2+1得n2=n0-1=32-1=31)3．一棵具有２５７個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為9。（注：用log2(n)+1=8.xx+1=9證明：根據(jù)性質(zhì)2，深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。最小的一棵完全二叉樹的結(jié)點(diǎn)數(shù)：（2k-1-1）+1=2k-1最大的一棵完全二叉樹（滿二叉樹）的結(jié)點(diǎn)數(shù)：（2k-1）則：2k-1<=n<2k,取對(duì)數(shù):k-1<=log2n<k,因?yàn)閗是整數(shù),所以:k=log2(n)+14.一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有350個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)＝[n/2]＝3505.設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有500個(gè)葉子結(jié)點(diǎn)，有499個(gè)度為2的結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左子樹，有0個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)＝[n/2]＝500，n2=n0-1=499。另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)＝0.6.一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為n，最小深度為2。答：當(dāng)k=1(單叉樹)時(shí)應(yīng)該最深，深度＝n（層）；當(dāng)k=n-1（n-1叉樹）時(shí)應(yīng)該最淺，深度＝2（層），但不包括n=0或1時(shí)的特例情況。7.二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按DLR次序），后序法（即按LRD次序）和中序法（也稱對(duì)稱序法，即按LDR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是FEGHDCB。

解：法1：先由已知條件畫圖，再后序遍歷得到結(jié)果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹。例如，前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計(jì)算。如B在前序序列中第一，中序中在中間（可知左右子樹上有哪些元素），則在后序中必為最后。如法對(duì)B的左右子樹同樣處理，則問題得解。8.用5個(gè)權(quán)值{3,2,4,5,1}構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度是33。解：先構(gòu)造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33(15)(9)(6)453(3)12三、單項(xiàng)選擇題（C）1．不含任何結(jié)點(diǎn)的空樹。（Ａ）是一棵樹;（Ｂ）是一棵二叉樹;（Ｃ）是一棵樹也是一棵二叉樹;（Ｄ）既不是樹也不是二叉樹答：以前的標(biāo)答是B，因?yàn)槟菚r(shí)樹的定義是n≥1（C）2．二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以。（Ａ）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);（Ｂ）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);（Ｃ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ);（Ｄ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用（C）3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1注1：x表示不小于x的最小整數(shù)；x表示不大于x的最大整數(shù)，它們與[]含義不同！(四舍五入)注2：選（A）是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)冪時(shí)就會(huì)少算一層。log2(n+1)是正確的。（A）4．把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是。（Ａ）唯一的（Ｂ）有多種（Ｃ）有多種，但根結(jié)點(diǎn)都沒有左孩子（Ｄ）有多種，但根結(jié)點(diǎn)都沒有右孩子四、簡答題（每小題4分，共20分）1.一棵度為2的樹與一棵二叉樹有何區(qū)別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結(jié)點(diǎn)只有一個(gè)孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個(gè)孩子也有左右之分。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的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。D ACFEGBHI五、閱讀分析題1.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA2.把如圖所示的樹轉(zhuǎn)化成二叉樹。答：注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結(jié)點(diǎn)一律歸入左子樹，新添連線結(jié)點(diǎn)一律歸入右子樹。ABECKFHDLGIMJ4.畫出和下列二叉樹相應(yīng)的森林。答：注意根右邊的子樹肯定是森林，而孩子結(jié)點(diǎn)的右子樹均為兄弟。5.假設(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ì)哈夫曼編碼。使用0～7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：01010121321010101213210101106123（40）（60）192132(28）(11)7106（5）23方案比較：字母編號(hào)對(duì)應(yīng)編碼字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.07