《數(shù)據(jù)結(jié)構(gòu)》習(xí)題匯編06第六章樹(shù)和二叉樹(shù)試題

1、第六章 樹(shù)和二叉樹(shù) 試題一、單項(xiàng)選擇題1. 樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ ）。 A. 0 B. 1 C. -1 D. 22. 在一棵樹(shù)中，（ ）沒(méi)有前驅(qū)結(jié)點(diǎn)。 A. 分支結(jié)點(diǎn) B. 葉結(jié)點(diǎn) C. 根結(jié)點(diǎn) D. 空結(jié)點(diǎn)3. 在一棵二叉樹(shù)的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（ ）。 A. 2 B. 1 C. 0 D. -14. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于（ ）。 A. n B. n-1 C. n+1 D. 2*n5. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的第i層上（假定根結(jié)點(diǎn)為第0層，i大于等于0而小于等于樹(shù)的高度），最多具有（ ）個(gè)結(jié)點(diǎn)。 A. 2i B. 2i+1

2、 C. 2i-1 D. 2n6. 在一棵高度為h（假定根結(jié)點(diǎn)的層號(hào)為0）的完全二叉樹(shù)中，所含結(jié)點(diǎn)個(gè)數(shù)不小于（ ）。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h7. 在一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，該樹(shù)的高度為（ ）。假定空樹(shù)的高度為-1。 A. 5 B. 6 C. 7 D. 88. 在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，分支結(jié)點(diǎn)的最大編號(hào)為（ ）。假定樹(shù)根結(jié)點(diǎn)的編號(hào)為0。 A. (n-1)/2 B. n/2 C. n/2 D. n/2 -19. 在一棵完全二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左子女結(jié)點(diǎn)的編號(hào)為（ ）。假定根結(jié)點(diǎn)的編號(hào)為0 A. 2i B. 2i-1 C. 2

3、i+1 D. 2i+210. 在一棵完全二叉樹(shù)中，假定根結(jié)點(diǎn)的編號(hào)為0，則對(duì)于編號(hào)為i（i0）的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為（ ）。 A. (i+1)/2 B. (i-1)/2 C. i/2 D. i/2 -111. 在一棵樹(shù)的左子女-右兄弟表示法中，一個(gè)結(jié)點(diǎn)的右孩子是該結(jié)點(diǎn)的（ ）結(jié)點(diǎn)。 A. 兄弟 B. 子女 C. 祖先 D. 子孫12. 在一棵樹(shù)的靜態(tài)雙親表示中，每個(gè)存儲(chǔ)結(jié)點(diǎn)包含（ ）個(gè)域。 A. 1 B. 2 C. 3 D. 413. 已知一棵二叉樹(shù)的廣義表表示為a (b (c), d (e ( , g (h) ), f ) )，則該二叉樹(shù)的高度為（ ）。假定根結(jié)點(diǎn)的高度為0。 A. 3

4、B. 4 C. 5 D. 614. 已知一棵樹(shù)的邊集表示為 , , , , , , , ，則該樹(shù)的高度為（ ）。假定根結(jié)點(diǎn)的高度為0。 A. 2 B. 3 C. 4 D. 515. 利用n個(gè)值作為葉結(jié)點(diǎn)上的權(quán)值生成的霍夫曼樹(shù)中共包含有（ ）個(gè)結(jié)點(diǎn)。 A. n B. n+1 C. 2*n D. 2*n-116. 利用3, 6, 8, 12這四個(gè)值作為葉結(jié)點(diǎn)的權(quán)值生成一棵霍夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為（ ）。 A. 55 B. 29 C. 58 D. 3817. 一棵樹(shù)的廣義表表示為a (b, c (e, f (g) ), d)，當(dāng)用左子女-右兄弟鏈表表示時(shí)，右指針域非空的結(jié)點(diǎn)個(gè)數(shù)為（ ）。 A.

