樹與二叉樹的練習(xí)題

1、習(xí)題一、選擇題1 .有一 “遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給V。表 示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為()。A.向量B.樹C圖D.二叉樹2 .樹最合適用來表示()。A.有序數(shù)據(jù)元素B元素之間具有分支層次關(guān)系的數(shù)據(jù)C無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)3 .樹B的層號表示為la , 2b, 3d, 3e, 2c,對應(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的完全二叉樹至少有()個結(jié)點(diǎn)，至多有()個結(jié)點(diǎn)。A.2h_l B.h C . 2h-1 D.2h5 .在一楝完全二叉

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

3、點(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.D C .空 D.I（4） F結(jié)點(diǎn)的雙親結(jié)點(diǎn)是A.A B.B C.C D.D（5）樹的深度為A.1 B.2 C.3 D.4（6）B結(jié)點(diǎn)的深度為A.1 B.2 C.3 D.4（7） A結(jié)點(diǎn)所在的層是A.1 B.2 C.3 D.411. 在一棵具有35個結(jié)點(diǎn)的完全二叉樹中，該樹的深度為（）。A.5 B.6 C.7 D.812. 一棵有124個葉結(jié)點(diǎn)的完全二叉樹，最多有（）個結(jié)點(diǎn)。A. 247 B , 248 C , 249 D .

4、 25013 .用順序存儲的方法將完全二叉樹中所有結(jié)點(diǎn)逐層存放在數(shù)組R1,n中，結(jié)點(diǎn)Ri若有左子樹，則左子樹是結(jié)點(diǎn)（）。A.R2i+l B.R2i C.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個度為1的結(jié)點(diǎn)，有n2個度為2的結(jié)點(diǎn),，有 nm個度為m的結(jié)點(diǎn)，則該樹的葉結(jié)點(diǎn)數(shù)為（）。A.n1+n2+.+nm B.（m-l）nm+.+n2+1C.n1+n2+1 D.nl-n216 .已知某二叉樹的中序遍歷序列是 deba

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

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

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

8、結(jié)點(diǎn)數(shù)為6個，則葉子 結(jié)點(diǎn)為個。10 .在一棵二叉樹中，第五層上的結(jié)點(diǎn)數(shù)最多為 。11 .對于一棵具有n個結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針 域的總數(shù)為個，其中個用于鏈接孩子結(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后序序列為BDCAFGE則該

9、二叉樹結(jié) 點(diǎn)的前序序列為 ，該二叉樹對應(yīng)的森林包括 棵樹。17 .用一維數(shù)組存放的一棵完全二叉樹如題圖 6-4所示。腔用6.4則后序遍歷該二叉樹時結(jié)點(diǎn)訪問的順序?yàn)?。18 .由n個權(quán)值構(gòu)成的哈夫曼樹共有 個結(jié)點(diǎn)。19 .由帶權(quán)為3, 9, 6, 2, 5的5個葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長 度為。20 .設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有一個。21 .二叉樹的存儲結(jié)構(gòu)分為 ,樹的存儲結(jié)構(gòu)分為。三、判斷題1 .樹中任意結(jié)點(diǎn)的子樹不必是有序的。（）2 .樹可以看成特殊的無向圖。（）3 .可以使用雙鏈表表示樹型結(jié)構(gòu)。（）4 .順序存儲方

10、式只能用于存儲線性結(jié)構(gòu)。（）5 .完全二叉樹的某結(jié)點(diǎn)若無左孩子，則必是葉結(jié)點(diǎn)。（）6 .在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹。（）7 .由于二叉樹中每個結(jié)點(diǎn)的度最大為 2,所以二叉樹是一種特殊的樹。（）8 .二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子樹結(jié)點(diǎn)的前面。（）9 .二叉樹的前序和后序遍歷序列能惟一確定這棵二叉樹。（）10 .中序線索二叉樹中，右線索若不為空，則一定指向其父結(jié)點(diǎn)。（）四、算法和操作題1 .假定一棵二叉樹廣義表表示為 a（b（c） , d（e, D）,分別寫出對它進(jìn)行前序、 中序、后序遍歷的結(jié)果。前序：中序：后序：2 .已知一棵二叉樹的中序和后

11、序序列，求該二叉樹的高度和雙支、單支及葉子結(jié)點(diǎn)數(shù)。中根序列：c, b, d, e, a, g, i,h,j , f后根序列：c, e, d, b, i , j , h, g, fa高度：雙支：單支：葉子：3,已知一棵樹邊的集合為<I<SPAN> M> <I<SPAN> N> <E<SPAN> I> , <B<SPAN>E> <B<SPAN>D> <A<SPAN> B> <G<SPAN>J>, <G<SPAN>K

12、> <C<SPAN>G> <C<SPAN>F> <H<SPAN>L> <C<SPAN>H> <A<SPAN> C>）, 請畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？ 哪個是結(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的層次號分別是什么？（9）樹的深度是多少？（10）以結(jié)點(diǎn)C為根的子樹的深度是多少？4 .將算術(shù)表達(dá)式（a+b）+c*

13、（d+e）+f*（g+h）轉(zhuǎn)化為二叉樹。5 .一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組 BT中，如題表6-1所 示。畫出該二叉樹的鏈接表示形式。數(shù)組BT的存放形式是相對于滿二叉樹中編號為數(shù)組下標(biāo)值的結(jié)點(diǎn)值。若該結(jié)點(diǎn)不存在，則取0值6 .假設(shè)前序遍歷某棵樹的結(jié)點(diǎn)次序?yàn)?SACEFBDGHIJ痂序遍歷該樹的結(jié)點(diǎn)次 序?yàn)镃FEABHGIKJDS青畫出這棵樹。7 .已知一棵樹如題圖6-5所示，將其轉(zhuǎn)換為其孩子兄弟表示的二叉樹。并畫 出該二叉樹的后序線索二叉樹。8 .試找出分別滿足下列條件的所有二叉樹：(1)前序遍歷序列和中序遍歷序列相同。(2)中序遍歷序列和后序遍歷序列相同。(3)前序遍歷&q

14、uot;序列和后序遍歷'序列相同。9 .已知信息為“ ABCDBCDCBDBACB青按此信息構(gòu)造哈夫曼樹，求出每一字符 的最優(yōu)編碼。10 .己知中序線索二叉樹采用二叉鏈表存儲結(jié)構(gòu)，鏈結(jié)點(diǎn)的構(gòu)造為：tug kMd Lu ndiiki rug 其中若ltag為0,則lchild指向結(jié)點(diǎn)的前驅(qū)，否則lchild 指向左孩子結(jié)點(diǎn)； 若rtag為0,則rchild指向結(jié)點(diǎn)的后繼，否則rchild指向右孩子結(jié)點(diǎn)。下面 的算法返回x所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的位置。若該算法有錯，則請改正錯誤； 若無錯，請寫“正確”二字。BiTree INSUCC(BiTree x) s=X->rchild; if

15、 (s->rtag ) while (s->ltag ) s=s->rchild; returns ；) 五、算法設(shè)計(jì)題1 .編寫對二叉樹進(jìn)行中序遍歷的非遞歸算法，并對算法執(zhí)行題圖6-6所示的二叉樹的情況進(jìn)行跟蹤(即給出各階段棧的變化及輸出的結(jié)點(diǎn)序列)。 棧已經(jīng)定 義：InitStack(S)(初始化)、Empty(S)(判?？?、Push(S, p)(入棧)、Pop(S, p)(出棧)等操作。RA壯陽22 .假設(shè)在表示一棵二叉樹的二叉鏈表上增加兩個域：雙親域用于指示其雙親結(jié) 點(diǎn)，標(biāo)志域flag (可取0.2 )的值，用以區(qū)分在遍歷過程中到達(dá)該結(jié)點(diǎn)時繼 續(xù)向右或向左或訪問該結(jié)

16、點(diǎn)。試以此存儲結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞歸 形式的算法。3 . 一棵具有n個結(jié)點(diǎn)的完全二叉樹，以一維數(shù)組作為存儲結(jié)構(gòu)，試設(shè)計(jì)一個對 該完全二叉樹進(jìn)行前序遍歷的算法。4 .設(shè)中序線索樹的結(jié)點(diǎn)由5個域組成。Info :給出結(jié)點(diǎn)的數(shù)據(jù)域。 LT:標(biāo)志域，為0或1。LL:當(dāng)LT為1時，給出該結(jié)點(diǎn)的左孩子的地址。當(dāng)LT為0時，給出按中序遍歷的前驅(qū)結(jié)點(diǎn)地址。RT:標(biāo)志域，為0或1。RL:當(dāng)RT為1時，給出該結(jié)點(diǎn)的右孩子的地址。當(dāng)RT為O時，給出按中序遍歷的后繼結(jié)點(diǎn)地址。請編寫 程序，在具有上述結(jié)點(diǎn)結(jié)構(gòu)的中序線索二叉樹上，求某一結(jié)點(diǎn)p按后序遍歷次序的后繼結(jié)點(diǎn)的地址q,設(shè)該中序線索二叉樹的根結(jié)點(diǎn)地址為 r

17、。另外，請注意必須滿足：(l)額外空間的使用只能為O(1)。 (2)程序?yàn)榉沁f歸形式。5 .假設(shè)二叉樹采用鏈接方法存儲，編寫一個函數(shù)按凹入表表示法打印出該二叉 樹。6 .給出中序線索樹的結(jié)點(diǎn)結(jié)構(gòu)，設(shè)計(jì)算法在不使用棧和遞歸的情況下前序遍歷 一棵中序線索樹，并分析它的時間復(fù)雜度。7 .以二叉鏈表為存儲結(jié)構(gòu)，寫出交換各結(jié)點(diǎn)左右子樹的算法。8 .假設(shè)二叉樹采用鏈接方法存儲，編寫一個函數(shù)按凹入表表示法打印出該二叉 樹。、選擇題(參考答案)1 . B 2 . B 3 . C 4.A, C 5.C6. C 7 . A 8 . B 9. A, B 10.(1)C (2)A (3)C (4)A C (6)A C

