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

1、第第 5 章章 樹樹【例 5-1】寫出如圖 5-1 所示的樹的葉子結(jié)點、非終端結(jié)點、每個結(jié)點的度及樹深度。解：（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?！纠?5-2】一棵度為 2 的樹與一棵二叉樹有什么區(qū)別？解：度為 2 的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有左右之分，左右子樹的次序不能交換?！纠?5-3】樹與二叉樹有什么區(qū)別？解：區(qū)別有兩點：（1）二叉樹的一個結(jié)點至多有兩個子樹，樹則不然；（2）二叉樹的一個結(jié)點的子樹有

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

3、相同；（3）先序序列和后序序列相同。解：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點的二叉樹?！纠?5-7】如圖 5-5 所示的二叉樹，要求：（1）寫出按先序、中序、后序遍歷得到的結(jié)點序列。（2）畫出該二叉樹的后序線索二叉樹。解：（1）先序遍歷序列：ABDEFC中序遍歷序列：DEFBAC后序遍歷序列：FEDBCA（2）其后序線索二叉樹如圖 5-6 所示。bacdef圖 5-5NULLcabdef圖 5-6abcdefg圖

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

5、圖 5-12圖 5-11CDEFGABHILJKABDHCFEJIBACDEFHIJ第一步第二步第三步BACDEFHIJ圖 5-10【例 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 所示。（2）設(shè)計哈夫曼編碼利用第八步得到的哈夫曼樹，規(guī)定左分支用 0 表示，右分支用 1 表示，字母A、B、C、D、E、F、G、H 的

6、哈夫曼編碼如下表示：A:0011B:01 C:0010D:1010第一步：25547912308第二步：257912305498第三步：25791230549815第四步：2579123081554918第五步：257912308155491827第六步：25309549187128152743第七步：2530954918712815274357第八步：2595491843307128152757100圖 5-13E:000F:100G:11 H:1011習(xí)題習(xí)題 5一、單項選擇題1. 在一棵度為 3 的樹中，度為 3 的結(jié)點數(shù)為 2 個，度為 2 的結(jié)點數(shù)為 1 個，度為 1 的結(jié)點數(shù)為 2

7、 個，則度為 0 的結(jié)點數(shù)為（ 1. C）個。A. 4B. 5C. 6D. 72. 假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為 15，單分支結(jié)點數(shù)為 30 個，則葉子結(jié)點數(shù)為（2. B ）個。A. 15B. 16C. 17D. 473. 假定一棵三叉樹的結(jié)點數(shù)為 50，則它的最小高度為（3. C ） 。A. 3 B. 4C. 5D. 64. 在一棵二叉樹上第 4 層的結(jié)點數(shù)最多為（ 4. D） 。A. 2B. 4 C. 6D. 85. 用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中 R1.n，結(jié)點 Ri若有左孩子，其左孩子的編號為結(jié)點（5. B） 。A. R2i+1B. R2iC. Ri/2

