,.第5章 樹【例5-1】寫出如圖5-1所示的樹的葉子結(jié)點、非終端結(jié)點、每個結(jié)點的度及樹深度。感謝閱讀AB C D EF G H I J圖5-1解：（1）葉子結(jié)點有：B、D、F、G、H、I、J。（2）非終端結(jié)點有：A、C、E。（3）每個結(jié)點的度分別是：A的度為4，C的度為2，E的度為3，其余結(jié)點的度為0。精品文檔放心下載（4）樹的深度為3?！纠?-2】一棵度為2的樹與一棵二叉樹有什么區(qū)別？感謝閱讀解：度為2的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有感謝閱讀左右之分，左右子樹的次序不能交換。【例5-3】樹與二叉樹有什么區(qū)別？解：區(qū)別有兩點：（1）二叉樹的一個結(jié)點至多有兩個子樹，樹則不然；（2）二叉樹的一個結(jié)點的子樹有左右之分，而樹的子樹沒有次序。謝謝閱讀【例5-4】分別畫出具有3個結(jié)點的樹和三個結(jié)點的二叉樹的所有不同形態(tài)。精品文檔放心下載,.解：如圖5-2(a)所示，具有3個結(jié)點的樹有兩種不同形態(tài)。謝謝閱讀5-2(a)如圖5-2(B)所示，具有3個結(jié)點的二叉樹有以下五種不同形態(tài)。謝謝閱讀5-2(b)【例5-5】如圖5-3所示的二叉樹，試分別寫出它的順序表示和鏈接表示（二叉鏈表）。感謝閱讀解：（1）順序表示。1234567891011a b c d e ^ ^ ^ ^ f g,.（2）該二叉樹的二叉鏈表表示如圖5-4所示。ab ∧ c ∧∧ d ∧ e∧ f ∧ ∧g∧5-4【例5-6】試找出滿足下列條件的所有二叉樹：（1）先序序列和中序序列相同；（2）中序序列和后序序列相同；（3）先序序列和后序序列相同。解：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉感謝閱讀樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉感謝閱讀樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點的二叉樹。謝謝閱讀,.a【例5-7】如圖5-5所示的二叉樹，要求：b c（1）寫出按先序、中序、后序遍歷得到的結(jié)點序列。de （2）畫出該二叉樹的后序線索二叉樹。f 解：5-5（1） 先序遍歷序列：ABDEFC中序遍歷序列：DEFBAC后序遍歷序列：FEDBCA（2）其后序線索二叉樹如圖5-6所示。ab cdefNULL5-6,.【例5-8】將圖5-7所示的樹轉(zhuǎn)換為二叉樹。AB C D EF G H I JK L M5-7解：第一步，加線。第二步，抹線。第三步，旋轉(zhuǎn)。過程如圖5-8所示。感謝閱讀A AB C D E B C D EF G H I J F G H I JK L M K L M圖5-8(a)第一步 加線 圖5-8(b)第二步抹線謝謝閱讀ABCF DK G EHMIJ圖5-8(c)第三步 旋轉(zhuǎn),.ABC DE F HI J5-9【例5-9】將如圖5-9所示的二叉樹轉(zhuǎn)換為樹。感謝閱讀解：第一步，加線。第二步，抹線。第三步，調(diào)整。過程如圖5-10所示。謝謝閱讀A AAB BC D C D B D HE F H E F H C F JI J I J E I第一步 第二步 第三步5-10,.【例5-10】將如圖5-11所示的森林轉(zhuǎn)換成二叉樹。感謝閱讀ACDHBEILFGJK圖5-11解：步驟略，結(jié)果如圖5-12所示。AB CDE HF IG J LK5-12,.【例5-11】假定用于通信的電文由8個字符A、B、C、D、E、F、G、H組成，各字母在謝謝閱讀電文中出現(xiàn)的概率為5％、25％、4％、7％、9％、12％、30％、8％，試為這8個字母設(shè)感謝閱讀計哈夫曼編碼。解：根據(jù)題意，設(shè)這8個字母對應(yīng)的權(quán)值分別為（5，25，4，7，9，12，30，8），謝謝閱讀并且n=8。（1）設(shè)計哈夫曼樹的步驟如圖5-13所示。第一步：52547912308第二步：2579123089第四步：251230151845789945第五步：2530271812 15 9 9,.第三步： 25 9 12 30第七步： 5727 3012 157 8第八步： 10043