18、 11. B 12.A 13 . B 14. A15. B 16 . D 17 . A 18 . C 19 . D 20 , D 二、填空題(參考答案)1 .樹的總結(jié)點(diǎn)數(shù)-1。2.前驅(qū)：1,后繼，任意多個。3. kl, k2, k4, k5, k7,2,k5, k6, kl,3,4。4.3 , 4, 6, 1, 1, 2, A, F, G* JU5 .(1) kA(i-), (2)*(3) n- l xk+n+1,(4)i wnk+l(n=0,l,2.),n+1.6 .前序遍歷，中序遍歷。7.前序，中序，后序，前序，后序。8. 2i-1 ,2/n,2/n.9.6 個。10. 16011.2n,

19、 n-l , n+l。12. A13 .樹可采用二叉樹的存儲結(jié)構(gòu)并可利用二叉樹的已有算法解決樹的有關(guān)問題。14 .只有1個結(jié)點(diǎn)的樹，空樹。 15.I, F。16.前序遍歷序列為：EACBDG F森林包括1棵樹。 17. HIDJKEBLFGCA0 18. 2n-l 。19. 56020. n+l。21.順序存儲和鏈?zhǔn)酱鎯Γp親鏈表表示法，孩子鏈表表示法，孩子兄弟鏈表表 示法 三、判斷題1. V 2. V 3. V 4. x 5. V 6. x 7. x 8. V 9. x 10. x四、算法和操作題1 .假設(shè)一棵二叉樹廣義表表示為 a(b(c) , d(e, D),分別寫出對它進(jìn)行前序、 中序

20、、后序遍歷的結(jié)果?！窘獯稹壳靶颍篴, 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 , b, d, e,右子樹為g , i , h, j , f);再由

