樹結(jié)構(gòu)習(xí)題及答案

1、第5章 樹【例5-1】寫出如圖5-1所示的樹的葉子結(jié)點(diǎn)、非終端結(jié)點(diǎn)、每個(gè)結(jié)點(diǎn)的度及樹深度。ABCDEFGHIJ圖5-1解：（1）葉子結(jié)點(diǎn)有：B、D、F、G、H、I、J。（2）非終端結(jié)點(diǎn)有：A、C、E。（3）每個(gè)結(jié)點(diǎn)的度分別是：A的度為4，C的度為2，E的度為3，其余結(jié)點(diǎn)的度為0。（4）樹的深度為3?！纠?-2】一棵度為2的樹與一棵二叉樹有什么區(qū)別？解：度為2的樹有兩個(gè)分支，但分支沒有左右之分；一棵二叉樹也有兩個(gè)分支，但有左右之分，左右子樹的次序不能交換?！纠?-3】樹與二叉樹有什么區(qū)別？解：區(qū)別有兩點(diǎn)：（1）二叉樹的一個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹，樹則不然；（2）二叉樹的一個(gè)結(jié)點(diǎn)的子樹有左右之分，而樹

2、的子樹沒有次序?！纠?-4】分別畫出具有3個(gè)結(jié)點(diǎn)的樹和三個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。解：如圖5-2(a)所示，具有3個(gè)結(jié)點(diǎn)的樹有兩種不同形態(tài)。圖5-2(a)如圖5-2(b)所示，具有3個(gè)結(jié)點(diǎn)的二叉樹有以下五種不同形態(tài)。圖5-2(b)【例5-5】如圖5-3所示的二叉樹，試分別寫出它的順序表示和鏈接表示（二叉鏈表）。解：（1）順序表示。1234567891011abcdefg（2）該二叉樹的二叉鏈表表示如圖5-4所示。abcdefg圖5-4【例5-6】試找出滿足下列條件的所有二叉樹：（1）先序序列和中序序列相同；（2）中序序列和后序序列相同；（3）先序序列和后序序列相同。解：（1）先序序列和中序

3、序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹。bacdef圖5-5【例5-7】如圖5-5所示的二叉樹，要求：（1）寫出按先序、中序、后序遍歷得到的結(jié)點(diǎn)序列。（2）畫出該二叉樹的后序線索二叉樹。解：（1）先序遍歷序列：ABDEFC中序遍歷序列：DEFBAC后序遍歷序列：FEDBCA（2）其后序線索二叉樹如圖5-6所示。NULLcabdef圖5-6A圖5-7BCDEFGHIKLMJ【例5-8】將圖5-7所示的樹轉(zhuǎn)換為二叉樹。解：第一步，加

4、線。第二步，抹線。第三步，旋轉(zhuǎn)。過程如圖5-8所示。A圖5-8(a) 第一步加線BCDEFGHIKLMJA圖5-8(b) 第二步抹線BCDEFGHIKLMJAB圖5-8(c) 第三步旋轉(zhuǎn)CFDKGELHMIJABCDEFHIJ圖5-9【例5-9】將如圖5-9所示的二叉樹轉(zhuǎn)換為樹。解： 第一步，加線。第二步，抹線。第三步，調(diào)整。過程如圖5-10所示。ABDHCFEJIBACDEFHIJ第一步第二步第三步BACDEFHIJ圖5-10【例5-10】將如圖5-11所示的森林轉(zhuǎn)換成二叉樹。圖5-11CDEFGABHILJK解： 步驟略，結(jié)果如圖5-12所示。CDEFGABHILJK圖5-12【例5-11

5、】假定用于通信的電文由8個(gè)字符A、B、C、D、E、F、G、H組成，各字母在電文中出現(xiàn)的概率為5、25、4、7、9、12、30、8，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。解： 根據(jù)題意，設(shè)這8個(gè)字母對應(yīng)的權(quán)值分別為（5，25，4，7，9，12，30，8），并且n=8。第一步：25547912308（1）設(shè)計(jì)哈夫曼樹的步驟如圖5-13所示。第四步：2579123081554918第五步：257912308155491827第六步：25309549187128152743第二步：257912305498第三步：25791230549815第七步：2530954918712815274357第八步：25954

6、91843307128152757100圖5-13（2）設(shè)計(jì)哈夫曼編碼利用第八步得到的哈夫曼樹，規(guī)定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼編碼如下表示：A:0011B:01 C:0010D:1010E:000F:100G:11 H:1011習(xí)題5一、單項(xiàng)選擇題1. 在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（ 1. C）個(gè)。A. 4B. 5C. 6D. 72. 假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（2. B ）個(gè)。A. 15B. 16C. 17D. 473.

7、 假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（3. C ）。A. 3 B. 4C. 5D. 64. 在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（ 4. D）。A. 2B. 4 C. 6D. 85. 用順序存儲的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R1.n，結(jié)點(diǎn)Ri若有左孩子，其左孩子的編號為結(jié)點(diǎn)（5. B）。A. R2i+1B. R2iC. Ri/2D. R2i-16. 由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（6. D ）。A. 24B. 48C. 72D. 537. 線索二叉樹是一種（ 7. C）結(jié)構(gòu)。A. 邏輯 B. 邏輯和存儲C. 物理 D. 線

8、性8. 線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是（ 8. B）。A. p->lc=NULL B. p->ltag=1 C. p->ltag=1 且p->lc=NULL D. 以上都不對9. 設(shè)n , m 為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（9. B）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孫10. 如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的（10. B ）。A. 中序B. 前序C. 后序D. 層次序11. 欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（

