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

1、解：(1)(2)(3)(4)葉子結(jié)點(diǎn)有：非終端結(jié)點(diǎn)有:I、JoB、D F、G H、A C、E。每個(gè)結(jié)點(diǎn)的度分別是： A的度為4, C的度為2, E的度為3,其余結(jié)點(diǎn)的度為0。 樹(shù)的深度為3?！纠?-2】一棵度為2的樹(shù)與一棵二叉樹(shù)有什么區(qū)別？解：度為2的樹(shù)有兩個(gè)分支，但分支沒(méi)有左右之分；一棵二叉樹(shù)也有兩個(gè)分支，但有左 右之分，左右子樹(shù)的次序不能交換?！纠?-3】樹(shù)與二叉樹(shù)有什么區(qū)別？解：區(qū)別有兩點(diǎn)：(1)二叉樹(shù)的一個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹(shù)，樹(shù)則不然；(2)二叉樹(shù)的一個(gè)結(jié)點(diǎn)的子樹(shù)有左右之分，而樹(shù)的子樹(shù)沒(méi)有次序。【例5-4 分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和三個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。解：如圖5-2(a)所

2、示，具有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ě)出它的順序表示和鏈接表示(二叉鏈表)解：(1)順序表示。1234567891011abcdeAAAAfg(2)該二叉樹(shù)的二叉鏈表表示如圖5-4所示。【例5-6】試找出滿足下列條件的所有二叉樹(shù):(1)(2)(3)解：(1) 樹(shù)；(2) 樹(shù)；(3)先序序列和中序序列相同;中序序列和后序序列相同;先序序列和后序序列相同。先序序列和中序序列相同的二叉樹(shù)為:中序序列和后序序列相同的二叉樹(shù)為:先序序列和后序序列相同的二叉樹(shù)為:空樹(shù)或者任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉空

3、樹(shù)或者任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉空樹(shù)或僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)。NULL圖5-6【例5-7】如圖5-5所示的二叉樹(shù)，要求：(1)寫(xiě)出按先序、中序、后序遍歷得到的結(jié)點(diǎn)序列。(2)畫(huà)出該二叉樹(shù)的后序線索二叉樹(shù)。解：(1)先序遍歷序列：ABDEFC中序遍歷序列：DEFBAC后序遍歷序列：FEDBCA(2)其后序線索二叉樹(shù)如圖5-6所示?！纠?-8 將圖5-7所示的樹(shù)轉(zhuǎn)換為二叉樹(shù)。過(guò)程如圖解：第一步，加線。第二步，抹線。第三步，旋轉(zhuǎn)。5-8所示?！纠?-9 將如圖5-9所示的二叉樹(shù)轉(zhuǎn)換為樹(shù)。5-10所示。解：第一步，加線。第二步，抹線。第三步，調(diào)整。過(guò)程如圖J【例5-10】將如圖5-11所示的森林轉(zhuǎn)換成

4、二叉樹(shù)。解：步驟略，結(jié)果如圖 5-12所示?！纠?-11】假定用于通信的電文由 8個(gè)字符A B、C、0 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所示。第一步:：5 f25 1 ：4；，：7. 1 191 ：12 .30；8 .第二步:第三步:平30第八步:第七步:圖 5-13(2)設(shè)計(jì)哈夫曼編碼利用第八步得到的哈夫曼樹(shù),規(guī)定左分支用0表示，右分支用1