5、 1 B. 2 C. 3 D. 418. 向具有n個(gè)結(jié)點(diǎn)的堆中插入一個(gè)新元素的時(shí)間復(fù)雜度為（ ）。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n)參考答案：1. C 2. C 3. A4. C5. A6. D7. A8. D9. C10. B11. A12. B13. B14. B15. D16. A17. C18. C二、填空題1. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為_(kāi)。2. 在一棵樹(shù)中，_結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。3. 在一棵樹(shù)中，_結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)。4. 一棵樹(shù)的廣義表表示為a (b (c, d (e, f), g (h) ), i (j, k

6、 (x, y) ) )，結(jié)點(diǎn)k的所有祖先的結(jié)點(diǎn)數(shù)為_(kāi)個(gè)。5. 一棵樹(shù)的廣義表表示為a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，結(jié)點(diǎn)f的層數(shù)為_(kāi)。假定根結(jié)點(diǎn)的層數(shù)為0。6. 假定一棵三叉樹(shù)（即度為3的樹(shù)）的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小高度為_(kāi)。假定根結(jié)點(diǎn)的高度為0。7. 在一棵高度為3的四叉樹(shù)中，最多含有_結(jié)點(diǎn)。8. 在一棵三叉樹(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ù)有_個(gè)。9. 一棵高度為5的完全二叉樹(shù)中，最多包含有_個(gè)結(jié)點(diǎn)。假定根結(jié)點(diǎn)的高度為0。10. 假定一棵樹(shù)的廣義表表示為A (B (C,

7、D (E, F, G), H (I, J) ) )，則該樹(shù)的高度為_(kāi)。假定根結(jié)點(diǎn)的高度為0。11. 在一棵二叉樹(shù)中，假定度為2的結(jié)點(diǎn)個(gè)數(shù)為5個(gè)，度為1的結(jié)點(diǎn)個(gè)數(shù)為6個(gè)，則葉結(jié)點(diǎn)數(shù)為_(kāi)個(gè)。12. 假定一棵二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為18，則它的最小高度為_(kāi)。假定根結(jié)點(diǎn)的高度為0。13. 在一棵高度為h的理想平衡樹(shù)（即從0層到h-1層都是滿的，第h層的結(jié)點(diǎn)分布在該層各處）中，最少含有_個(gè)結(jié)點(diǎn)。假定根結(jié)點(diǎn)的高度為0。14. 在一棵高度為h的理想平衡樹(shù)（即從0層到h-1層都是滿的，第h層的結(jié)點(diǎn)分布在該層各處）中，最多含有_個(gè)結(jié)點(diǎn)。假定根結(jié)點(diǎn)的高度為0。15. 若將一棵樹(shù)A (B (C, D, E), F (G

8、(H), I) ) 按照左子女-右兄弟表示法轉(zhuǎn)換為二叉樹(shù)，該二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)個(gè)。16. 一棵樹(shù)按照左子女-右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)，則該二叉樹(shù)中_結(jié)點(diǎn)肯定沒(méi)有右子女。17. 在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i（0in-1），則它的左子女元素的下標(biāo)為_(kāi)。18. 在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i（0in-1），則它的右子女元素的下標(biāo)為_(kāi)。19. 在一個(gè)小根堆（即最小堆）中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的_。 20. 在一個(gè)大根堆（即最大堆）中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的_。21. 6個(gè)結(jié)點(diǎn)可構(gòu)造出_種不同形態(tài)的二叉樹(shù)。22. 設(shè)森林F中有4棵樹(shù)，第1、2、3、4棵樹(shù)

9、的結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3、n4，當(dāng)把森林F轉(zhuǎn)換成一棵二叉樹(shù)后，其根結(jié)點(diǎn)的右子樹(shù)中有_個(gè)結(jié)點(diǎn)。23. 設(shè)森林F中有4棵樹(shù)，第1、2、3、4棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3、n4，當(dāng)把森林F轉(zhuǎn)換成一棵二叉樹(shù)后，其根結(jié)點(diǎn)的左子樹(shù)中有_個(gè)結(jié)點(diǎn)。24. 將含有82個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始順序編號(hào)，根結(jié)點(diǎn)為第0號(hào)，其他結(jié)點(diǎn)自上向下，同一層自左向右連續(xù)編號(hào)。則第40號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為_(kāi)。參考答案：1. n-12. 樹(shù)根3. 葉子4. 25. 36. 47. 858. 69. 6310. 311. 612. 413. 2h14. 2h+1-115. 216. 根17. 2i+118.

