第5章 樹與二叉樹習(xí)題參考答案

1、習(xí)題五參考答案習(xí)題五參考答案?jìng)渥渥?紅色字體標(biāo)明的是與書本內(nèi)容有改動(dòng)的內(nèi)容紅色字體標(biāo)明的是與書本內(nèi)容有改動(dòng)的內(nèi)容一、選擇題一、選擇題1對(duì)一棵樹進(jìn)行后根遍歷操作與對(duì)這棵樹所對(duì)應(yīng)的二叉樹進(jìn)行（B）遍歷操作相同。A先根B.中根C.后根D.層次2在哈夫曼樹中，任何一個(gè)結(jié)點(diǎn)它的度都是（C）。B0或1B.1或2C.0或2D.0或1或23對(duì)一棵深度為h的二叉樹，其結(jié)點(diǎn)的個(gè)數(shù)最多為（D）。A2hB.2h1C.2h1D.2h14一棵非空二叉樹的先根遍歷

2、與中根遍歷正好相同，則該二叉樹滿足（A）A所有結(jié)點(diǎn)無左孩子B.所有結(jié)點(diǎn)無右孩子C.只有一個(gè)根結(jié)點(diǎn)D.任意一棵二叉樹5一棵非空二叉樹的先根遍歷與中根遍歷正好相反，則該二叉樹滿足（B）B所有結(jié)點(diǎn)無左孩子B.所有結(jié)點(diǎn)無右孩子C.只有一個(gè)根結(jié)點(diǎn)D.任意一棵二叉樹6假設(shè)一棵二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為5，度為2的結(jié)點(diǎn)個(gè)數(shù)為3，則這棵二叉樹的葉結(jié)點(diǎn)的個(gè)數(shù)是（C）A2B.3C.4D.57若某棵二叉樹的先根遍歷序列為ABCDEF，中根遍歷序列為CBDAE

3、F，則這棵二叉樹的后根遍歷序列為（B）。AFEDCBAB.CDBFEAC.CDBEFAD.DCBEFA8若某棵二叉樹的后根遍歷序列為DBEFCA，中根遍歷序列為DBAECF，則這棵二叉樹的先根遍歷序列為（B）。AABCDEFB.ABDCEFC.ABCDFED.ABDECF9根據(jù)以權(quán)值為2，5，7，9，12構(gòu)造的哈夫曼樹所構(gòu)造的哈夫曼編碼中最大的長(zhǎng)度為（B）A2B.3C.4D.510在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中有（C）個(gè)空的指

4、針域。An1B.nC.n1D.0二、填空題二、填空題1.在一棵度為m的樹中，若度為1的結(jié)點(diǎn)有n1個(gè)，度為2的結(jié)點(diǎn)有n2個(gè)，……，度為m的結(jié)點(diǎn)有nm個(gè)，則這棵樹中的葉結(jié)點(diǎn)的個(gè)數(shù)為1n22n33n4…(m1)nm。2.一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度最多為n，最少為[log2n]1。3.一棵具有100個(gè)結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)為50。4.以5，9，12，13，20，30為葉結(jié)點(diǎn)的權(quán)值所構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是217return

5、null3.編寫算法求一棵二叉樹的根結(jié)點(diǎn)root到一個(gè)指定結(jié)點(diǎn)p之間的路徑并輸出。參考答案：參考答案：求根結(jié)點(diǎn)到指定結(jié)點(diǎn)的路徑過程中，采用了后跟遍歷的思想，最終求得的路徑保存在一個(gè)鏈棧中，其中根結(jié)點(diǎn)處于棧頂位置，指定結(jié)點(diǎn)處于棧底位置。下面用到的二叉樹結(jié)點(diǎn)類BiTreeNode在書中第5章中已給出publicLinkStackgetPath(BiTreeNoderootBiTreeNodep)BiTreeNodeT=rootLinkSta

6、ckS=newLinkStack()構(gòu)造鏈棧if(T!=null)S.push(T)根結(jié)點(diǎn)進(jìn)棧Booleanflag訪問標(biāo)記BiTreeNodeq=nullq指向剛被訪問的結(jié)點(diǎn)while(!S.isEmpty())while(S.peek()!=null)將棧頂結(jié)點(diǎn)的所有左孩子結(jié)點(diǎn)入棧S.push(((BiTreeNode)S.peek()).getLchild())S.pop()空結(jié)點(diǎn)退棧while(!S.isEmpty())T=(B

7、iTreeNode)S.peek()查看棧頂元素if(T.getRchild()==null||T.getRchild()==q)if(T.equals(p))對(duì)棧S進(jìn)行倒置，以保證根結(jié)點(diǎn)處于棧頂位置LinkStackS2=newLinkStack()while(!S.isEmpty())S2.push(S.pop())returnS2S.pop()移除棧頂元素q=Tq指向剛被訪問的結(jié)點(diǎn)flag=true設(shè)置訪問標(biāo)記elseS.push