數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案

1、第六章樹和二叉樹(下載后用閱讀版式視圖或web版式可以看清)、選擇題1有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為()。A.向量 B.樹 C圖 D.二叉樹2. 樹最合適用來(lái)表示()。A.有序數(shù)據(jù)元素B元素之間具有分支層次關(guān)系的數(shù)據(jù)C無(wú)序數(shù)據(jù)元素 D.元素之間無(wú)聯(lián)系的數(shù)據(jù)3. 樹B的層號(hào)表示為la, 2b, 3d, 3e, 2c,對(duì)應(yīng)于下面選擇的()。A. la (2b (3d,3e),2c) B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4高度為h的完全二叉樹至少有()個(gè)結(jié)點(diǎn)，至多有()個(gè)結(jié)點(diǎn)。A. 2h_

2、l B.h C. 2h-1 D. 2h5. 在一棵完全二叉樹中，若編號(hào)為f的結(jié)點(diǎn)存在右孩子，則右子結(jié)點(diǎn)的編號(hào)為()。A. 2i B. 2i-l C. 2i+l D. 2i+26. 一棵二叉樹的廣義表表示為a(b(c), d(e(, g(h), f)，則該二叉樹的高度為()。A.3B.4C.5D.67. 深度為5的二叉樹至多有()個(gè)結(jié)點(diǎn)。A. 31B. 32C. 16D. 108. 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為()個(gè)。A. 15B. 16C. 17D. 479.題圖6-1中，()10. 在題圖6-2所示的二叉樹中:扈期自JA結(jié)點(diǎn)是A.葉結(jié)點(diǎn)B根結(jié)點(diǎn)

3、但不是分支結(jié)點(diǎn)C根結(jié)點(diǎn)也是分支結(jié)點(diǎn)D.分支結(jié)點(diǎn)但不是根結(jié)點(diǎn)(2) J結(jié)點(diǎn)是A.葉結(jié)點(diǎn)B .根結(jié)點(diǎn)但不是分支結(jié)點(diǎn)C根結(jié)點(diǎn)也是分支結(jié)點(diǎn)D.分支結(jié)點(diǎn)但不是根結(jié)點(diǎn)(3) F結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是A.E B.DC.空 D(4) F結(jié)點(diǎn)的雙親結(jié)點(diǎn)是A. AB.BC. C D. D(5) 樹的深度為A. 1B.2C.3 D.4(6) B結(jié)點(diǎn)的深度為A. 1B.2C.3D.4(7) A結(jié)點(diǎn)所在的層是A. 1B.2C.3D.411在一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹中，該樹的深度為()。A. 5 B. 6 C. 7 D. 812. 一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有 ()個(gè)結(jié)點(diǎn)。A. 247 B. 248 C. 2

4、49 D. 25013用順序存儲(chǔ)的方法將完全二叉樹中所有結(jié)點(diǎn)逐層存放在數(shù)組R1 , n中，結(jié)點(diǎn)Ri若有左子樹，則左子樹是結(jié)點(diǎn)()。A. R2i+I B. R2iC.Ri/2 D. R2i-114在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊 ()。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)15. 一棵度為m的樹中，有ni個(gè)度為1的結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn),，有nm個(gè)度為m的結(jié)點(diǎn)，則該樹的葉結(jié)點(diǎn)數(shù)為()。A. m+n2+.+nmB. (m-l) nm+.+n2+1C. n什n2+1D. nrn216. 已知某二叉樹的中序遍歷序列是de

5、bac,后序遍歷序列是 dabec,它的前序遍歷序列是（）。A. acbed B. decab C. deabc D. cedba17. 在一棵二叉樹的二叉鏈表中，空指針域等于所有非空指針域數(shù)加（）。A.2B.1C.0D.-118. 線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯 B .邏輯和存儲(chǔ) C.物理 D.線性19. 由權(quán)值分別是8, 7, 2, 5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）。A. 23 B. 37 C. 46 D. 4320. 設(shè)T是哈夫曼樹，具有 5個(gè)葉結(jié)點(diǎn)，樹T的高度最高可以是（）。A.2 B. 3C.4D.5、填空題1. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)