10、2i+219. 最小值20. 最大值21. 13222. n2+n3+n423. n1-124. 19三、判斷題1. 當(dāng)向一個(gè)小根堆（最小堆）中插入一個(gè)具有最小值的元素時(shí)，該元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。2. 當(dāng)從一個(gè)小根堆（最小堆）中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。3. 二叉樹(shù)是一棵無(wú)序樹(shù)。4. 在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和后序遍歷，則具有相同的遍歷結(jié)果。5. 在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的遍歷結(jié)

11、果。6. 在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和中序遍歷，則具有相同的遍歷結(jié)果。7. 在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和按層遍歷，則具有相同的遍歷結(jié)果。8. 在樹(shù)的存儲(chǔ)中，若使每個(gè)結(jié)點(diǎn)帶有指向前驅(qū)結(jié)點(diǎn)的指針，將在算法中為尋找前驅(qū)結(jié)點(diǎn)帶來(lái)方便。9. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹(shù)，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O(n)。10. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹(shù)，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O(h)。11. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的任何二叉樹(shù)，進(jìn)行前序、中序或后序的任一種次序遍歷的空間復(fù)雜度為O(lo

12、g2n)。12. 在一棵具有n個(gè)結(jié)點(diǎn)的線索化二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的指針域可能指向子女結(jié)點(diǎn)，也可能作為線索，使之指向某一種遍歷次序的前驅(qū)或后繼結(jié)點(diǎn)，所有結(jié)點(diǎn)中作為線索使用的指針域共有n個(gè)。13. 線索化二叉樹(shù)中的每個(gè)結(jié)點(diǎn)通常包含有5個(gè)數(shù)據(jù)成員。14. 線索化二叉樹(shù)中的每個(gè)結(jié)點(diǎn)通常包含有3個(gè)數(shù)據(jù)成員。15. 對(duì)具有n個(gè)結(jié)點(diǎn)的堆進(jìn)行插入一個(gè)元素運(yùn)算的時(shí)間復(fù)雜度為O(n)。16. 從具有n個(gè)結(jié)點(diǎn)的堆中刪除一個(gè)元素，其時(shí)間復(fù)雜度為O(log2n)。17. 二叉樹(shù)是樹(shù)的特殊情形。18. 若有一個(gè)結(jié)點(diǎn)是二叉樹(shù)中某個(gè)子樹(shù)的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹(shù)的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。19.

13、若有一個(gè)結(jié)點(diǎn)是二叉樹(shù)中某個(gè)子樹(shù)的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹(shù)的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。20. 若有一個(gè)葉子結(jié)點(diǎn)是二叉樹(shù)中某個(gè)子樹(shù)的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹(shù)的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。21. 若有一個(gè)葉子結(jié)點(diǎn)是二叉樹(shù)中某個(gè)子樹(shù)的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)，則它一定是該子樹(shù)的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)。22. 若將一批雜亂無(wú)章的數(shù)據(jù)按堆結(jié)構(gòu)組織起來(lái), 則堆中各數(shù)據(jù)必然按自小到大的順序排列起來(lái)。參考答案：1. 是2. 是3. 否4. 否5. 是6. 否7. 是8. 是9. 是10. 否11. 否12. 否13. 是14. 否15. 否

14、16. 是17. 是18. 否19. 否20. 是21. 否22. 否四、運(yùn)算題1. 假定一棵二叉樹(shù)的廣義表表示為a (b (c), d (e, f) )，分別寫(xiě)出對(duì)它進(jìn)行前序、中序、后序、按層遍歷的結(jié)果。 前序：_ 中序：_ 后序：_ 按層：_2. 假定一棵二叉樹(shù)的廣義表表示為A (B ( , D (G) ), C (E, F) )，分別寫(xiě)出對(duì)它進(jìn)行前序、中序、后序、按層遍歷的結(jié)果。 前序：_ 中序：_ 后序：_ 按層：_3. 假定一棵普通樹(shù)的廣義表表示為a (b (e), c (f (h, i, j), g), d)，分別寫(xiě)出先根、后根、按層遍歷的結(jié)果。 先根：_ 后根：_ 按層：_4.

