第6章-樹和二叉樹習題課課件

第6章樹和二叉樹習題課中北大學信息與通信工程學院主講：金永副教授第6章樹和二叉樹習題課中北大學信息與通信工程學院11、已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2、設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）。A．M1B．M1+M2C．M3D．M2+M33、有關(guān)二叉樹下列說法正確的是（）A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2D．二叉樹中任何一個結(jié)點的度都為2選擇題1、已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形24、二叉樹的第I層上最多含有結(jié)點數(shù)為（）A．2IB．2I-1-1C．2I-1D．2I-15、一個具有1025個結(jié)點的二叉樹的高h為（）A．11B．10C．11至1025之間D．10至1024之間6、高度為K的二叉樹最大的結(jié)點數(shù)為（）。A．2k B．2k-1C．2k-1D．2k-1-17、利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）。A．指向最左孩子B．指向最右孩子C．空D．非空8、對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用()次序的遍歷實現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷4、二叉樹的第I層上最多含有結(jié)點數(shù)為（）39、某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則先序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不對10、上題的二叉樹對應的森林包括多少棵樹（）A．lB．2C．3D．概念上是錯誤的11、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是任意一棵二叉樹12、在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（）A．都不相同B．完全相同C．先序和中序相同，而與后序不同D．中序和后序相同，而與先序不同9、某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為413、在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒()。

A．左子結(jié)點B．右子結(jié)點

C．左子結(jié)點和右子結(jié)點

D．左子結(jié)點，右子結(jié)點和兄弟結(jié)點14、n個結(jié)點的線索二叉樹上含有的線索數(shù)為（）A．2nB．n－lC．n＋lD．n15、下述編碼中哪一個不是前綴碼（）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）16、在下述結(jié)論中，正確的是（）①只有一個結(jié)點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A．①②③B．②③④C．②④D．①④13、在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒()517、若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（）

A．9B．11C．15D．不確定18、具有10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點

A．8B．9C．10D．1l19、一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）A．250B．500C．254D．50120、有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（）。A．不確定B．2nC．2n+1D．2n-121、二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是（）。A、EB、F

C、G

D、H17、若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，622、設(shè)森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（）A．m-nB．m-n-1C．n+1D．條件不足，無法確定23、用一維數(shù)組存儲二叉樹時，總是以（）遍歷順序存儲結(jié)點A．先序B.中序C.后序D.按層次遍歷24、對一棵二叉樹進行層次遍歷時，應借助于一個（）。A．順序表B.數(shù)組C.棧D.隊列25、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A．空或只有一個結(jié)點B．任一結(jié)點無左子樹C．高度等于其結(jié)點數(shù)D．任一結(jié)點無右子樹22、設(shè)森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p,p726、設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）A．5B．6C．7D．827、將一棵樹t轉(zhuǎn)換為孩子—兄弟鏈表表示的二叉樹h，則t的后根序遍歷是h的（）A．先序遍歷B．中序遍歷C．后序遍歷28、某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進行編號，編號為1，2，…，n，且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時是按()編號的。A.中序遍歷序列B.先序遍歷序列C.后序遍歷序列D.層次順序26、設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為81、從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（森林的特例）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下，也必須指出是左子樹還是右子樹，樹無此限制。應用題1、從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，9

2、試找出滿足下列條件的二叉樹1）先序序列與后序序列相同；2）中序序列與后序序列相同；3）先序序列與中序序列相同；1)、既不含左子樹，也不含右子樹的二叉樹。2)、不含右子樹的二叉樹。3)、不含左子樹的二叉樹。2、試找出滿足下列條件的二叉樹1)、既不含左子樹，也不含右103、已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，…，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點？根據(jù)樹的定義，在一顆樹中，除樹根結(jié)點外，每個結(jié)點有且僅有一個前驅(qū)結(jié)點，也就是說，每個結(jié)點與指向它的一個分支一一對應，所以除樹根結(jié)點之外的結(jié)點樹等于所有結(jié)點的分支數(shù)，即度數(shù)，從而可得樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1?？偨Y(jié)點數(shù)為而度為0的結(jié)點數(shù)就應為總結(jié)點數(shù)減去度不為0的結(jié)點數(shù)的總和，即3、已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的114、將算術(shù)表達式((a+b)+c*(d+e)+f)*(g+h)轉(zhuǎn)化為二叉樹。++*+fhg*+abc+de5、用一維數(shù)組存放的一棵完全二叉樹如下圖所示：ABCDEFGHIJKL寫出后序遍歷該二叉樹時訪問結(jié)點的順序。HIDJKEBLFGCA4、將算術(shù)表達式((a+b)+c*(d+e)+f)*(g+126、對下圖所示二叉樹分別按先序、中序﹑后序遍歷，給出相應的結(jié)點序列，同時給二叉樹加上中序線索。（1）先序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA6、對下圖所示二叉樹分別按先序、中序﹑后序遍歷，給出相應的結(jié)137、設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC（1）畫出這棵二叉樹。（2）將這棵二叉樹轉(zhuǎn)換成對應的樹（或森林）A B F D C E H G 7、設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列：A14B A C E D F N P G H J M O L I K H G D A C J I B F E M P ON K L 8、將森林轉(zhuǎn)換成對應的二叉樹B A C E D F N P G H J M O L I 159、一棵二叉樹的先序、中序、后序序列如下，其中一部分未標出，請構(gòu)造出該二叉樹。先序序列：__CDE_GHI_K中序序列：CB__FA_JKIG后序序列：_EFDB_JIH_AA B C E D G I H F J K 9、一棵二叉樹的先序、中序、后序序列如下，其中一部分未標出，1610、設(shè)二叉樹BT的存儲結(jié)構(gòu)如下:12345678910Lchild

0

0

2

3

7

5

8

0

10

1DataJ

H

F

D

B

A

C

E

G

IRchild

0

0

0

9

4

0

0

0

0

0其中BT為樹根結(jié)點的指針，其值為6,Lchild,Rchild分別為結(jié)點的左、右孩子指針域,data為結(jié)點的數(shù)據(jù)域。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu);（2）寫出按先序、中序、后序遍歷該二叉樹所得到的結(jié)點序列;（3）畫出二叉樹的后序線索樹。10、設(shè)二叉樹BT的存儲結(jié)構(gòu)如下:12345678910L17BACEDFGHIJ先序序列：ＡＢＣＥＤＦＨＧＩJ中序序列：ECBHFDJIGA后序序列：ＥＣＨＦＪＩＧＤＢＡBACEDFGHIJ先序序列：ＡＢＣＥＤＦＨＧＩJ1811、給定集合{15,3,14,2,6,9,16,17}，(1)構(gòu)造相應的huffman樹，(2)計算它的帶權(quán)路徑長度，(3)寫出它的huffman編碼。16296170

115314011100001101wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229編碼為：15:111,3:10101,14:110,2:101006:10119:10016:0017:0111、給定集合{15,3,14,2,6,9,16,17}，(1912、已知下列字符A、B、C、D、