6、之和為 。2. 在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)前驅(qū)結(jié)點(diǎn)：葉子結(jié)點(diǎn)沒(méi)有 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)可以有 后繼結(jié)點(diǎn)。3. 有一棵樹如題圖6-3所示，回答下面的問(wèn)題。這棵樹的根點(diǎn)是 ;葉子結(jié)點(diǎn)是 ;結(jié)點(diǎn)k3的度是;結(jié)點(diǎn)k3的子女是;結(jié)點(diǎn)k3的父結(jié)點(diǎn)是 ;這棵樹的度為 ;這棵樹的深度是，單分支結(jié)點(diǎn)的個(gè)數(shù)為4. 假定一棵樹的廣義表表示為A（B（E） , C（F（H , I, J, G）, D），則該樹的度為，樹的深度為，終端結(jié)點(diǎn)的個(gè)數(shù)為，雙分支結(jié)點(diǎn)的個(gè)數(shù)為 , 3分支結(jié)點(diǎn)的個(gè)數(shù)為 , C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 ，其孩子結(jié)點(diǎn)為 。5. 一棵深度為h的滿k叉樹有如下性質(zhì)：第 h層上的結(jié)點(diǎn)都是

7、葉子結(jié)點(diǎn)，其余各層上的每個(gè)結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序（同層自左至右）從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，則：（1）第i層結(jié)點(diǎn)數(shù)目是 。（2）編號(hào)為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號(hào)是_。（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是_。編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是 _ :其右兄弟的編號(hào)是_。6. 前序遍歷一棵樹相當(dāng)于 樹中對(duì)應(yīng)的二叉樹，后序遍歷一棵樹則相當(dāng)于樹中對(duì)應(yīng)的二叉樹。7. 二叉樹的遍歷分為 ，樹與森林的遍歷包括 。&一棵二叉樹的第i（i>=1）層最多有個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有 個(gè)葉子和 個(gè)非終端結(jié)點(diǎn)。9在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為

8、5個(gè)，單分支結(jié)點(diǎn)數(shù)為 6個(gè)，則葉子結(jié)點(diǎn)為 個(gè)。10 .在一棵二叉樹中，第五層上的結(jié)點(diǎn)數(shù)最多為 。個(gè)空閑著?？脴?。11. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為個(gè)，其中 個(gè)用于鏈接孩子結(jié)點(diǎn)，.12. 前序遍歷的順序是 ABDGEHICFJ，則二叉樹的根是。13. 從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是14. 結(jié)點(diǎn)最少的樹為 ，結(jié)點(diǎn)最少的二叉樹為 。15. 一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI，則在前序遍歷中結(jié)點(diǎn)E的直接前驅(qū)為 ，后序遍歷中結(jié)點(diǎn) B的直接后繼是16. 某二叉樹的中序遍歷序列為 ABCDEFG，后序

9、序列為 BDCAFGE，則該二叉樹結(jié)點(diǎn)的前序序列為 ，該二叉樹對(duì)應(yīng)的森林包括 _17. 用一維數(shù)組存放的一棵完全二叉樹如題圖6-4所示。| L :1 S i57電9 U)l2I a ir i)E t；G b I JK t題圖6-4則后序遍歷該二叉樹時(shí)結(jié)點(diǎn)訪問(wèn)的順序?yàn)?。18. 由n個(gè)權(quán)值構(gòu)成的哈夫曼樹共有 個(gè)結(jié)點(diǎn)。19. 由帶權(quán)為3, 9, 6, 2, 5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng)度為 。20. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則 B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有 個(gè)。21. 二叉樹的存儲(chǔ)結(jié)構(gòu)分為，樹的存儲(chǔ)結(jié)構(gòu)分為。三、判斷題1. 樹中任意結(jié)點(diǎn)的子樹不