15、已知一棵二叉樹(shù)的前序和中序序列，求該二叉樹(shù)的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列：_5. 已知一棵二叉樹(shù)的中序和后序序列如下，求該二叉樹(shù)的前序序列。中序序列：c, b, d, e, a, g, i, h, j, f后序序列：c, e, d, b, i, j, h, g, f, a前序序列：_6. 已知一棵二叉樹(shù)的中序和后序序列如下，求該二叉樹(shù)的高度（假定空樹(shù)的高度為-1）和度為2、度為1的結(jié)點(diǎn)及葉結(jié)點(diǎn)個(gè)數(shù)。 中根序列：c, b, d, e, a, g, i, h, j, f 后根序

16、列：c, e, d, b, i, j, h, g, f, a高度：_ 度為2：_ 度為1：_ 葉子：_7. 已知一棵二叉樹(shù)的靜態(tài)數(shù)組表示（即順序存儲(chǔ)表示）如下，其中0表示空指針，請(qǐng)分別寫(xiě)出該二叉樹(shù)的前序、中序、后序遍歷的序列。 0 1 2 3 4 5 6 7 8 9 10 11 12 20 8 46 5 15 30 0 0 0 10 18 0 35 前序序列：_ 中序序列：_后序序列：_8. 已知一棵樹(shù)的靜態(tài)雙親表示如下，其中用 -1表示空指針，樹(shù)根結(jié)點(diǎn)存于0號(hào)單元，分別求出該樹(shù)的葉子結(jié)點(diǎn)數(shù)、單分支結(jié)點(diǎn)數(shù)、兩分支結(jié)點(diǎn)數(shù)和三分支結(jié)點(diǎn)數(shù)。序號(hào)： 0 1 2 3 4 5 6 7 8 9 10 dat

17、a: a b c d e f g h i j k parent: -1 0 1 1 3 0 5 6 6 0 9葉子結(jié)點(diǎn)數(shù)： _單分支結(jié)點(diǎn)數(shù)：_兩分支結(jié)點(diǎn)數(shù)：_三分支結(jié)點(diǎn)數(shù)：_9. 假定一個(gè)最大堆（大根堆）為（56, 38, 42, 30, 25, 40, 35, 20），則依次向它插入45和64兩個(gè)元素后得到的最大堆為：_10. 假定一個(gè)最小堆（小根堆）為（20, 35, 50, 57, 42, 70, 83, 65, 86），則依次從中刪除三個(gè)最小元素后得到的最小堆為：_11. 已知一組數(shù)為（56, 48, 25, 16, 74, 52, 83, 45），請(qǐng)把該組數(shù)調(diào)整為最小堆（即小根堆）。

18、最小堆：_12. 有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3, 7, 8, 2, 6, 10, 14，試以它們?yōu)槿~結(jié)點(diǎn)生成一棵霍夫曼樹(shù)，求出該樹(shù)的帶權(quán)路徑長(zhǎng)度、高度、度為2的結(jié)點(diǎn)個(gè)數(shù)。 帶權(quán)路徑長(zhǎng)度：_ 高度：_ 度為2的結(jié)點(diǎn)數(shù)：_13. 設(shè)二叉樹(shù)根結(jié)點(diǎn)所在層次為0，樹(shù)的高度h為距離根最遠(yuǎn)的葉結(jié)點(diǎn)所在層次，則：高度為h的完全二叉樹(shù)的不同二叉樹(shù)棵數(shù)：_高度為h的滿二叉樹(shù)的不同二叉樹(shù)棵數(shù)：_14. 確定滿足以下條件的二叉樹(shù)的可能形態(tài)：二叉樹(shù)的前序序列與中序序列相同：_二叉樹(shù)的中序序列與后序序列相同：_二叉樹(shù)的前序序列與后序序列相同：_參考答案：1. 前序：a, b, c, d, e, f /2分中序：c, b

