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

2、與中根遍歷正好相同，則該二叉樹滿足（A）A所有結(jié)點無左孩子B.所有結(jié)點無右孩子C.只有一個根結(jié)點D.任意一棵二叉樹5一棵非空二叉樹的先根遍歷與中根遍歷正好相反，則該二叉樹滿足（B）B所有結(jié)點無左孩子B.所有結(jié)點無右孩子C.只有一個根結(jié)點D.任意一棵二叉樹6假設一棵二叉樹中度為1的結(jié)點個數(shù)為5，度為2的結(jié)點個數(shù)為3，則這棵二叉樹的葉結(jié)點的個數(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)造的哈夫曼編碼中最大的長度為（B）A2B.3C.4D.510在有n個結(jié)點的二叉樹的二叉鏈表存儲結(jié)構(gòu)中有（C）個空的指

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

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

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

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