10、必是有序的。（）2. 樹可以看成特殊的無(wú)向圖。（）3. 可以使用雙鏈表表示樹型結(jié)構(gòu)。（）4. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（）5. 完全二叉樹的某結(jié)點(diǎn)若無(wú)左孩子，則必是葉結(jié)點(diǎn)。（）6. 在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹。（）7. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹是一種特殊的樹。（）&二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子樹結(jié)點(diǎn)的前面。（）9. 二叉樹的前序和后序遍歷序列能惟一確定這棵二叉樹。（）10. 中序線索二叉樹中，右線索若不為空，則一定指向其父結(jié)點(diǎn)。四、算法和操作題1 假定一棵二叉樹廣義表表示為a(b(c)，d(e, D)，

11、分別寫出對(duì)它進(jìn)行前序、中序、后序遍歷的結(jié)果。前序：中序：后序：2 已知一棵二叉樹的中序和后序序列，求該二叉樹的高度和雙支、單支及葉子結(jié)點(diǎn)數(shù)。中根序列:c, b,d, e, a, g, i,h,j , f后根序列:c, e,d, b,i, j, h, g, fa高度：雙支：?jiǎn)沃?葉子：3 .已知一棵樹邊的集合為 <l< SPAN, M> , <I< SPAN, N> , <E< SPAN, I> , <B< SPAN, E>, <B< SPAN, D>, <A< SPAN, B>, <

12、;G< S PAN> , J>, <G< SPAN> , K> , <C< SPAN> , G>, <C< SPAN> , F>, <H< SPAN> , L> , <C< SPAN> , H> , <A< SPAN> , C>)，請(qǐng)畫出這棵樹，并回答 下列問(wèn)題：(1)哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪個(gè)是結(jié)點(diǎn)G的雙親？哪些是結(jié)點(diǎn)G的祖先？哪些是結(jié)點(diǎn)G的孩子？(6)哪些是結(jié)點(diǎn)E的子孫？哪些是結(jié)點(diǎn)E的兄弟？哪些是結(jié)點(diǎn) F的兄弟?(8) 結(jié)

13、點(diǎn)B和N的層次號(hào)分別是什么？(9) 樹的深度是多少？(10) 以結(jié)點(diǎn)C為根的子樹的深度是多少？4 將算術(shù)表達(dá)式(a+b)+c*(d+e)+f*(g+h)轉(zhuǎn)化為二叉樹。5. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組BT中，如題表6-1所示。畫出該二叉樹的鏈接表示形式。數(shù)組BT的存放形式是相對(duì)于滿二叉樹中編號(hào)為數(shù)組下標(biāo)值的結(jié)點(diǎn)值。若該結(jié)點(diǎn)不存在，則取0值。6-11L23456781?10l1213141516)719cafd8cJIh,b6 假設(shè)前序遍歷某棵樹的結(jié)點(diǎn)次序?yàn)镾ACEFBDGHIJK ;后序遍歷該樹的結(jié)點(diǎn)次序?yàn)镃FEABHGIKJDS，請(qǐng)畫出這棵樹。7 .已知一棵樹如題圖 6-

14、5所示，將其轉(zhuǎn)換為其孩子兄弟表示的二叉樹。并畫出該二叉樹的后序線索二叉樹。&試找出分別滿足下列條件的所有二叉樹：(1)前序遍歷序列和中序遍歷序列相同。 中序遍歷序列和后序遍歷序列相同。(3)前序遍歷序列和后序遍歷序列相同。9 .已知信息為“ ABCD BCD CB DB ACB ”，請(qǐng)按此信息構(gòu)造哈夫曼樹，求出每一字符的最優(yōu)編碼。10.己知中序線索二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，鏈結(jié)點(diǎn)的構(gòu)造為：| Ichilddakrchiki其中若Itag為0,則Ichild指向結(jié)點(diǎn)的前驅(qū)，否則Ichild指向左孩子結(jié)點(diǎn)；若rtag為0,則rchild指向結(jié)點(diǎn)的后繼，否則 rchild指向右孩子結(jié)點(diǎn)。下

15、面的算 法返回x所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的位置。若該算法有錯(cuò)，則請(qǐng)改正錯(cuò)誤；若無(wú)錯(cuò)，請(qǐng)寫“正確”二字。BiTree INSUCC （BiTree x） s=X->rchild;if （ s->rtag） while （ s->ltag） s=s->rchild;return s； )五、算法設(shè)計(jì)題1編寫對(duì)二叉樹進(jìn)行中序遍歷的非遞歸算法，并對(duì)算法執(zhí)行題圖6-6所示的二叉樹的情況進(jìn)行跟蹤(即給出各階段棧的變化及輸出的結(jié)點(diǎn)序列)。棧已經(jīng)定義：InitStack(S)(初始化)、Empty(S)(判棧空)、2假設(shè)在表示一棵二叉樹的二叉鏈表上增加兩個(gè)域：雙親域用于指示其雙親結(jié)點(diǎn)，標(biāo)