19、, a, e, d, f /2分后序：c, b, e, f, d, a /1分按層：a, b, d, c, e, f /1分2. 前序：A, B, D, G, C, E, F/2分中序：B, G, D, A, E, C, F/2分后序：G, D, B, E, F, C, A/1分按層：A, B, C, D, E, F, G/1分3. 先根：a, b, e, c, f, h, i, j, g, d /2分 后根：e, b, h, i, j, f, g, c, d, a /2分按層：a, b, c, d, e, f, g, h, i, j /2分4. 后序序列：C, B, F, E, I, J,

20、H, G, D, A /6分5. 前序序列：a, b, c, d, e, f, g, h, i, j /6分6. 高度：5 /2分 度為2：3 /2分度為1：3 /1分葉子：4 /1分7. 前序序列：20, 8, 5, 15, 10, 18, 46, 30, 35 /2分中序序列：5, 8, 10, 15, 18, 20, 30, 35, 46 /2分后序序列：5, 10, 18, 15, 8, 35, 30, 46, 20 /2分8. 葉子結(jié)點(diǎn)數(shù)： 5 /2分單分支結(jié)點(diǎn)數(shù)：3 /2分兩分支結(jié)點(diǎn)數(shù)：2 /1分三分支結(jié)點(diǎn)數(shù)：1 /1分9. (64, 56, 42, 38, 45, 40, 35,

21、 20, 30, 25)/6分10. (50, 57, 70, 65, 86, 83) /6分11. (16, 45, 25, 48, 74, 52, 83, 56) /6分12. 帶權(quán)路徑長(zhǎng)度：131 /3分 高度：4 /2分度為2的結(jié)點(diǎn)數(shù)：6 /1分13. 高度為h的完全二叉樹(shù)的不同二叉樹(shù)棵數(shù)：2h；/3分高度為h的滿二叉樹(shù)的不同二叉樹(shù)棵數(shù)：1；/3分14. 二叉樹(shù)的前序序列與中序序列相同：所有結(jié)點(diǎn)的左子樹(shù)為空；/2分二叉樹(shù)的中序序列與后序序列相同：所有結(jié)點(diǎn)的右子樹(shù)為空；/2分二叉樹(shù)的前序序列與后序序列相同：只有一個(gè)結(jié)點(diǎn)，左右子樹(shù)為空；/2分五、算法分析題1. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用Bi

22、nTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函數(shù)的功能是返回二叉樹(shù)BT中值為x的結(jié)點(diǎn)所在的層號(hào)，請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)合適的內(nèi)容。int NodeLevel ( BinTreeNode * BT, ElemType& x ) if ( BT = NULL ) return 1; /空樹(shù)的層號(hào)為-1 else if ( BT-data = x ) return

23、0; /根結(jié)點(diǎn)的層號(hào)為0 else int c1 = NodeLevel ( BT-leftChild, x ); /向子樹(shù)中查找x結(jié)點(diǎn) if ( c1 = 0 ) _(1)_; int c2 =_(2)_; _(3)_; else return -1; /在樹(shù)中不存在x結(jié)點(diǎn)返回-1(1) _(2) _(3) _2. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指

24、向左、右子女結(jié)點(diǎn)的指針域。下面函數(shù)的功能是從二叉樹(shù)BT中查找值為x的結(jié)點(diǎn)，返回指向其父結(jié)點(diǎn)的指針。若該結(jié)點(diǎn)不存在或?yàn)闃?shù)根結(jié)點(diǎn)則返回空。算法中參數(shù)PT的初值為NULL。請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)合適的內(nèi)容。BinTreeNode* ParentPtr ( BinTreeNode* BT, BinTreeNode* PT, ElemType& x ) if ( BT = NULL ) return NULL; else if ( BT-data = x ) return PT; else if ( PT = ParentPtr ( BT-leftChild, BT, x ) ) _(1)_; _(2)

25、_; else _(3)_; (1) _(2) _(3) _3. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹(shù)的樹(shù)根結(jié)點(diǎn)。BinTreeNode* BinTreeSwopX ( BinTreeNode * BT ) if ( BT = NULL ) return NULL;e

