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

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

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

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

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

5、圖 5-12圖 5-11CDEFGABHILJKABDHCFEJIBACDEFHIJ第一步第二步第三步BACDEFHIJ圖 5-10【例 5-11】假定用于通信的電文由 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è)字母對(duì)應(yīng)的權(quán)值分別為（5，25，4，7，9，12，30，8） ，并且 n=8。（1）設(shè)計(jì)哈夫曼樹(shù)的步驟如圖 5-13 所示。（2）設(shè)計(jì)哈夫曼編碼利用第八步得到的哈夫曼樹(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一、單項(xiàng)選擇題1. 在一棵度為 3 的樹(shù)中，度為 3 的結(jié)點(diǎn)數(shù)為 2 個(gè)，度為 2 的結(jié)點(diǎn)數(shù)為 1 個(gè)，度為 1 的結(jié)點(diǎn)數(shù)為 2

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

8、D. R2i-16. 由權(quán)值分別為 3,8,6,2,5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（6. D ） 。A. 24B. 48C. 72D. 537. 線索二叉樹(shù)是一種（ 7. C）結(jié)構(gòu)。A. 邏輯 B. 邏輯和存儲(chǔ)C. 物理 D. 線性8. 線索二叉樹(shù)中，結(jié)點(diǎn) p 沒(méi)有左子樹(shù)的充要條件是（ 8. B） 。A. p-lc=NULL B. p-ltag=1 C. p-ltag=1 且 p-lc=NULL D. 以上都不對(duì)9. 設(shè) n , m 為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中 n 在 m 前的條件是（9. B） 。 A. n 在 m 右方 B. n 在 m 左方 C. n

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

10、A. 不發(fā)生改變 B. 發(fā)生改變C. 不能確定 D. 以上都不對(duì)14. 已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為 9 個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（14. B ） 。A. 1 B. 2C. 3D. 415. 根據(jù)先序序列 ABDC 和中序序列 DBAC 確定對(duì)應(yīng)的二叉樹(shù)，該二叉樹(shù)（ 15. A ） 。A. 是完全二叉樹(shù) B. 不是完全二叉樹(shù)C. 是滿二叉樹(shù)D. 不是滿二叉樹(shù)二、判斷題1. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度不能超過(guò) 2，所以二叉樹(shù)是一種特殊的樹(shù)。（1.）2. 二叉樹(shù)的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。（ 2. ）3. 線索二叉樹(shù)是一種邏輯結(jié)構(gòu)。（3.）4. 哈夫曼樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)（多于 1 時(shí)）不能

11、為偶數(shù)。（4.）5. 由二叉樹(shù)的先序序列和后序序列可以唯一確定一顆二叉樹(shù)。（5.）6. 樹(shù)的后序遍歷與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同。（6.）7. 根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹(shù)。（7.）8. 滿二叉樹(shù)也是完全二叉樹(shù)。（8.）9. 哈夫曼樹(shù)一定是完全二叉樹(shù)。（9.）10. 樹(shù)的子樹(shù)是無(wú)序的。（10.）三、填空題1. 假定一棵樹(shù)的廣義表表示為 A（B（E） ，C（F（H，I，J） ，G） ，D） ，則該樹(shù)的度為_(kāi)，樹(shù)的深度為_(kāi)，終端結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，單分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，雙分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，三分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，C 結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_(kāi)，其孩子結(jié)點(diǎn)為_(kāi)和_結(jié)點(diǎn)。1. 3，4，6，1

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

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

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

15、索是指_。18. 指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19. 線索鏈表中的 rtag 域值為_(kāi)時(shí)，表示該結(jié)點(diǎn)無(wú)右孩子，此時(shí)_域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。19. 1，RChild20. 本節(jié)中我們學(xué)習(xí)的樹(shù)的存儲(chǔ)結(jié)構(gòu)有_、_和_。20. 孩子表示法，雙親表示法，長(zhǎng)子兄弟表示法四、應(yīng)用題1. 已知一棵樹(shù)邊的集合為，請(qǐng)畫(huà)出這棵樹(shù)，并回答下列問(wèn)題：（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 的層次號(hào)分別是什么？（9）

16、樹(shù)的深度是多少？（10）以結(jié)點(diǎn) c 為根的子樹(shù)深度是多少？1. 解答：根據(jù)給定的邊確定的樹(shù)如圖 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 的子孫；abcdegfhimnjki圖 5-15e 是結(jié)點(diǎn) d 的兄弟；g、h 是結(jié)點(diǎn) f 的兄弟；結(jié)點(diǎn) b 和 n 的層次號(hào)分別是 2 和 5；樹(shù)的深度為 5。4. 已知用一維數(shù)組存放的一棵完全二叉樹(shù)：ABCDEFGHIJKL，寫(xiě)出該二叉樹(shù)的先序、中序和后序遍歷序列。4. 解答：先序序列：ABDHIEJKCFLG中序序列：HD

17、IBJEKALFCG后序序列：HIDJKEBLFGCA6. 找出所有滿足下列條件的二叉樹(shù)：（1）它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（2）它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（3）它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的遍歷序列相同；6. 解答：（1）先序序列和中序序列相同的二叉樹(shù)為：空樹(shù)或者任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹(shù)；（2）中序序列和后序序列相同的二叉樹(shù)為：空樹(shù)或者任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹(shù)；（3）先序序列和后序序列相同的二叉樹(shù)為：空樹(shù)或僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)。7. 假設(shè)一棵二叉樹(shù)的先序序列為 EBADCFHGIKJ，中序序列為 ABCDEFGHIJK，請(qǐng)寫(xiě)出該二叉樹(shù)的后序遍歷序列。7. 解答：后序序列：ACDBGJKIHFE8. 假設(shè)一棵二