數(shù)據(jù)結(jié)構(gòu)單元練習(xí)7.

1、(11)(12)(13)(14)(15)(16)前序?yàn)锳，B，CDEBAFCHG，則二單元練習(xí)7一判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打V;錯(cuò)誤的打X )(V) (1)樹結(jié)構(gòu)中每 個(gè)結(jié)點(diǎn)最 多只有一個(gè)直 接前驅(qū)。(X) (2)完全二叉樹 一定是滿 二查樹。(X) ( 3)在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。(V) (4) 一棵二叉樹中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，必定是該二叉樹前序遍歷的最后一個(gè)結(jié)點(diǎn)。(V) ( 5)二叉樹的前序遍歷中，任意一個(gè)結(jié)點(diǎn)均處于其子女結(jié)點(diǎn)的前面。(V) (6)由二叉樹的前序遍歷序列和中序遍歷序列，可以推導(dǎo)出后序遍歷的序列。(V) ( 7)在完全二叉樹

2、中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必然是葉子結(jié)點(diǎn)。(X) ( 8)在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同，其編碼也相同，對(duì)于這種情況應(yīng)該做特 殊處理。(X) ( 9)含多于兩棵樹的森林轉(zhuǎn)換的二叉樹，其根結(jié)點(diǎn)一 定無(wú)右 孩子。(V) (10)具有n個(gè)葉子結(jié)點(diǎn)的 哈夫曼 樹共有2n-1個(gè)結(jié)點(diǎn)。二填空題(1) 在樹中，一個(gè)結(jié)點(diǎn)所擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度 。(2) 度為零的結(jié)點(diǎn)稱為葉(或葉子，或終端)結(jié)點(diǎn)。(3) 樹中結(jié)點(diǎn)的最大層次稱為樹的深度(或高度)。(4) 對(duì)于二叉樹來(lái)說(shuō)，第i層上至多有 2i-1個(gè)結(jié)點(diǎn)。(5) 深度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)。(6) 由一棵二叉樹的前序序列和中序序列可唯一

3、確定這棵二叉樹。(7) 有20個(gè)結(jié)點(diǎn)的完全二叉樹，編號(hào)為10的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)是5 。(8) 哈夫曼樹是帶權(quán)路徑長(zhǎng)度最小 的二叉樹。(9) 由二叉樹的后序和中序 遍歷序列，可以唯一確定一棵二叉樹。(10) 某二叉樹的中序遍歷序列為：DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為:DABEC 。設(shè)一棵二叉樹結(jié)點(diǎn)的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為:叉樹中葉結(jié)點(diǎn)是：E、F、H 。已知完全二叉樹的第 8層有8個(gè)結(jié)點(diǎn)，則其葉結(jié)點(diǎn)數(shù)是68。由樹轉(zhuǎn)換成二叉樹時(shí)，其根結(jié)點(diǎn)無(wú)右子樹 。采用二叉鏈表存儲(chǔ)的 n個(gè)結(jié)點(diǎn)的二叉樹，一共有 2n個(gè)指針域。采用二叉鏈表存儲(chǔ)的 n個(gè)結(jié)點(diǎn)的二叉樹，共

4、有空指針n+1個(gè)。(17)三個(gè)結(jié)點(diǎn)可以組成2種不同形態(tài)的樹。2*i。(18) 將一棵完全二叉樹按層次編號(hào)，對(duì)于任意一個(gè)編號(hào)為i的結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)的編號(hào)為ABEFHCG給定如下圖所示的二叉樹，其前序遍歷序列為:(17)三個(gè)結(jié)點(diǎn)可以組成2種不同形態(tài)的樹。(17)三個(gè)結(jié)點(diǎn)可以組成2種不同形態(tài)的樹。(19) 給定如下圖所示的二叉樹，其層次遍歷序列為：ABCEFGHACBEFGH三選擇題(1) 樹最適合用來(lái)表示( D )。A 有序數(shù)據(jù)元素C 元素之間無(wú)聯(lián)系的數(shù)據(jù)B 無(wú)序數(shù)據(jù)元素D元素之間有分支的層次關(guān)系(2) 前序?yàn)锳 , B, C的二叉樹共有( D )種。A 2B 3C 4(3) 根據(jù)二叉樹的定義，