21、后序 序列可知該樹的左子樹的根結(jié)點(diǎn)為 b,右子樹的根結(jié)點(diǎn)為f .再由中序遍歷序列 可知b結(jié)點(diǎn)的左子樹為c,右子樹為d, e);再由后序遍歷序列可知右子樹d, e的根結(jié)點(diǎn)為d,再由中序遍歷序列可知d的左子樹為空，右子樹為e。對以 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>, <B, E> <B, D> <

22、;A, B> <GJ> <G K> <C, G> <C, F>, <H, L>, <C, H> <A, C>,請畫出這棵 樹，并回答問題？【解答】根據(jù)邊集畫出的樹如下所示：0 I VjHji根結(jié)點(diǎn)是：A。(2)葉子結(jié)點(diǎn)是：D, M N, F, J, K, Lo (3) 結(jié)點(diǎn)G的雙親是：C。結(jié)點(diǎn)G的祖先是：A C (5)結(jié)點(diǎn)G的孩子是：J, Ko(6)結(jié)點(diǎn)E的子孫是：I , M N 結(jié)點(diǎn)E的兄弟是：D;結(jié)點(diǎn)F的兄弟是：G H(8)結(jié)點(diǎn)B和N的層次號分別是：2,5。(9)樹的深度是：5(10)以結(jié)點(diǎn)C為根的子