5、表示，字母A、B、C、D E、F、GA:0011E:000H的哈夫曼編碼如下表示:B:01F:100C:0010G:11D:1010H:1011習(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個(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. 3B. 4C. 5D. 64 .在一棵二叉樹(shù)上第 4層的結(jié)點(diǎn)數(shù)最

6、多為（4. D ）。A. 2B. 4C. 6D. 85 .用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R1.n，結(jié)點(diǎn)Ri若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（5. B ）。A. R2i+1 B. R2i6.由權(quán)值分別為3,8,6,2,5D ）。6.C. Ri/2D. R2i-1的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（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=NULLB. p-ltag=1C. p-ltag=1 且 p

7、-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是m的祖先D. n是m的子孫10 .如果F是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是 F中結(jié)點(diǎn)的（10.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ù)的左右子

8、樹(shù)有次序之分13 .任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（13. A ）。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)14 .已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（14. B ）。A. 1B. 2C. 3D. 415 .根據(jù)先序序列 ABDCF口中序序列 DBACt定對(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. X ）2.二叉樹(shù)的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。（2.V ）3.線索二叉樹(shù)是一種邏

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

10、為,三分支結(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, G2 .設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域 為空的結(jié)點(diǎn)有 個(gè)。2. n+13 .對(duì)于一個(gè)有 n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵 二叉樹(shù)時(shí)具有最小高度，即為 ,當(dāng)它為一棵單支樹(shù)具有 高度，即為 。3.完全，最大，n4 .由帶權(quán)為3, 9, 6, 2, 5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，則帶權(quán)路徑長(zhǎng)度為。4.555 .在一棵二叉排序樹(shù)上按 遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。5.中序6 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，

11、其二叉鏈表中的指針域的總數(shù)為 個(gè)，其中 個(gè)用于鏈接孩子結(jié)點(diǎn)， 個(gè)空閑著。6. 2n , n-1 , n+17 .在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)個(gè)數(shù)為no,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則no=。7.年+18 . 一棵深度為k的滿二叉樹(shù)的結(jié)點(diǎn)總數(shù)為 ，一棵深度為k的完全二叉樹(shù)的結(jié)點(diǎn)總數(shù) 的最小值為 ,最大值為 。8. 2 k-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ù)至 少為。 10. 2 h-111 . 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，形態(tài)達(dá)到最大深度，形態(tài)達(dá)到最小深度。11.單

12、支樹(shù)，完全二叉樹(shù)12 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若一個(gè)結(jié)點(diǎn)的編號(hào)為i（1 wi wn）,則它的左孩子結(jié)點(diǎn)的編號(hào)為 ,右孩子結(jié)點(diǎn)的編號(hào)為 ,雙殺結(jié)點(diǎn)白勺編號(hào)為 o 12. 2i , 2i+1 , i/2 （或 i/2）13 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為個(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 .三叉鏈表比二叉鏈表多

13、一個(gè)指向 的指針域。17.雙親結(jié)點(diǎn)18 .線索是指。 18.指向結(jié)點(diǎn)前驅(qū)和后繼 信息的指針19 .線索鏈表中的rtag域值為 時(shí)，表示該結(jié)點(diǎn)無(wú)右孩子， 此時(shí) 域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。19. 1 , RChild。20.孩20 .本節(jié)中我們學(xué)習(xí)的樹(shù)的存儲(chǔ)結(jié)構(gòu)有 子表示法，雙親表示法，長(zhǎng)子兄弟表示法四、應(yīng)用題1.已知一棵樹(shù)邊的集合為 , , , , , , , , , , , ,請(qǐng)畫(huà)出這棵樹(shù)，并回答下列問(wèn)(1)(2)(3)(4)(5)(6)(8)(9)哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)?哪個(gè)是結(jié)點(diǎn)哪些是結(jié)點(diǎn)哪些是結(jié)點(diǎn)哪些是結(jié)點(diǎn)哪些是結(jié)點(diǎn)的雙親？的祖先？的孩子？的孩子？的兄弟？哪些是結(jié)點(diǎn)結(jié)點(diǎn)b和n的

14、層次號(hào)分別是什么?樹(shù)的深度是多少？f的兄弟?(10)以結(jié)點(diǎn)c為根的子樹(shù)深度是多少?1.解答：根據(jù)給定的邊確定的樹(shù)如圖 其中根結(jié)點(diǎn)為a;葉子結(jié)點(diǎn)有：d、m n、j、 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的層次號(hào)分別是 樹(shù)的深度為5。5-15所示。k、 f、 l ；2和5;4.已知用一維數(shù)組存放的一棵完全二叉樹(shù): 序和后序遍歷序列。ABCDEFGHIJKL寫(xiě)出該二叉樹(shù)的先序、中4.解答:先序序列中序序列后序序列HIDJKEBLFGCAABDHIEJKCFLGHDIBJEKALFCG6 .找出所有滿足下

15、列條件的二叉樹(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è)一棵二叉樹(shù)白后序序列為DCEG