5、具有3個(gè)結(jié)點(diǎn)的二叉樹有( C )種樹型。A 3B 4C 5(4 )在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)的總數(shù)為(B )A 16B 31C 32(5)具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為( C )A 5B 6C 7D 5D 6D 33D 8(6)任何一棵二叉樹的葉結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序(A.不發(fā)生改變B 發(fā)生改變C 不能確定A )。D 以上都不對(duì)(7) A , B為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，A在B前的條件是( C )。B . A是B祖先C . A在B左方D. A是B子孫(8) 下列4棵樹中,B )不是完全二叉樹。(9) 如右圖所示的二叉樹，后序遍歷的序列是(A、B、C、

6、D、E、F、G、H、IB . A、B、D、H、I、E、C、F、GC . H、D、I、B、E、A、F、C、GD. H、I、D、E、B、F、G、C、AD )(10) 對(duì)于下邊的二叉樹，其中序序列為(A )A. DBEHAFCG.ABCDEFGH(11) 某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為：DEBAC，則前序遍歷序列為(D )。A . ACBEDB . DECABC . DEABCD . CEDBA(12) 具有n (n>1)個(gè)結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i ( 2i>n)的左孩子結(jié)點(diǎn)是(D )。A . 2iB . 2i+1C . 2i-1D .不存在(若2i<=n，

7、則答案為A)(13) 把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是(A )。A .唯一的B.有多種C .有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子D .有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子(14 )將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為45的結(jié)點(diǎn)的左孩子編號(hào)為(B )。A . 46B . 47C . 90D . 91(15)將一棵有 100 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為 49 的結(jié)點(diǎn)的右孩子編號(hào)為( B )。A 98B 99C. 50D. 10016)二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索，這

8、種說(shuō)法(BA正確B.錯(cuò)誤C .不確定D .都有可能17)下列陳述正確的是(D )。A二叉樹是度為 2 的有序樹B .二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分C二叉樹中必有度為2 的結(jié)點(diǎn)D .一叉樹中最多只有兩棵子樹，且有左右子樹之分18)用 5 個(gè)權(quán)值 3, 2, 4, 5, 1 構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是(B )。A 32B. 33C. 34D.15先構(gòu)造哈夫曼樹，WPL=( 1+2) *3+( 3+4+5) *2=33 )19)在樹結(jié)構(gòu)中，若結(jié)點(diǎn)B有4個(gè)兄弟，A是B的父親結(jié)點(diǎn)，貝UA的度為為(C )。A 3B. 4C. 5D.620)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)比度為 2的結(jié)點(diǎn)的個(gè)數(shù)( C )。A

9、無(wú)關(guān)B.相等C .多一個(gè)D.少一個(gè)四 . 簡(jiǎn)答題1 已知一棵樹邊的集合如下，請(qǐng)畫出此樹，并回答問(wèn)題。(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G ,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)(1) 哪個(gè)是根結(jié)點(diǎn)？(2) 哪些是葉結(jié)點(diǎn)？(3) 哪個(gè)是G的雙親？(4) 哪些是G的祖先？(5) 哪些是G的孩子？(6) 哪些是E的子孫？(7) 哪些是E的兄弟？哪些是 F的兄弟？(8) 結(jié)點(diǎn)B和N的層次各是多少？( 9)樹的深度是多少？(10) 以結(jié)點(diǎn)C為根的子樹的深度是多少？(11) 樹的度數(shù)是多少？答：( 1 ) A 是根結(jié)點(diǎn)。(2)