23、樹的深度是：3。4 .將算術(shù)表達(dá)式(a+b)+c*(d+e)+f*(g+h)轉(zhuǎn)化為二叉樹?！窘獯稹哭D(zhuǎn)化成如下二叉樹：1b5 .-棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組BT中，如題表6-1所示。畫出該二叉樹的鏈接表示形式。數(shù)組 BT的存放形式是相對于滿二叉樹中編 號為數(shù)組下標(biāo)值的結(jié)點(diǎn)值。若該結(jié)點(diǎn)不存在，則取 0值。題表6-1【解答】二叉樹的鏈?zhǔn)奖硎緸?6 .若前序遍歷某樹的結(jié)點(diǎn)次序：SACEFBDGHIJ盾序遍歷的結(jié)點(diǎn)次序?yàn)?CFEABHGIKJD SB出這棵樹?！窘獯稹慨嫵鰳淙缦拢?.將原教材題圖6-5轉(zhuǎn)換為孩子兄弟所表示的二叉樹及該二叉樹的后序線索二 叉樹如下：8 .空樹滿足所有條件

24、。非空樹如下：(1)前序和中序遍歷序列相同的二叉樹是沒有左子樹的二叉樹(右單支樹)。(2)中序和后序遍歷序列相同的二叉樹是沒有右子樹的二叉樹(左單支樹)。(3)前序和后序遍歷序列相同的二叉樹是只有根的二叉樹。9 .在信息“ABCD BCD CB DB AC Bp A, B, C, D四個字符出現(xiàn)的頻率依次 是:2, 5, 4, 3。在哈夫曼樹中每個字符的最優(yōu)編碼：I fi可得編碼為：A-110 B-O C-10 D-II1信息編碼為：110010111 0101111001110 11010010.錯誤。修改如下:BiTree INSUCC (BiTree x)S=X->rchild;i

25、f(s->rtag)while (s->ltag )s=s->lchild;return S; 五、算法設(shè)計(jì)題1 .編寫對二叉樹進(jìn)行中序遍歷的非遞歸算法，并對算法執(zhí)行原教材題圖6-6所示的二叉樹的情況進(jìn)行跟蹤(即給出各階段棧的變化及輸出的結(jié)點(diǎn)序列)。【解答】中序遍歷的非遞歸算法如下：InorderTrirerse (B?ree T： r nitStack;W,的5.1 號1 Empty (S) If (p)Pi_Eh(£； p) ;p=p-> Ichi I d; ) elseI POP (S. D)：printf ( “8* p->data); p=p-

26、>rchlld).) ) )對于給定的二叉樹，算法執(zhí)行情況如下：A入棧，B入棧，D入棧，D出棧,訪問D, B出棧，訪問B, A出棧，訪問A, , C入棧，E入棧，E出棧，訪問E, G入棧,G出棧，訪問G, C出棧，訪問C, F入棧,F出棧，訪問F,棧和指針 p均空，結(jié)束。 最后的遍歷序列是：DBAGECF2 .假設(shè)在表示一棵二叉樹的二叉鏈表上增加兩個域：雙親域用于指示其雙親結(jié) 點(diǎn)，標(biāo)志域flag (可取0, , 2)的值，用以區(qū)分在遍歷過程中到達(dá)該結(jié)點(diǎn)時 繼續(xù)向右或向左或訪問該結(jié)點(diǎn)。試以此存儲結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞 推形式的算法?！窘獯稹恳鉀Q這一問題必須區(qū)分結(jié)點(diǎn)在訪問過程中的狀

27、態(tài)，這可通過結(jié)點(diǎn)的 標(biāo)志域來處理。對一個結(jié)點(diǎn)來說當(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 pastonder (BTree T)"后扁匾回二叉樹日&類型的結(jié)點(diǎn)含4個博；flag* parent) Ichi Id > rchild ; flag初值為C>指針指向根結(jié)點(diǎn)(EiTree jrl:wliile %) witch ( case 0: p->flag«l ： if (p->lchild)

28、 p-p->lchildtireak:case 1: p-flag7=2; i£ (p/rcHil d) ppzrchild; break;case 2: p->flag=O ：prirrtf (p- >dst a),p=p->p3reEit ：3 . 一棵具有n個結(jié)點(diǎn)的完全二叉樹，以一維數(shù)組作為存儲結(jié)構(gòu)，試設(shè)計(jì)一個對該完全二 叉樹進(jìn)行前序遍歷的算法?！窘獯稹吭O(shè)完全二叉樹的結(jié)點(diǎn)以層次為序，按從上至下，由左至右的順序編號， 存放在一維數(shù)組R1, , n中。對于編號為t的結(jié)點(diǎn)，若存在子結(jié)點(diǎn)，其左 孩子結(jié)點(diǎn)一定是2*t ,右孩子結(jié)點(diǎn)是2*t+l ,由此可得對完全二叉

29、樹進(jìn)行前序遍 歷的遞歸算法。void preorder (int R . int m int t)/J前序遍歷一叉樹 R 口(printf凱n Ht);輸出當(dāng)前堵點(diǎn)值If (t*2<=n)precrder(R, n, t*2);遞歸前序遍歷左子結(jié)點(diǎn)if (t*2+l<ni)pTearder - 口 t2+l);"遞歸前序遍歷石子結(jié)點(diǎn) |4 .在不使用棧和遞歸的條件下，后序序列遍歷中序線索二叉樹，需要知道任意 結(jié)點(diǎn)的后序直接后繼。中序線索樹所能提供的是當(dāng)前訪問結(jié)點(diǎn)的祖先(雙親) 信息，利用雙親信息，就可以對中序線索樹進(jìn)行后序遍歷。中序線索樹有如下 性質(zhì)： 若x是parent