26、lse BinTreeNode* pt = new BinTreeNode;pt-data = BT-data;pt-rightChild = BinTreeSwopX ( BT-leftChild );pt-lefthild = BinTreeSwopX ( BT-rightChild ); return pt; 算法功能：_4. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用ThreeTreeNode表示，被定義為: struct ThreeTreeNode datatype data; ThreeTreeNode *leftChild, *rightChild, *parent; ; 其中data為結(jié)點(diǎn)值域，

27、leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域，parent為指向父結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)T指向一棵二叉樹(shù)的樹(shù)根結(jié)點(diǎn)，x保存一個(gè)結(jié)點(diǎn)的值。ThreeTreeNode* PN ( ThreeTreeNode * T, datatype& x ) if ( T = NULL ) return NULL; else ThreeTreeNode* mt;if ( T-data = x ) return T-parent;else if ( mt = PN ( T-leftChild, x ) ) return mt;else if ( mt

28、 = PN ( T-rightChild, x ) ) return mt;return NULL; 算法功能：_5. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹(shù)的根結(jié)點(diǎn)。void BTC ( BinTreeNode* BT ) if ( BT != NULL ) if (

29、 BT-leftChild != NULL & BT-rightChild != NULL ) if ( BT-leftChild-data BT-rightChild-data ) BinTreeNode* t = BT-leftChild; BT-leftChild = BT-rightchild; BT-rightChild = t; BTC ( BT-leftChild );BTC ( BT-rightChild ); 算法功能：_6. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode char data; BinTreeNode *

30、leftChild, *rightChild;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定指針bt指向一棵二叉樹(shù)，該二叉樹(shù)的廣義表表示為a (b (a, d (f) ), c (e ( , a (k) ), b) )，整數(shù)變量C的值為0，若：(1) 執(zhí)行BTC1( bt, a, C ) 調(diào)用后，C的值為_(kāi);(2) 執(zhí)行BTC1( bt, b, C ) 調(diào)用后，C的值為_(kāi);(3) 執(zhí)行BTC1( bt, c, C) 調(diào)用后，C的值為_(kāi);(4) 執(zhí)行BTC1( bt, g, C) 調(diào)用后，C的值為_(kāi);void BTC1( BinTreeNo

31、de* BT, char x, int& k ) if ( BT != NULL ) if ( BT-data = x ) k+;BTC1( BT-leftChild, x, k );BTC1( BT-rightChild, x, k );7. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode * leftChild, * rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函數(shù)的功能是從二叉樹(shù)BT中查找值為x的結(jié)

32、點(diǎn)，若查找成功則返回結(jié)點(diǎn)地址，否則返回空。請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)合適內(nèi)容。BinTreeNode* BTF ( BinTreeNode* BT, ElemType& x ) if ( BT = NULL ) _(1)_; else if ( BT-data = x ) _(2)_; else BinTreeNode* t;If ( t = BTF ( BT-leftChild, x ) ) _(3)_; _(4)_; else return NULL;(1) _(2) _(3) _(4) _8. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNod

33、e ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹(shù)的根結(jié)點(diǎn)。int DST ( BinTreeNode*& BT, ElemType x ) if ( BT = NULL ) return 0;else if ( BT-data = x ) BT = NULL; return 1; else if ( DST ( BT-leftChild, x ) ) return 1;if

34、( DST ( BT-rightChild, x ) ) return 1;else return 0; 算法功能：_9. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode char data; BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定一棵二叉樹(shù)采用鏈接存儲(chǔ)，它的廣義表表示為r (b (, d (f, g) ), t (e) )，rt, bt, dt和et指針變量分別保存指向r, b, d和e結(jié)點(diǎn)的指針值，

35、則：(1)執(zhí)行BTM (rt) 調(diào)用后，得到的函數(shù)值為_(kāi);(2)執(zhí)行BTM (bt) 調(diào)用后，得到的函數(shù)值為_(kāi);(3)執(zhí)行BTM (dt) 調(diào)用后，得到的函數(shù)值為_(kāi);(4)執(zhí)行BTM (et) 調(diào)用后，得到的函數(shù)值為_(kāi);char BTM(BinTreeNode* BT) static char max = 0;if ( BT != NULL ) char k1, k2;k1 = BTM ( BT-leftChild );k2 = BTM ( BT-rightChild );if ( k1 max ) max = k1;else if ( k2 max ) max = k2;else if (

36、BT-data max ) max = BT-data;return max;10. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹(shù)的根結(jié)點(diǎn)。void preserve ( BinTreeNode* BT, ElemType a , int n ) static int i =