10、葉結(jié)點(diǎn)： M，N，D，J，K，F(xiàn)，I。( 3) G 的雙親： C。( 4) G 的祖先： A ， C。( 5) G 的孩子： J，K。( 6) E 的子孫： L，M ，N。( 7) E 的兄弟： D；F 的兄弟： G，H。( 8)結(jié)點(diǎn) B 的層次為 2；結(jié)點(diǎn) N 的層次是 5。( 9)樹的深度是 5。( 10)以結(jié)點(diǎn) C 為根的子樹的深度是 3。( 11 )樹的度數(shù)是 3。2.設(shè)下列二叉樹是與某森林對(duì)應(yīng)的二叉樹，試回答下列問(wèn)題。ACBDFGEHJKL解4(2)G,K(3)6(4)2(5)7答種5(2)AAACBCBBACABCCB答o(2)O(i)(i)(i)A , C4.分別畫出具有3個(gè)結(jié)點(diǎn)

11、的樹和三個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。(5 )森林中有幾個(gè)葉結(jié)點(diǎn)?ABC試問(wèn)有幾種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果？并畫三個(gè)結(jié)點(diǎn)的樹(1)森林中有幾棵樹?(2)每一棵樹的根結(jié)點(diǎn)分別是什么?(3 )第一棵樹有幾個(gè)結(jié)點(diǎn)?(4 )第二棵樹有幾個(gè)結(jié)點(diǎn)?3.二叉樹按中序遍歷的結(jié)果為:出這些二叉樹。三個(gè)結(jié)點(diǎn)的二叉樹樹五.應(yīng)用題1 已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：A, C, D, B, G, I，H, F, E和 A, B, C, D, E, F, G, H I。 請(qǐng)畫出該二叉樹，并寫出它的前序遍歷的序列。答：恢復(fù)的二叉樹為：其前序遍歷的序列為：E B A D C F H G I 2 .

12、已知一棵二叉樹的前序遍歷和中序遍歷的序列分別為：A , B, D, G H, C, E, F, I 和 G D, H, B, A, E, C, I , F。 請(qǐng)畫出此二叉樹，并寫出它的后序遍歷的序列。答：恢復(fù)的二叉樹為：AB：C1DE : FGH ：l ' I其后序遍歷的序列為：G H D B E I F C AABCDEFGHIJ，中序遍歷的序列為:DBGEHJACIF，請(qǐng)畫3.已知一棵樹的層次遍歷的序列為：出該二叉樹，并寫出它的后序遍歷的序列。解:后序遍歷的序列：D G J H E B I F C A解:4.(1(2) A解:5.把下列森林轉(zhuǎn)換為二叉樹KABGCHE其中根結(jié)點(diǎn)的指針

13、為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。6.把下列二叉樹還原為森林解:其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。7.某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)，其結(jié)構(gòu)如下:1234567891011121314151617181920EAFDHCGIB(1)畫出該二叉樹(3分)(2)寫出按層次遍歷的結(jié)點(diǎn)序列(2分)解:(1)(2)00237580101JHFDBACEGI000940000012368

14、910457Ichilddatarchild& 某二叉樹的存儲(chǔ)如下:其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。(1)畫出該二叉樹(3分)其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。(2)寫出該樹的前序遍歷的結(jié)點(diǎn)序列( 解：(1)ABCDEFGHIJ2分)(2 )前序遍歷的結(jié)點(diǎn)序列:A B C E D F H G I J給定如圖所示二叉樹 T,請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)

15、域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。解：(1)中序遍歷序列：55 402560 28083354(2)中序線索二叉樹:其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。NU

16、LL*其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。畫出表達(dá)式：-A+B-C+D的標(biāo)識(shí)符樹，并求它們的后綴表達(dá)式。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。解:+后綴表達(dá)式：0 A - B + C - D +9. 畫出表達(dá)式：（A+B/C-D ） * （ E* （ F+G）的標(biāo)識(shí)符樹，并求它們的后綴表達(dá)式。 解：后綴表達(dá)式：A B C / + D -E F G + * *其中根結(jié)

17、點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。10. 對(duì)于算術(shù)表達(dá)式（A+B*C/D）*E+F*G，畫出標(biāo)識(shí)符樹，并求它們的后綴表達(dá)式。 解：其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。其中根結(jié)點(diǎn)的指針為6, Ichild 、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域,data為數(shù)據(jù)域。后綴表達(dá)式：A B C D / * + E * F G * +60253512131718967845解