16、志域flag (可取 0.2)的值，用以區(qū)分在遍歷過(guò)程中到達(dá)該結(jié)點(diǎn)時(shí)繼續(xù)向右或向左或訪問(wèn)該結(jié)點(diǎn)。試以此存儲(chǔ)結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞歸形式的算法。3一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹，以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)對(duì)該完全二叉樹進(jìn)行前序遍歷的算法。4設(shè)中序線索樹的結(jié)點(diǎn)由 5 個(gè)域組成。Info ：給出結(jié)點(diǎn)的數(shù)據(jù)域。LT: 標(biāo)志域，為 0 或 1。LL ：當(dāng) LT 為 1 時(shí)，給出該結(jié)點(diǎn)的左孩子的地址。當(dāng) LT 為 0 時(shí)，給出按中序遍歷的前驅(qū)結(jié)點(diǎn)地址。RT:標(biāo)志域，為0或1。RL :當(dāng) RT為1時(shí)，給出該結(jié)點(diǎn)的右孩子的地址。當(dāng) RT 為 O 時(shí)，給出按中序遍歷的后繼結(jié)點(diǎn)地址。請(qǐng)編寫 程序

17、，在具有上述結(jié)點(diǎn)結(jié)構(gòu)的中序線索二叉樹上，求某一結(jié)點(diǎn)p按后序遍歷次序的后繼結(jié)點(diǎn)的地址q，設(shè)該中序線索二叉樹的根結(jié)點(diǎn)地址為r。另外，請(qǐng)注意必須滿足:(1) 額外空間的使用只能為 0(1)。(2) 程序?yàn)榉沁f歸形式。 5假設(shè)二叉樹采用鏈接方法存儲(chǔ)，編寫一個(gè)函數(shù)按凹入表表示法打印出該二叉樹。 6給出中序線索樹的結(jié)點(diǎn)結(jié)構(gòu)，設(shè)計(jì)算法在不使用棧和遞歸的情況下前序遍歷一棵中序線索樹，并分析它的時(shí)間復(fù)雜度。 7以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫出交換各結(jié)點(diǎn)左右子樹的算法。8假設(shè)二叉樹采用鏈接方法存儲(chǔ)，編寫一個(gè)函數(shù)按凹入表表示法打印出該二叉樹。第六章 樹和二叉樹 第 6 章樹和二叉樹 、選擇題(參考答案)1B2B3C4A，

18、C5C6C7A8B9A，B10. (1)C(2)A(3)C(4)A(5)C(6)A(7)C11B12.A13B14A15 B16D17A18C19D20 D二、填空題(參考答案)1 樹的總結(jié)點(diǎn)數(shù) -1 。2 前驅(qū)：1,后繼，任意多個(gè)。3. k i, k 2, k 4, k 5, k 7,2,k 5, k 6, k 1,3,4 。4.3 , 4, 6, 1, 1 , 2, A, F, Gn-2卄5.(1) k i-1 , (2)_ 孔, n-lx k+n +1,(4)i 工 nk+l(n=0,l,2, , ),n+1.6 .前序遍歷，中序遍歷。7 .前序，中序，后序，前序，后序。8. 2i-1,