9、11. A）存儲結(jié)構(gòu)。A. 三叉鏈表B. 廣義表C. 二叉鏈表 D. 順序12. 下面敘述正確的是（ 12. D）。A. 二叉樹是特殊的樹B. 二叉樹等價(jià)于度為2的樹C. 完全二叉樹必為滿二叉樹D. 二叉樹的左右子樹有次序之分13. 任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（13. A ）。A. 不發(fā)生改變 B. 發(fā)生改變C. 不能確定 D. 以上都不對14. 已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（14. B ）。A. 1 B. 2C. 3D. 415. 根據(jù)先序序列ABDC和中序序列DBAC確定對應(yīng)的二叉樹，該二叉樹（ 15. A ）。A. 是完全二

10、叉樹 B. 不是完全二叉樹C. 是滿二叉樹D. 不是滿二叉樹二、判斷題1. 二叉樹中每個(gè)結(jié)點(diǎn)的度不能超過2，所以二叉樹是一種特殊的樹。（1.×）2. 二叉樹的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。（ 2. ）3. 線索二叉樹是一種邏輯結(jié)構(gòu)。（3.×）4. 哈夫曼樹的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。（4.）5. 由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。（5.×）6. 樹的后序遍歷與其對應(yīng)的二叉樹的后序遍歷序列相同。（6.）7. 根據(jù)任意一種遍歷序列即可唯一確定對應(yīng)的二叉樹。（7.）8. 滿二叉樹也是完全二叉樹。（8.）9. 哈夫曼樹一定是完全二叉樹

11、。（9.×）10. 樹的子樹是無序的。（10.×）三、填空題1. 假定一棵樹的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹的度為_，樹的深度為_，終端結(jié)點(diǎn)的個(gè)數(shù)為_，單分支結(jié)點(diǎn)的個(gè)數(shù)為_，雙分支結(jié)點(diǎn)的個(gè)數(shù)為_，三分支結(jié)點(diǎn)的個(gè)數(shù)為_，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_，其孩子結(jié)點(diǎn)為_和_結(jié)點(diǎn)。1. 3，4，6，1，1，2，A，F(xiàn)，G2. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_個(gè)。2. n+13. 對于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵_二叉樹時(shí)具有最小高度，即為_，當(dāng)它為一棵單支樹具有_高度，即為_。3. 完全，最

12、大，n4. 由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為_。4. 555. 在一棵二叉排序樹上按_遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。5. 中序6. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時(shí)，其二叉鏈表中的指針域的總數(shù)為_個(gè)，其中_個(gè)用于鏈接孩子結(jié)點(diǎn)，_個(gè)空閑著。6. 2n，n-1，n+17. 在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=_。7. n2+18. 一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_，最大值為_。8. 2k-1，2k-1，2k-19. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有_種不同

13、的形態(tài)。9. 510. 設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_。10. 2h-111. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，_形態(tài)達(dá)到最大深度，_形態(tài)達(dá)到最小深度。11. 單支樹，完全二叉樹12. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號為i(1in)，則它的左孩子結(jié)點(diǎn)的編號為_，右孩子結(jié)點(diǎn)的編號為_，雙親結(jié)點(diǎn)的編號為_。12. 2i，2i+1，i/2（或ëi/2û）13. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲時(shí)，鏈表中指針域的總數(shù)為_個(gè)，其中_個(gè)用于鏈接孩子結(jié)點(diǎn)，_個(gè)空閑著。13. 2n，n-1，n+114. 哈夫曼樹是指

14、_的二叉樹。14. 帶權(quán)路徑長度最小15. 空樹是指_，最小的樹是指_。15. 結(jié)點(diǎn)數(shù)為0，只有一個(gè)根結(jié)點(diǎn)的樹16. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有_和_兩種。16. 二叉鏈表，三叉鏈表17. 三叉鏈表比二叉鏈表多一個(gè)指向_的指針域。17. 雙親結(jié)點(diǎn)18. 線索是指_。18. 指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19. 線索鏈表中的rtag域值為_時(shí)，表示該結(jié)點(diǎn)無右孩子，此時(shí)_域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。19. 1，RChild20. 本節(jié)中我們學(xué)習(xí)的樹的存儲結(jié)構(gòu)有_、_和_。20. 孩子表示法，雙親表示法，長子兄弟表示法四、應(yīng)用題1. 已知一棵樹邊的集合為<i，m>，<i，n>，&

15、lt;e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>，請畫出這棵樹，并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)g的雙親？（4）哪些是結(jié)點(diǎn)g的祖先？（5）哪些是結(jié)點(diǎn)g的孩子？（6）哪些是結(jié)點(diǎn)e的孩子？（7）哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？（8）結(jié)點(diǎn)b和n的層次號分別是什么？（9）樹的深度是多少？（10）以結(jié)點(diǎn)c為根的子樹深度是多少？1. 解答：abcd

16、egfhimnjki圖5-15根據(jù)給定的邊確定的樹如圖5-15所示。其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號分別是2和5；樹的深度為5。4. 已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。4. 解答：先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA6. 找出所有滿足下列條件的二叉樹：（1）它們在先序遍歷和中序遍歷時(shí)，得到的遍歷序列相同；（2）它們在后序遍歷和中序遍歷時(shí)，得到的遍歷序列相同；（3）它們在先序遍歷和后序遍歷時(shí)，得到的遍歷序列相同；6. 解答：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹。7. 假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。7. 解答：后序序列：ACDBGJKIHFE8.