18、236914151617823349161720299111465211. 給定一個(gè)權(quán)集 W=4 , 5, 7, 8, 6, 12, 18，試畫出相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)路徑長(zhǎng) 度 WPL。解：456 7 8 121891317253560WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15912. 給定一個(gè)權(quán)集 W=3，15，17，14，6，16，9，2，試畫出相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)路 徑長(zhǎng)度WPL。5293311204982WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=22913. 假設(shè)用于通信的電文僅由A、B、C、D、E、F、G 8

19、個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。1字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率A10107B0019C100002D10016E1132D100013E0121F101110解：以權(quán)值：2、3、6、7、10、19、21、32構(gòu)造哈夫曼樹：六算法設(shè)計(jì)題以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)二叉樹BT 結(jié)構(gòu)為：typedef struct BT char data;BT *lchild;BT *rchild;BT;1求二叉樹中的度數(shù)為 2 的結(jié)點(diǎn)。2求二叉樹中值為最大的元素。3將二叉樹各結(jié)點(diǎn)存儲(chǔ)到一維數(shù)組中。4前序輸出二叉樹中各結(jié)點(diǎn)及其結(jié)點(diǎn)所在的層號(hào)。5

20、求二叉樹的寬度6交換二叉樹各結(jié)點(diǎn)的左右子樹。7寫出在二叉樹中查找值為 x 的結(jié)點(diǎn)在樹中層數(shù)的算法。解：1求二叉樹中的度數(shù)為 2 的結(jié)點(diǎn)。void count(BT t) if (t) if (t->lchild && t->rchild) k+;count(t->lchild);count(t->rchild);2. 求二叉樹中值為最大的元素。int maxnode(BT t, int max) if (t) if (t->data>max) max=t->data;max=maxnode(t->lchild,max); max=

21、maxnode(t->rchild,max);3將二叉樹各結(jié)點(diǎn)存儲(chǔ)到一維數(shù)組中。void create(BT t,int a ,int i) if (t) ai=t->data;create (t->lchild, a, 2*i);create (t->rchild, a, 2*i+1);4前序輸出二叉樹中各結(jié)點(diǎn)及其結(jié)點(diǎn)所在的層號(hào)。void preorderlevel (BT t,int h) / t 的層數(shù)為 h if (t!=NULL) printf( “ %d,%d” ,t ->data, h);preorderlevel (t->lchild, h+

22、1);preorderlevel (t->rchild, h+1);5. 求二叉樹的寬度思想：按層遍歷二叉樹，采用一個(gè)隊(duì)列q,讓根結(jié)點(diǎn)入隊(duì)列，最后出隊(duì)列，若有左右子樹，則左右子樹根結(jié)點(diǎn)入隊(duì)列，如此反復(fù)，直到隊(duì)列為空。int Width(BT *T) int front=-1,rear=-1;/ 隊(duì)列初始化int flag=0,count=0,p;/ p用于指向樹中層的最右邊的結(jié)點(diǎn),標(biāo)志 flag 記錄層中結(jié)點(diǎn)數(shù)的最大值if (T!=NULL) rear+;qrear=T;flag=1;p=rear;while (front<p) front+;T=qfront;if (T->

23、lchild!=NULL) rear+;qrear=T->lchild; count+;if (T->rchild!=NULL) rear+;qrear=T->rchild; count+;if (front=p)/ 當(dāng)前層已遍歷完畢 if (flag<count)flag=count;count=0;p=rear;/ p 指向下一層最右邊的結(jié)點(diǎn) / endwhile return(flag);6解：借助棧來(lái)進(jìn)行對(duì)換。Swap(BinTree*T) BinTree *stack100, *temp;int top=-1;root=T;if (T!=NULL)top+;s

24、tacktop=T;while(top>-1) T=stacktop;top-;/ 交換結(jié)點(diǎn)的左右指針if (T->child!=NULL|T->rchild!=NULL)temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;if (T->lchild!=NULL) top+; stacktop=T->lchild;if (T->rchild!=NULL) top+; stacktop=T->rchild;main() int I,j,k,l;printf( “ n” );root=