19、2/n , |l2/n .9.6 個(gè)。10. 16011.2n , n-l , n+l 。12 . A13. 樹可采用二叉樹的存儲(chǔ)結(jié)構(gòu)并可利用二叉樹的已有算法解決樹的有關(guān)問(wèn)題。14. 只有1個(gè)結(jié)點(diǎn)的樹，空樹。15.I ，F(xiàn)。16. 前序遍歷序列為：EACBDGF森林包括1棵樹。17. HIDJKEBLFGCAO18. 2n-l 。19. 56020 . n+l。21.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，雙親鏈表表示法，孩子鏈表表示法，孩子兄弟鏈表表示法三、判斷題1. V 2. V 3. V 4. X 5. V 6. X 7. x 8. V 9. x 10. x四、算法和操作題1 假設(shè)一棵二叉樹廣義表表示為a(

20、b(c) , d(e , D),分別寫出對(duì)它進(jìn)行前序、中序、后序遍歷的結(jié)果。【解答】前序：a, b, c, d, e, D中序：c, b, a, e, d, D后序：c, b, e, D, d, a2 已知一棵二叉樹的中序和后序序列，求該二叉樹的高度和雙支、單支及葉子結(jié)點(diǎn)數(shù)?！窘獯稹恐行蛐蛄校篶, b, d, e, a, g, i , h , j , f后序序列：c , e , d , b , i , j , h , g , f, a由中序和后序(前序)遍歷序列可惟一確定一棵二叉樹，基本思想是后序(前序)定根，中序分左右。由后序序列可知該樹的根結(jié)點(diǎn)為a,由中序遍歷序列可知該樹的左子樹為c ,

21、b , d , e,右子樹為g , i , h , j , f);再由后序序列可知該樹的左子樹的根結(jié)點(diǎn)為b,右子樹的根結(jié)點(diǎn)為 f 再由中序遍歷序列可知b結(jié)點(diǎn)的左子樹為c,右子樹為d,e);再由后序遍歷序列可知右子樹d , e的根結(jié)點(diǎn)為d,再由中序遍歷序列可知d的左子樹為空，右子樹為e。對(duì)以f為根結(jié)點(diǎn)的子樹可做類似的分析。最后得到由中序和后序序列決定的二叉樹為：a(b(c , d( , e) , f(g( , h(i , j),由此可知該樹：高度：5雙分支：3單分支：3葉結(jié)點(diǎn)：4。3 .已知一棵樹邊的集合為<I ,M>,<I ,N>,<E , I> ,<

22、B,E> ,<B,D>,<A,B>,<GJ>,<G K> , <C,G>,<C,F>,<H,L> ,<C,H>,<A,C>，請(qǐng)畫出這棵樹,并回答問(wèn)題？【解答】根據(jù)邊集畫出的樹如下所示：(3) 結(jié)點(diǎn)G的雙親是(4) 結(jié)點(diǎn)G的祖先是(5) 結(jié)點(diǎn)G的孩子是(6) 結(jié)點(diǎn)E的子孫是(7) 結(jié)點(diǎn)E的兄弟是(1)根結(jié)點(diǎn)是：A。葉子結(jié)點(diǎn)是：D, M N F, J, K, L。CoA, CoJ, KoI , M, NoD;結(jié)點(diǎn)F的兄弟是：G, Ho(8) 結(jié)點(diǎn)B和N的層次號(hào)分別是：2 , 5o(9)

23、 樹的深度是：5 o(10) 以結(jié)點(diǎn)C為根的子樹的深度是：3o4 將算術(shù)表達(dá)式(a+b)+c*(d+e)+f*(g+h)轉(zhuǎn)化為二叉樹?！窘獯稹哭D(zhuǎn)化成如下二叉樹:BT的存放形式是相對(duì)于滿二叉樹中編號(hào)5 -棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組BT中，如題表6-1所示。畫出該二叉樹的鏈接表示形式。數(shù)組為數(shù)組下標(biāo)值的結(jié)點(diǎn)值。若該結(jié)點(diǎn)不存在，則取0值。題表6-1l1II11ItpItjLlI1 <ftf1h【解答】二叉樹的鏈?zhǔn)奖硎緸?6 若前序遍歷某樹的結(jié)點(diǎn)次序：SACEFBDGHIJK后序遍歷的結(jié)點(diǎn)次序?yàn)?CFEABHGIKJDS畫出這棵樹?！窘獯稹慨嫵鰳淙缦?將原教材題圖6-5轉(zhuǎn)換為

24、孩子兄弟所表示的二叉樹及該二叉樹的后序線索二叉樹如下:8 .9 .是：2, 5,（右單支樹）。（左單支樹）?？諛錆M足所有條件。非空樹如下： 前序和中序遍歷序列相同的二叉樹是沒(méi)有左子樹的二叉樹 中序和后序遍歷序列相同的二叉樹是沒(méi)有右子樹的二叉樹 前序和后序遍歷序列相同的二叉樹是只有根的二叉樹。在信息“ ABCD BCD CB DB ACB中A, B, C, D四個(gè)字符出現(xiàn)的頻率依次 4, 3。在哈夫曼樹中每個(gè)字符的最優(yōu)編碼：可得編碼為：A-110 B-O C-10 D-II1信息編碼為：110010111 0101111001110 11010010.錯(cuò)誤。修改如下：BiTree INSUCC

25、(BiTree x) S=X->rchild;if(s_>rtag)while (s->ltag )s=s->lchild;return S;五、算法設(shè)計(jì)題1 編寫對(duì)二叉樹進(jìn)行中序遍歷的非遞歸算法，并對(duì)算法執(zhí)行原教材題圖6-6所示的二叉樹的情況進(jìn)行跟蹤(即給出各階段棧的變化及輸出的結(jié)點(diǎn)序列)?！窘獯稹恐行虮闅v的非遞歸算法如下：void In orderTraverse (BTree T) In itStack (S);P=T;while (p&& 1Empty (S) if (P) Push(S,p);p=p->lchild;)else pop (

26、S,p);prin tf( "ooC", p->data);p=p->rchild); 對(duì)于給定的二叉樹，算法執(zhí)行情況如下：A入棧，B入棧，D入棧，D出棧，訪問(wèn)D, B出棧，訪問(wèn)B，A出棧，訪問(wèn)A，C入棧，E入棧，E出棧，訪問(wèn)E，G入棧，G出棧，訪問(wèn)G, C出棧，訪問(wèn)C, F入棧，F(xiàn)出棧，訪問(wèn)F，棧和指針p均空，結(jié)束。最后的遍歷序列是：DBAGECF2 假設(shè)在表示一棵二叉樹的二叉鏈表上增加兩個(gè)域：雙親域用于指示其雙親結(jié)點(diǎn)，標(biāo)志域flag (可取0，,，2)的值，用以區(qū)分在遍歷過(guò)程中到達(dá)該結(jié)點(diǎn)時(shí)繼續(xù)向右或向左或訪問(wèn)該結(jié)點(diǎn)。試以此存儲(chǔ)結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞推

27、形式的算法?！窘獯稹恳鉀Q這一問(wèn)題必須區(qū)分結(jié)點(diǎn)在訪問(wèn)過(guò)程中的狀態(tài)，這可通過(guò)結(jié)點(diǎn)的標(biāo)志域來(lái)處理。對(duì)一個(gè)結(jié)點(diǎn)來(lái)說(shuō)當(dāng)前的結(jié)點(diǎn)可能由：(1)其雙親結(jié)點(diǎn)轉(zhuǎn)換;(2)其左子樹遍歷結(jié)束轉(zhuǎn)換；(3)其右予樹遍歷結(jié)束轉(zhuǎn)換。所以，算法主要執(zhí)行按這三種狀態(tài)進(jìn)行處理或處理當(dāng)前結(jié)點(diǎn)或 轉(zhuǎn)換結(jié)點(diǎn)的狀態(tài)，從而算法可描述為：void postorder (BTree T)/ 后序遍歷二叉樹/Btree類型的結(jié)點(diǎn)含 4個(gè)域：flag ，pare nt ， lchild ， rchild; flag 初值為0，指針指向根結(jié)點(diǎn) BiTree p=T;while (p)switch (p->flag) case O:p->

28、;flag=l; if (p->lchild) p=p->lchild;break;case l: p->flag=2; if (p->rchild) p=p->rchild;break;case 2: p->flag=0; printf (p->data); p=p->parent ;3. 一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹，以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)對(duì)該完全二 叉樹進(jìn)行前序遍歷的算法?！窘獯稹吭O(shè)完全二叉樹的結(jié)點(diǎn)以層次為序，按從上至下，由左至右的順序編號(hào)，存放在一維數(shù)組R1 , , n中。對(duì)于編號(hào)為t的結(jié)點(diǎn)，若存在子結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)一定