15 97 8 4 54318 259 94 5571825273099121545785-13,.（2）設(shè)計哈夫曼編碼利用第八步得到的哈夫曼樹，規(guī)定左分支用0表示，右分支用1表示，字母A、B、C、謝謝閱讀D、E、F、G、H的哈夫曼編碼如下表示：A:0011B:01C:0010D:1010E:000F:100G:11H:1011習(xí)題5一、單項選擇題在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（1.C）個。感謝閱讀假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為（2.B）個。謝謝閱讀A.15B.16C.17D.473.假定一棵三叉樹的結(jié)點數(shù)為50，則它的最小高度為（3.C）。A.3B.4C.5D.64.在一棵二叉樹上第4層的結(jié)點數(shù)最多為（4.D）。A.2B.4C.6D.8,.用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中R[1..n]，結(jié)點R[i]若有左孩子，其左孩子的編號為結(jié)點（5.B）。精品文檔放心下載由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（6.D）。精品文檔放心下載A.24B.48C.72D.537.線索二叉樹是一種（7.C）結(jié)構(gòu)。A.邏輯B.邏輯和存儲C.物理D.線性8.線索二叉樹中，結(jié)點p沒有左子樹的充要條件是（8.B）。A.p->lc=NULLB.p->ltag=1C.p->ltag=1且p->lc=NULLD.以上都不對9.設(shè)n,m為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件是（9.B）。A.n在m右方B.n在m左方C.n是m的祖先D.n是m的子孫如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序就是F中結(jié)點的（10.謝謝閱讀B）。欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用感謝閱讀11.A）存儲結(jié)構(gòu)。下面敘述正確的是（12.D）。二叉樹是特殊的樹二叉樹等價于度為2的樹,.完全二叉樹必為滿二叉樹二叉樹的左右子樹有次序之分任何一棵二叉樹的葉子結(jié)點在先序、中序和后序遍歷序列中的相對次序（13.A）。感謝閱讀A.不發(fā)生改變 B.發(fā)生改變C.不能確定 D.以上都不對已知一棵完全二叉樹的結(jié)點總數(shù)為9個，則最后一層的結(jié)點數(shù)為（14.B）。謝謝閱讀根據(jù)先序序列ABDC和中序序列DBAC確定對應(yīng)的二叉樹，該二叉樹（15.A）。精品文檔放心下載A.是完全二叉樹B.不是完全二叉樹C.是滿二叉樹D.不是滿二叉樹二、判斷題1.二叉樹中每個結(jié)點的度不能超過2，所以二叉樹是一種特殊的樹。（1.×）2.二叉樹的前序遍歷中，任意結(jié)點均處在其子女結(jié)點之前。（2.√）3.線索二叉樹是一種邏輯結(jié)構(gòu)。（3.×）4.哈夫曼樹的總結(jié)點個數(shù)（多于1時）不能為偶數(shù)。（4.√）5.由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。（5.×）6.樹的后序遍歷與其對應(yīng)的二叉樹的后序遍歷序列相同。（6.√）7.根據(jù)任意一種遍歷序列即可唯一確定對應(yīng)的二叉樹。（7.√）8.滿二叉樹也是完全二叉樹。（8.√）9.哈夫曼樹一定是完全二叉樹。（9.×）,.10.樹的子樹是無序的。 （10.× ）三、填空題假定一棵樹的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹的度為_____，精品文檔放心下載樹的深度為_____，終端結(jié)點的個數(shù)為______，單分支結(jié)點的個數(shù)為______，雙分支結(jié)點的個數(shù)為______，三分支結(jié)點的個數(shù)為_______，C結(jié)點的雙親結(jié)點為_______，其孩子結(jié)點為_______感謝閱讀和_______結(jié)點。1.3，4，6，1，1，2，A，F(xiàn)，G謝謝閱讀設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有_______個。2.n+1精品文檔放心下載對于一個有n個結(jié)點的二叉樹，當(dāng)它為一棵________二叉樹時具有最小高度，即為_______，謝謝閱讀log(n1)當(dāng)它為一棵單支樹具有_______高度，即為_______。3.完全， 2 ，最大，n謝謝閱讀由帶權(quán)為3，9，6，2，5的5個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為___。精品文檔放心下載55在一棵二叉排序樹上按_______遍歷得到的結(jié)點序列是一個有序序列。5.中序感謝閱讀對于一棵具有n個結(jié)點的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為精品文檔放心下載_______個，其中_______個用于鏈接孩子結(jié)點，_______個空閑著。6.2n，n-1，n+1感謝閱讀在一棵二叉樹中，度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0=______。7.n2+1感謝閱讀一棵深度為k的滿二叉樹的結(jié)點總數(shù)為_______，一棵深度為k的完全二叉樹的結(jié)點總數(shù)的最小值為_____，最大值為______。8.2k-1，2k-1，2k-1感謝閱讀由三個結(jié)點構(gòu)成的二叉樹，共有____種不同的形態(tài)。9.5感謝閱讀設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為____。10.2h-1精品文檔放心下載一棵含有n個結(jié)點的k叉樹，______形態(tài)達(dá)到最大深度，____形態(tài)達(dá)到最小深度。11.單感謝閱讀,.支樹，完全二叉樹對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i(1≤i≤n)，則它的左孩子結(jié)點的編號為________，右孩子結(jié)點的編號為________，雙親結(jié)點的編號為________。12.2i，2i+1，i/2（或i/2）謝謝閱讀對于一棵具有n個結(jié)點的二叉樹，采用二叉鏈表存儲時，鏈表中指針域的總數(shù)為感謝閱讀_________個，其中___________個用于鏈接孩子結(jié)點，_____________個空閑著。13.2n，n-1，n+1謝謝閱讀哈夫曼樹是指________________________________________________的二叉樹。14.帶權(quán)路徑長度最小感謝閱讀空樹是指________________________，最小的樹是指_______________________。15.結(jié)點數(shù)為0，只有一個根結(jié)點的樹感謝閱讀二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有______________和_______________兩種。16.二叉鏈表，三叉鏈精品文檔放心下載表三叉鏈表比二叉鏈表多一個指向______________的指針域。17.雙親結(jié)點精品文檔放心下載線索是指___________________________________________。18.指向結(jié)點前驅(qū)和后繼信息的指針感謝閱讀線索鏈表中的rtag域值為_____時，表示該結(jié)點無右孩子，此時______域為指向該結(jié)點后繼線索的指針。19.1，RChild精品文檔放心下載本節(jié)中我們學(xué)習(xí)的樹的存儲結(jié)構(gòu)有_____________、___________和___________。20.孩子表示法，雙親表示法，長子兄弟表示法感謝閱讀,.四、應(yīng)用題已知一棵樹邊的集合為{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，請畫出這棵樹，并回答下列問題：精品文檔放心下載（1）哪個是根結(jié)點？（2）哪些是葉子結(jié)點？（3）哪個是結(jié)點g的雙親？（4）哪些是結(jié)點g的祖先？（5）哪些是結(jié)點g的孩子？（6）哪些是結(jié)點e的孩子？（7）哪些是結(jié)點e的兄弟？哪些是結(jié)點f的兄弟？謝謝閱讀（8）結(jié)點b和n的層次號分別是什么？（9）樹的深度是多少？（10）以結(jié)點c為根的子樹深度是多少？解答：根據(jù)給定的邊確定的樹如圖5-15所示。abc其中根結(jié)點為a；degfh葉子結(jié)點有：d、m、n、j、k、f、l；ijkic是結(jié)點g的雙親；m na、c是結(jié)點g的祖先；圖5-15j、k是結(jié)點g的孩子；m、n是結(jié)點e的子孫；,.e是結(jié)點d的兄弟；g、h是結(jié)點f的兄弟；結(jié)點b和n的層次號分別是2和5；樹的深度為5。已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。精品文檔放心下載解答：先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA6.找出所有滿足下列條件的二叉樹：（1）它們在先