8、D. R2i-16. 由權(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=NULL B. p-ltag=1 C. p-ltag=1 且 p-lc=NULL D. 以上都不對9. 設(shè) n , m 為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中 n 在 m 前的條件是（9. B） 。 A. n 在 m 右方 B. n 在 m 左方 C. n

9、是 m 的祖先 D. n 是 m 的子孫10. 如果 F 是由有序樹 T 轉(zhuǎn)換而來的二叉樹，那么 T 中結(jié)點的前序就是 F 中結(jié)點的（10. B ） 。A. 中序B. 前序C. 后序D. 層次序11. 欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（ 11. A）存儲結(jié)構(gòu)。A. 三叉鏈表B. 廣義表C. 二叉鏈表 D. 順序12. 下面敘述正確的是（ 12. D） 。A. 二叉樹是特殊的樹B. 二叉樹等價于度為 2 的樹C. 完全二叉樹必為滿二叉樹D. 二叉樹的左右子樹有次序之分13. 任何一棵二叉樹的葉子結(jié)點在先序、中序和后序遍歷序列中的相對次序（13. A ） 。

10、A. 不發(fā)生改變 B. 發(fā)生改變C. 不能確定 D. 以上都不對14. 已知一棵完全二叉樹的結(jié)點總數(shù)為 9 個，則最后一層的結(jié)點數(shù)為（14. B ） 。A. 1 B. 2C. 3D. 415. 根據(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 時）不能

11、為偶數(shù)。（4.）5. 由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。（5.）6. 樹的后序遍歷與其對應(yīng)的二叉樹的后序遍歷序列相同。（6.）7. 根據(jù)任意一種遍歷序列即可唯一確定對應(yīng)的二叉樹。（7.）8. 滿二叉樹也是完全二叉樹。（8.）9. 哈夫曼樹一定是完全二叉樹。（9.）10. 樹的子樹是無序的。（10.）三、填空題1. 假定一棵樹的廣義表表示為 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

12、，1，2，A，F(xiàn)，G2. 設(shè) F 是一個森林，B 是由 F 轉(zhuǎn)換得到的二叉樹，F(xiàn) 中有 n 個非終端結(jié)點，則 B 中右指針域為空的結(jié)點有_個。2. n+13. 對于一個有 n 個結(jié)點的二叉樹，當(dāng)它為一棵_二叉樹時具有最小高度，即為_，當(dāng)它為一棵單支樹具有_高度，即為_。3. 完全，2log (1)n，最大，n4. 由帶權(quán)為 3，9，6，2，5 的 5 個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為_。4. 555. 在一棵二叉排序樹上按_遍歷得到的結(jié)點序列是一個有序序列。5. 中序6. 對于一棵具有 n 個結(jié)點的二叉樹，當(dāng)進行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為_個，其中_個用于鏈接孩子結(jié)點

13、，_個空閑著。6. 2n，n-1，n+17. 在一棵二叉樹中，度為 0 的結(jié)點個數(shù)為 n0，度為 2 的結(jié)點個數(shù)為 n2，則 n0=_。7. n2+18. 一棵深度為 k 的滿二叉樹的結(jié)點總數(shù)為_，一棵深度為 k 的完全二叉樹的結(jié)點總數(shù)的最小值為_，最大值為_。8. 2k-1，2k-1，2k-19. 由三個結(jié)點構(gòu)成的二叉樹，共有_種不同的形態(tài)。9. 510. 設(shè)高度為 h 的二叉樹中只有度為 0 和度為 2 的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為_。10. 2h-111. 一棵含有 n 個結(jié)點的 k 叉樹，_形態(tài)達(dá)到最大深度，_形態(tài)達(dá)到最小深度。11. 單支樹，完全二叉樹12. 對于一棵具

14、有 n 個結(jié)點的二叉樹，若一個結(jié)點的編號為 i(1in)，則它的左孩子結(jié)點的編號為_，右孩子結(jié)點的編號為_，雙親結(jié)點的編號為_。12. 2i，2i+1，i/2（或 i/2）13. 對于一棵具有 n 個結(jié)點的二叉樹，采用二叉鏈表存儲時，鏈表中指針域的總數(shù)為_個，其中_個用于鏈接孩子結(jié)點，_個空閑著。13. 2n，n-1，n+114. 哈夫曼樹是指_的二叉樹。14. 帶權(quán)路徑長度最小15. 空樹是指_，最小的樹是指_。15. 結(jié)點數(shù)為 0，只有一個根結(jié)點的樹16. 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有_和_兩種。16. 二叉鏈表，三叉鏈表17. 三叉鏈表比二叉鏈表多一個指向_的指針域。17. 雙親結(jié)點18. 線

15、索是指_。18. 指向結(jié)點前驅(qū)和后繼信息的指針19. 線索鏈表中的 rtag 域值為_時，表示該結(jié)點無右孩子，此時_域為指向該結(jié)點后繼線索的指針。19. 1，RChild20. 本節(jié)中我們學(xué)習(xí)的樹的存儲結(jié)構(gòu)有_、_和_。20. 孩子表示法，雙親表示法，長子兄弟表示法四、應(yīng)用題1. 已知一棵樹邊的集合為，請畫出這棵樹，并回答下列問題：（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）

16、樹的深度是多少？（10）以結(jié)點 c 為根的子樹深度是多少？1. 解答：根據(jù)給定的邊確定的樹如圖 5-15 所示。其中根結(jié)點為 a；葉子結(jié)點有：d、m、n、j、k、f、l；c 是結(jié)點 g 的雙親；a、c 是結(jié)點 g 的祖先；j、k 是結(jié)點 g 的孩子；m、n 是結(jié)點 e 的子孫；abcdegfhimnjki圖 5-15e 是結(jié)點 d 的兄弟；g、h 是結(jié)點 f 的兄弟；結(jié)點 b 和 n 的層次號分別是 2 和 5；樹的深度為 5。4. 已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。4. 解答：先序序列：ABDHIEJKCFLG中序序列：HD

17、IBJEKALFCG后序序列：HIDJKEBLFGCA6. 找出所有滿足下列條件的二叉樹：（1）它們在先序遍歷和中序遍歷時，得到的遍歷序列相同；（2）它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；（3）它們在先序遍歷和后序遍歷時，得到的遍歷序列相同；6. 解答：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點的二叉樹。7. 假設(shè)一棵二叉樹的先序序列為 EBADCFHGIKJ，中序序列為 ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。7. 解答：后序序列：ACDBGJKIHFE8. 假設(shè)一棵二