29、是 2*t，右孩子結(jié)點(diǎn)是2*t+l ,由此可得對(duì)完全二叉樹進(jìn)行前序遍歷的遞歸算法。 void preorder (int R， int n ， int t)/ 前序遍歷二叉樹 R printf (” %Cn"， Rt );/ 輸出當(dāng)前結(jié)點(diǎn)值if(t*2<=n)preorder(R ， n， t*2);/ 遞歸前序遍歷左子結(jié)點(diǎn)if(t*2+1<=n)preorder(R ， n， t*2+1);/ 遞歸前序遍歷右子結(jié)點(diǎn)4 在不使用棧和遞歸的條件下，后序序列遍歷中序線索二叉樹，需要知道任意結(jié)點(diǎn)的后序直接后繼。中序線索樹所能提供的是當(dāng)前訪問(wèn)結(jié)點(diǎn)的祖先(雙親)信 息，利用雙親信息

30、，就可以對(duì)中序線索樹進(jìn)行后序遍歷。中序線索樹有如下性質(zhì)： 若x是pare nt的左孩子，則pare nt是x的最右子孫的右線索。 若x是pare nt的右孩子，則pare nt是x的最左子孫的左線索。因此設(shè)計(jì)兩個(gè)函數(shù)求給定結(jié)點(diǎn)的最左子孫的左線索和最右子孫的右線索; 這兩個(gè)線索均是 T 的祖先。具體實(shí)現(xiàn)如下：typedef enumLink, ThreadPointer Tag;/Link=0 ：指針 ;Thread=l ：線索typedef struct BiThrNode/ 中序線索樹結(jié)點(diǎn)結(jié)構(gòu)ElemrType dataStructBiThrHodelchild, rchild;Pointe

31、rTag ltag, Rtag; BiThrNode,*BiThrNode;typedef enum lEFT, RIGHT) TagType;BiTHrNode*LeftMose( BiTHrTree T)/ 求 T 的最左子孫的左線索 BighrNode*p=T;while (p->Ltag! =Thread)p-p->lchild;if (p->lchild)return p->lchild;else return NULL;BiTHrNode*RightMost (BiTHrTree T)/ 求 T 的最右子孫的右線索 BiThrNode *p=T;while