37、 0;if ( BT != NULL ) preserve ( BT-leftChild, a, n );ai+ = BT-data;preserve ( BT-rightChild, a, n ); 算法功能：_11. 假定在a10數(shù)組中數(shù)據(jù)為 16, 42, 35, 73, 54, 38, 80 ，n為整型變量，其值為7，則執(zhí)行IH ( a, n, 25 ) 調(diào)用下面算法后數(shù)組a中的數(shù)據(jù)變?yōu)椋篲void IH ( int HBT , int& n, int item ) HBTn = item;n+; int x = item; int i = n-1; while ( i != 0 )

38、int j = (i-1)/2; if ( x = HBTj ) break; HBTi = HBTj; i = j; HBTi = x;12. 假定在a10數(shù)組中數(shù)據(jù)為 16, 35, 42, 73, 54, 68, 80, 26，n為整型變量，其值為8，則執(zhí)行DH ( a, n ) 調(diào)用下面算法后數(shù)組a中的數(shù)據(jù)變?yōu)椋篲int DH ( int HBT , int& n ) if ( n = 0 ) cerr null! endl; exit (1); int temp = HBT0;n-;int x = HBTn;int i = 0, j = 2*i+1;while ( j = n-1 )

39、 if ( j HBTj+1 ) j+;if ( x rightChild, X )/3分(3) if (c2 = 0 ) return c2+1 /3分2. (1) return PT /2分(2) if ( PT = ParentPtr ( BT-rightChild, BT, X ) ) return PT /4分(3) return NULL或return 0 /2分3. 算法功能：生成一棵新二叉樹(shù)并返回樹(shù)根指針，該二叉樹(shù)是已知二叉樹(shù)BT中所有結(jié)點(diǎn)的左、右子樹(shù)交換的結(jié)果。4. 算法功能：從樹(shù)根指針為T的二叉樹(shù)中查找值為X的結(jié)點(diǎn)，返回指向父結(jié)點(diǎn)的指針。5. 算法功能：對(duì)二叉樹(shù)BT進(jìn)行處理

40、，當(dāng)BT中每個(gè)結(jié)點(diǎn)的左孩子的值大于右孩子的值則交換左右子樹(shù)。6. (1) 3 /2分(2) 2 /2分(3) 1 /2分(4) 0 /2分7. (1) return NULL /2分(2) return BT /2分(3) return t /2分(4) if ( t = BTF ( BT-rightChild, x ) ) return t /2分8. 算法功能：從一棵二叉樹(shù)中刪除根結(jié)點(diǎn)值為x的子樹(shù)，若刪除成功則返回1，否則返回0。9. (1) t /2分(2) g /2分(3) g /2分(4) e/2分10. 算法功能：對(duì)具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)進(jìn)行中根遍歷，把得到的結(jié)點(diǎn)值序列保存到數(shù)組a中

41、。11. 16, 25, 35, 42, 54, 38, 80, 73 /有一處錯(cuò)則不得分12. 26, 35, 42, 73, 54, 68, 80 /有一處錯(cuò)則不得分六、算法設(shè)計(jì)題1. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫(xiě)出求一棵二叉樹(shù)高度的算法，該高度由函數(shù)返回。假定根結(jié)點(diǎn)的層次為0，參數(shù)BT初始指向這棵二叉樹(shù)

42、的根結(jié)點(diǎn)。 int BTreeHeight ( BinTreeNode* BT );2. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫(xiě)出求一棵二叉樹(shù)中結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹(shù)的根結(jié)點(diǎn)。 int BTreeCount ( BinTreeNode* BT );3. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用B

43、inTreeNode表示，被定義為: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫(xiě)出求一棵二叉樹(shù)中葉子結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹(shù)的根結(jié)點(diǎn)。 int BTreeLeafCount ( BinTreeNode* BT );4. 已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為: struct BinTreeNode char data;BinTr