30、的左孩子，則parent是x的最右子孫的右線索。 若x是parent的右孩子，則parent是x的最左子孫的左線索。因此設(shè)計(jì)兩個函數(shù)求給定結(jié)點(diǎn)的最左子孫的左線索和最右子孫的右線索；這兩個線索均 是T的祖先。具體實(shí)現(xiàn)如下：typedal enumUink, Thread Painter Tag;/Linic-Di 指引;ThiBad=-lr 線索type defstruct BiThrNode ("中序線索樹結(jié)點(diǎn)結(jié)構(gòu)EldataStruct Bi ThrHode Ictiild, rchi Id;PdinterTag Itag, Rtag： BiThrNode, iThrNcde;v/

31、pedef entxn LEFT, RIGKT) TagT5-pe;BiTHrH口加+LeitNcse( BiTttrTree T) ”求二的最左子孫的左線索£ Bi ghrNode'flfiils (j>-Ltag! =Thread) p-p-lchild;if (p->lrhiId) return p->lchild; al se re turn NULL :)MTHrMode礪1由d。式(BITHrTree T) "求T的最右子林的右線索 BiThrVods與=Twnile (p->Rtag! -Thrsad p-p->rchil

32、d：if ；p-3rohildjrgturrt p->rchild;else return NULL： )im工sri期shila (EIThrTree LbiThrTree Stparent)判斷T是否是rm出的右孩子，若是返回L否則返回。 P4rsnt=LeftMo5t .if (parent8c S：parent->rchild=p) TBturn 1;else (parenlNUIL, return0,)voidttisttraverseInThuPree (EiTheTree T)。后序遍歷中序微索樹.當(dāng)訪問標(biāo)志t£g為RIGETT時才訪問當(dāng)前轉(zhuǎn)點(diǎn) Tag ty

33、pe tag；"待訪間標(biāo)志表示當(dāng)前結(jié)點(diǎn)是從左孩子還是右孩子返叵的而lc (p) while Cp->ltig!=ThrBad) r=&->lchild： if "->工國相二ink) tag=LEFT；"左接為線索.石形亍為榜.相當(dāng)于從左返回else ta移也4匯;當(dāng)前結(jié)點(diǎn)為葉州點(diǎn)，相當(dāng)于從右退回 RiGHT)1 visit, "僅當(dāng)tRIGHT時返回 if (Leri ghtrhiId :p, pr»nt/從右孩彳返回r需訪間pa±Ctl如修改P指向雙親 p=parpnt; tag=RGHT ： '

34、.山”是左遨了，用最右的線索找雙親結(jié)點(diǎn) ¥=REghtMci 年t (p)；if&-評匕鏟=Thrm")tssIGKT;else TaE-LEFT;1Jif (t3S=LEfI'fflp) p=p->rchild； )5 .凹入表示法打印二叉樹：采用前序遍歷的遞歸函數(shù)依次輸出各結(jié)點(diǎn)的值，子結(jié)點(diǎn)比父結(jié)點(diǎn)右縮進(jìn) 3個字 符寬度，具體實(shí)現(xiàn)算法如下：Void di即(BiTree T, int space)/space為空格數(shù)( int i:if (t) far (i=l： i<£paee ：l-m-) prifttf C ") ：/5俞出 題縣整 個空格printf ("如5 ，p->dat a):ilisp (T->1 child,spade+3):d.isp ()工child,space+3);r6 .前序遍歷一棵中序線索樹：在不使用棧和遞歸的情況下對線索二叉樹進(jìn)行前序遍歷，需要知道任意結(jié)點(diǎn)前 序的直接后繼。type def enuiaf Link ； Thread) Pc inter Tag ;/Link ; Q 指針，Thread : 1 線索type def struct BiThxNo det