32、(p->Rtag!=Thread) p-p->rchild;if (p->rchild) return p->rchild;else return NULL;int Isrightchild (BiThrTree T,BiThrTree&parent)/ 判斷 T 是否是 parent 的右孩子，若是返回 1，否則返回 Oparent=LeftMost(T);if (parent parent->rchild=p) return l;else (parent=NUIL; return O;)void posttraverse InThrTree (BiTh

33、eTree T)/后序遍歷中序線索樹，當(dāng)訪問(wèn)標(biāo)志tag為RIGHT時(shí)才訪問(wèn)當(dāng)前結(jié)點(diǎn)Tagtype tag;/ 待訪問(wèn)標(biāo)志，表示當(dāng)前結(jié)點(diǎn)是從左孩子還是右孩子返回的while (p) while (p->ltag!=Thread) p=p->lchild;if (p->rtag=link) tag=LEFT;/ 左孩子為線索，右孩子為鏈，相當(dāng)于從左返回else tag=RIGHT;/ 當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn)，相當(dāng)于從右返回 while( tag=RiGHT) visit (p);/ 僅當(dāng) tag=RIGHT 時(shí)返回if (Isrightchild (p, parent)/ 從右孩子返回

34、，需訪問(wèn) parent ，修改 p 指向雙親 p=parent; tag=RIGHT;)else/p 是左孩子，用最右的線索找雙親結(jié)點(diǎn) p=RightMost (p);if (p p->Rtag=Thread) tag=RIGHT; else tag=LEFT;if (tag=LEFT& p)p=p->rchild;5 凹入表示法打印二叉樹：采用前序遍歷的遞歸函數(shù)依次輸出各結(jié)點(diǎn)的值，子結(jié)點(diǎn)比父結(jié)點(diǎn)右縮進(jìn)int space)/space 為空格數(shù)3 個(gè)字符寬度，具體實(shí)現(xiàn)算法如下：Void disp (BiTree T ， int i; if (t) for (i=l; i&l

35、t;space;printf( ” dn ,disp (T->lchild,disp (T->rchild, 6 前序遍歷一棵中序線索樹：在不使用棧和遞歸的情況下對(duì)線索二叉樹進(jìn)行前序遍歷，需要知道任意結(jié)點(diǎn)前序的直接后繼。i+) printf(" "); p->data); space+3); space+3);/ 輸出 space 個(gè)空格typedef enumf Link ，Thread)PointerTag;/Link:0 指針， Thread:1 線索typedef struct BiThrNodet/ 中序線索樹結(jié)點(diǎn)結(jié)構(gòu)ElemType data;Struct BiThrNode lchild, rchild