25、CreateBinTree();Inorder (root);i=CountNode (root);j=CountLeafs (root);k=Depth (root);l=Width (root);printf( “ nThe Node ' s Number:%d” ,i);printf( “ nThe Leafs ' s Number:%d” ,j);printf( “ nThe Depth is:%d ” ,k); printf ( “ nThe width is:%d ” ,l); Swap(root);Printf( “ nThe swapTree is: ” );

26、Inorder(root);7解：int h=- 1,lh=1,count=0;charx= ' c' ;/ 賦初值Level (BinTree T,int h,int lh)/ 求 X 結(jié)點(diǎn)在樹只的層樹 if (T=Null)h=0;elseif (T->data=x) h=lh; count=h;else h+;Level(T->lchild,h,lh);if (h=-1)Level(T->rchild,h,lh);main() BinTree *(*newroot);Printf( “ n”);Root=CreateBinTree();Inorder(r

27、oot);Printf( “ n”);Level(root,h,lh);Printf( “ %d” ,co unt);模擬考題一. 讀程序，寫出運(yùn)行結(jié)果1.二叉樹的結(jié)構(gòu)如圖所示，試寫出執(zhí)行下列算法后的輸出結(jié)果:（用大寫的英文字母表示，字母之間不要任何間隔符號(hào)，最后一個(gè)字母后面也不要間隔符號(hào)）typedef struct BT datatype data;BT *lchild;BT *rchild;BT;void Preorder(BT *T) i f (T!=NULL) cout<< T->data;Preorder(T->lchild);Preorder(T->

28、rchild);解: ABCEDFG先序遍歷2.二叉樹的結(jié)構(gòu)如圖所示，試寫出執(zhí)行下列算法后的輸出結(jié)果:定義結(jié)點(diǎn)typedef struct BT datatype data; /BT *lchild;BT *rchild;BT;int BTD(BT *T) i nt ldep,rdep;if (T=NULL)return 0;else ldep= BTD (T->lchild); rdep= BTD (T->rchild); if (ldep>rdep) retur n ldep+1;elseretur n rdep+1;解：4（求二叉樹深度）3.二叉樹的結(jié)構(gòu)如圖所示，試寫出

29、執(zhí)行下列算法后，typedef struct BT datatype data; /定義結(jié)點(diǎn)BT *lchild;count的值為多少?BT *rchild;BT；int coun t=0;void Leafnum(BT *T)if (T!=NULL) if(T->lchild=NULL && T->rchild=NULL)coun t+;Leafnum(T->lchild);Leafnum(T->rchild);解：3(求葉結(jié)點(diǎn)數(shù))(2, 3, 4改為程序填空)二. 程序填空1 填空完成二叉樹按層次遍歷的程序typedef struct BT data

30、type data;/定義結(jié)點(diǎn)BT *lchild;BT *rchild;BT;void Levelorder(BT *T)/層次遍歷 int i,j;BT *q1OO,*p;p=T;if ( p!=NULL ) i=1;qi=p;j=2; while (i!=j) p=qi;cout<< p_>data ;if ( p->lchild!=NULL ) qj= p->lchild ;j+;if (p->rchild!=NULL) qj= p->rchild ;j+; i+;三. 應(yīng)用題1.將下列二叉樹轉(zhuǎn)換為森林。解:2.畫出和下列二叉樹相應(yīng)的森林。解:（根右邊的子樹肯定是森林，而孩子結(jié)點(diǎn)的右子樹均為兄弟）解:(1)EAFDHCGIB3.某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)，其結(jié)構(gòu)如下:1234567891011121314151617181920(1)畫出該二叉樹(2分)3分)(2)寫出結(jié)點(diǎn)值為 D的父結(jié)點(diǎn)及左、右子樹(2) D的父結(jié)點(diǎn)為AD的左子樹為CD的右子樹為空00237580101JHFDBACEGI0009400000368910457LchildDataRchild其中根