數(shù)據(jù)結(jié)構(gòu)第六章考試題庫（含答案）

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)第六章考試題庫（含答案）第六章樹和二叉樹

一、選擇題

1．已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()

A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE

2．算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）

A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++/3.設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖），

+它所表示的算術(shù)表達(dá)式是（）+*C-*A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)

DEFGABC.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G

4.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）

A．5B．6C．7D．85.在下述結(jié)論中，正確的是（）

①只有一個結(jié)點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度一致的滿二叉樹。A．①②③B．②③④C．②④D．①④

6.設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（）

A．m-nB．m-n-1C．n+1D．條件不足，無法確定7.樹是結(jié)點的有限集合，它（(1）)根結(jié)點，記為T。其余結(jié)點分成為m（m>0）個(（2）)的集合T1，T2，?，Ｔm，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1≤i≤m）。一個結(jié)點的子結(jié)點個數(shù)稱為該結(jié)點的(（3）)。二叉樹與樹是兩個不同的概念，二叉樹也是結(jié)點的有限集合，它(（4）)根結(jié)點。可以把樹的根結(jié)點的層數(shù)定義為1，其他結(jié)點的層數(shù)等于其父結(jié)點所在層數(shù)加上1。令T是一棵二叉樹，Ki和Kj是T中子結(jié)點數(shù)小于2的結(jié)點中的任意兩個，它們所在的層數(shù)分別為λKi和λKj，當(dāng)關(guān)系式│λKi-λKj│≤1一定成立時，則稱T為一棵（(5)）。供選擇的答案：

（1）(4)A.有0個或1個B.有0個或多個C.有且只有一個D.有1個或1個以上（2）A.互不相交B.允許相交C.允許葉結(jié)點相交D.允許樹枝結(jié)點相交（3）A.權(quán)B.維數(shù)C.次數(shù)D.序

（5）A.飽滿樹B.查找樹C.平衡樹D.完全樹8．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（）

A．9B．11C．15D．不確定

9．在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個

A．4B．5C．6D．7

10．設(shè)森林F中有三棵樹，第一，其次，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）。

A．M1B．M1+M2C．M3D．M2+M311．具有10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點，

A．8B．9C．10D．ll

12．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）

A．250B．500C．254D．505E．以上答案都不對

13.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為()

A．不確定B．2nC．2n+1D．2n-114.有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（）。

A．不確定B．2nC．2n+1D．2n-115．若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（）。

A．n-1B．?n/m?-1C．?(n-1)/(m-1)?D．?n/(m-1)?-1E．?(n+1)/(m+1)?-116.有關(guān)二叉樹以下說法正確的是（）

A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2D．二叉樹中任何一個結(jié)點的度都為217．二叉樹的第I層上最多含有結(jié)點數(shù)為（）

II-1I-1I

A．2B．2-1C．2D．2-118.一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（）

A．11B．10C．11至1025之間D．10至1024之間

19．一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有()結(jié)點

A．2hB．2h-1C．2h+1D．h+120．對于有n個結(jié)點的二叉樹,其高度為（）

A．nlog2nB．log2nC．?log2n?|+1D．不確定21.一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）是（）

A．?logn?+1B．logn+1C．?logn?D．logn-1

22．深度為h的滿m叉樹的第k層有（）個結(jié)點。(1==1)。31．必需把一般樹轉(zhuǎn)換成二叉樹后才能進(jìn)行存儲。32．完全二叉樹的存儲結(jié)構(gòu)尋常采用順序存儲結(jié)構(gòu)。33．將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹；34．在二叉樹中插入結(jié)點，則此二叉樹便不再是二叉樹了。35．二叉樹是一般樹的特別情形。36．樹與二叉樹是兩種不同的樹型結(jié)構(gòu)。37.非空的二叉樹一定滿足：某結(jié)點若有左孩子，則其中序前驅(qū)一定沒有右孩子

38．在任意一棵非空二叉排序樹，刪除某結(jié)點后又將其插入，則所得二叉排序樹與刪除前原二叉排序樹一致。39．度為二的樹就是二叉樹。

k-2

40．深度為k具有n個結(jié)點的完全二叉樹，其編號最小的結(jié)點序號為?2?+1。

41.下面二叉樹的定義只有一個是正確的，請在正確的地方畫“√〞。

（1）它是由一個根和兩株互不相交的、稱為左子樹和右子樹的二叉樹組成。

i-1

（2）（a）在一株二叉樹的級i上，最大結(jié)點數(shù)是2（i≥1）

k-1

（b）在一棵深度為k的二叉樹中，最大結(jié)點數(shù)是2+1（k≥1）。（3）二叉樹是結(jié)點的集合，滿足如下條件：（a）它或者是空集；

（b）或者是由一個根和兩個互不相交的、稱為左子樹和右子樹的二叉樹組成。

42.在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點。43.線索二叉樹的優(yōu)點是便于是在中序下查找前驅(qū)結(jié)點和后繼結(jié)點。

44.二叉樹中序線索化后，不存在空指針域。45．霍夫曼樹的結(jié)點個數(shù)不能是偶數(shù)。46.一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點的權(quán)值之和。47.哈夫曼樹無左右子樹之分。

48．當(dāng)一棵具有n個葉子結(jié)點的二叉樹的WPL值為最小時，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。

49．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。

50.用鏈表（llink-rlink）存儲包含n個結(jié)點的二叉樹時，結(jié)點的2n個指針區(qū)域中有n+1個空指針。()

三、填空題

1．二叉樹由_(1)__，__(2)_，_(3)__三個基本單元組成。2．樹在計算機(jī)內(nèi)的表示方式有_(1)__，_(2)__，_(3)__。3．在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是______。

4．中綴式a+b*3+4*（c-d）對應(yīng)的前綴式為__(1)_，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運(yùn)算結(jié)果為_(2)__。

5．二叉樹中某一結(jié)點左子樹的深度減去右子樹的深度稱為該結(jié)點的____。6．具有256個結(jié)點的完全二叉樹的深度為______。

7．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有______個葉子結(jié)點。

8．深度為k的完全二叉樹至少有___(1)____個結(jié)點，至多有___(2)____個結(jié)點。

9．深度為H的完全二叉樹至少有_(1)__個結(jié)點；至多有_(2)__個結(jié)點；H和結(jié)點總數(shù)N之間的關(guān)系是(3)__。

10．在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是______。

11．在完全二叉樹中，編號為i和j的兩個結(jié)點處于同一層的條件是______。

12．一棵有n個結(jié)點的滿二叉樹有__(1)_個度為1的結(jié)點、有__(2)_個分支（非終端）結(jié)點和__(3)_個葉子，該滿二叉樹的深度為_(4)__。

14．在一棵二叉樹中，度為零的結(jié)點的個數(shù)為N0,度為2的結(jié)點的個數(shù)為N2,則有N0=______

15．設(shè)只含根結(jié)點的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點數(shù)為______,最小結(jié)點數(shù)為______。

16．設(shè)有N個結(jié)點的完全二叉樹順序存放在向量A[1:N]中，其下標(biāo)值最大的分支結(jié)點為______。

17．高度為K的完全二叉樹至少有______個葉子結(jié)點。18．高度為8的完全二叉樹至少有______個葉子結(jié)點。19．已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是______。

20．一個有2023個結(jié)點的完全二叉樹的高度為______。

21．設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應(yīng)的二叉樹為B,已知T1,T2,T3的結(jié)點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有__(1)_個結(jié)點，右子樹中有_(2)__個結(jié)點。

22．一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是__(1)_；編號是i的結(jié)點所在的層次號是_(2)__（根所在的層次號規(guī)定為1層）。

23．如某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)為______。

24．假使結(jié)點A有3個兄弟，而且B是A的雙親，則B的度是______。

25．高度為h的2-3樹中葉子結(jié)點的數(shù)目至多為______。26．完全二叉樹中，結(jié)點個數(shù)為n，則編號最大的分支結(jié)點的編號為______。

27．設(shè)一棵完全二叉樹葉子結(jié)點數(shù)為k,最終一層結(jié)點數(shù)>2，則該二叉樹的高度為______。

28．對于一個具有n個結(jié)點的二元樹，當(dāng)它為一棵_(1)_二元樹時具有最小高度，當(dāng)它為一棵_(2)_時，具有最大高度。

29．具有N個結(jié)點的二叉樹，采用二叉鏈表存儲，共有______個空鏈域。30．8層完全二叉樹至少有______個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為______。

31．含4個度為2的結(jié)點和5個葉子結(jié)點的二叉樹，可有______個度為1的結(jié)點。

32．一棵樹T中，包括一個度為1的結(jié)點，兩個度為2的結(jié)點，三個度為3的結(jié)點，四個度為4的結(jié)點和若干葉子結(jié)點，則T的葉結(jié)點數(shù)為______。

33．n（n大于1）個結(jié)點的各棵樹中，其深度最小的那棵樹的深度是_(1)__。它共有_(2)__個葉子結(jié)點和_(3)__個非葉子結(jié)點，其中深度最大的那棵樹的深度是_(4)__，它共有_(5)__個葉子結(jié)點和_(6)__個非葉子結(jié)點。

34．每一棵樹都能唯一的轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，對稱序列是FEBGCHD，則它的后序序列是_(1)__。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的先根次序序列是_(2)__。

35．先根次序周游樹林正好等同于按_(1)__周游對應(yīng)的二叉樹，后根次序周游樹林正好等同于按__(2)_周游對應(yīng)的二叉樹。36．二叉樹結(jié)點的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結(jié)點的前序序列為_(1)__,則該二叉樹對應(yīng)的樹林包括_(2)__棵樹。

37．二叉樹的先序序列和中序序列一致的條件是______。

38．已知一棵二叉樹的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹的根為_(1)__，左子樹中有_(2)__，右子樹中有_(3)__。

39．設(shè)二叉樹中每個結(jié)點均用一個字母表示，若一個結(jié)點的左子樹或右子樹為空，用．表示，現(xiàn)前序遍歷二叉樹，訪問的結(jié)點的序列為ABD.G...CE.H..F．．，則中序遍歷二叉樹時，訪問的結(jié)點序列為_(1)__;后序遍歷二叉樹時，訪問的結(jié)點序列為_(2)__。40．已知二叉樹前序為ABDEGCF，中序為DBGEACF，則后序一定是____。41．現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有_(1)__種不同的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是_(2)__。

42．一個無序序列可以通過構(gòu)造一棵______樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。

43．利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為______。

44．若一個二叉樹的葉子結(jié)點是某子樹的中序遍歷序列中的最終一個結(jié)點，則它必是該子樹的______序列中的最終一個結(jié)點。

45．先根次序周游樹林正好等同于按______周游對應(yīng)的二叉樹；后根次序周游樹林正好等同于______周游對應(yīng)的二叉樹。

46.在一棵存儲結(jié)構(gòu)為三叉鏈表的二叉樹中，若有一個結(jié)點是它的雙親的左子女，且它的雙親有右子女，則這個結(jié)點在后序遍歷中的后繼結(jié)點是______。47．一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個數(shù)為：______。

48．具有n個結(jié)點的滿二叉樹，其葉結(jié)點的個數(shù)是______。

49．設(shè)一棵后序線索樹的高是50，結(jié)點x是樹中的一個結(jié)點，其雙親是結(jié)點y,y的右子樹高度是31，x是y的左孩子。則確定x的后繼最多需經(jīng)過______中間結(jié)點（不含后繼及x本身）

50．線索二元樹的左線索指向其______，右線索指向其______。

51．設(shè)y指向二叉線索樹的一葉子，x指向一待插入結(jié)點，現(xiàn)x作為y的左孩子插入，樹中標(biāo)志域為ltag和rtag，并規(guī)定標(biāo)志為1是線索，則下面的一段算法將x插入并修改相應(yīng)的線索，試補(bǔ)充完整：(lchild,rchild分別代表左，右孩子)

x^.ltag:=(1)___;x^.lchild:=(2)___;y^.ltag:=(3)___;y^.lchild:=(4)___;x^.rtag:=(5)___;x^.rchild:=(6)___;

IF(x^.lchildNIL)AND(x^lchild^.rtag=1)THENx^.lchild^.rchild:=(7)___;52．哈夫曼樹是______。53．若以{4，5，6，7，8}作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是______。

54．有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，則所建Huffman樹的樹高是_(1)__，帶權(quán)路徑長度WPL為_(2)__。

55．有一份電文中共使用6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹，則其加權(quán)路徑長度WPL為_(1)__，字符c的編碼是_(2)__。56．設(shè)n0為哈夫曼樹的葉子結(jié)點數(shù)目，則該哈夫曼樹共有______個結(jié)點。

57．①二叉樹用來表示表達(dá)式，因為需要保存各子樹的值，修改二叉樹的結(jié)點結(jié)構(gòu)為(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意義同前，Val用來存放以該結(jié)點為根的子樹的值，值的類型依具體情況而定。為了簡便起見，算法假定所考慮的表達(dá)式只有+，-，*，/四種二目運(yùn)算，且已表示成相應(yīng)的二叉樹。算法所計算的表達(dá)式值放在根結(jié)點的Val域中。PROCPostorder-eval(t:ptrType)BEGINIF(t!=NULL)

BEGIN(1)_______;(2)_______;

CASEt^.data:

‘+’:t^.Val:=t^.Lchild^.Val+t^.Rchild^.Val;BREAK;

‘-’:t^.Val:=t^.Lchild^.Val-t^.Rchild^.Val;BREAK;‘*’:t^.Val:=t^.Lchild^.Val*t^.Rchild^.Val;BREAK;‘/’:t^.Val:=t^.Lchild^.Val/t^.Rchild^.Val;BREAK;otherwise:(3)___;BREAK;ENDCASEENDEND;

②PROCDelete(x:datatype,A:tree)BEGINtempA:=(4)___;

WHILE(tempA^.Item!=x)AND(tempA!=NULL)DO

IF(xrchild=(2)___;(3)___=q;

if(p->lchild)(4)___;if(p->rchild)(5)___;}

}}//

60．設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個兒子的結(jié)點個數(shù)N2;只有非空左兒子的個數(shù)NL;只有非空右兒子的結(jié)點個數(shù)NR和葉子結(jié)點個數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.typedefstructnode

{intdata;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node*t)

{if(t->lchild!=NULL)if(1)___N2++;elseNL++;

elseif(2)___NR++;else(3)__;

if(t->lchild!=NULL)(4)____;if(t->rchild!=NULL)(5)____;}/*callform:if(t!=NULL)count(t);*/

61．下面是求二叉樹高度的類PASCAL（注：編者略）及類C寫的遞歸算法試補(bǔ)充完整[說明]（1）考生可根據(jù)自己的狀況任選一個做（都選不給分)

（2）二叉樹的兩指針域為lchild與rchild,算法中p為二叉樹的根，lh和rh分別為以p為根

的二叉樹的左子樹和右子樹的高，hi為以p為根的二叉樹的高，hi最終返回。

height(p)

{if((1)___)

{if(p->lchild==null)lh=(2)_______;elselh=(3)_______;

if(p->rchild==null)rh=(4)_______;elserh=(5)_______;if(lh>rh)hi=(6)__；elsehi=(7)_______;}

elsehi=(8)_______;returnhi;

}//

62．二叉樹以鏈方式存儲，有三個域，數(shù)據(jù)域data，左右孩子域lchild,rchild。樹根由tree指向?，F(xiàn)要求按層次從上到下，同層次從左到右遍歷樹。下面算法中用到addx(p)，將指針p進(jìn)隊，delx()將隊頭元素返回并退隊，notempty在隊不空時返回true，否則為false，將算法補(bǔ)充完整:

PROCprocessnode(p);

IF(1)_______THEN[write(p＾.data);(2)_______]ENDP;

PROCtrave(tree);

write(tree＾.data);(3)_______;WHILEnotempty()DO

[r:=delx();processnode(r＾.lchild);processnode((4)_______)]ENDP;63閱讀以下程序說明和程序，填充程序中的______

本程序完成將二叉樹中左、右孩子交換的操作。交換的結(jié)果如下所示（編者略）。

本程序采用非遞歸的方法，設(shè)立一個堆棧stack存放還沒有轉(zhuǎn)換過的結(jié)點，它的棧頂指針為tp。交換左、右子樹的算法為：

（1）把根結(jié)點放入堆棧。

（2）當(dāng)堆棧不空時，取出棧頂元素，交換它的左、右子樹，并把它的左、右子樹分別入棧。（3）重復(fù)（2）直到堆棧為空時為止。typedefstructnode*tree;

structnode{intdata;treelchild,rchild;}exchange(treet)

{treer,p;treestack[500];inttp=0;(1)_______while(tp>=0)

{(2)_______

if((3)_______)

{r=p->lchild;p->lchild=p->rchild;p->rchild=r

stack[(4)_______]=p->lchild;stack[++tp]=p->rchild;

}

}}

64．下面使用類pascal語言寫的對二叉樹進(jìn)行操作的算法，請細(xì)心閱讀

TYPEpointer=^tnodetp;

tnodetp=RECORDdata:char;llink,rlink:pointer；END;linkstack=^linknodet;

linknodet=RECORDdata:pointer；next;linkstack；END;PROCunknown(VARt:pointer);VARp,temp：pointer;BEGINp:=t;

IFpNILTHEN

[temp:=p^.llink；p^.llink:=p^.rlink;；p^.rlink:=temp;unknown(p^.llink);unknown(p^.rlink);]

END;

①指出該算法完成了什么功能

②用棧將以上算法改為非遞歸算法unknown1,其中有若干語句或條件空缺請在空缺處填寫上適當(dāng)?shù)恼Z句或條件

>ch;//從ins順序讀入一個字符

while(ch!=‘#’){//逐個字符處理，直到遇到‘#’為止switch(ch){

case‘(’:(1)___；k=1;break;case‘)’:pop(s);break;case’,’:(2)___；break;

default:p=newBinTreeNode;(3)____;p->leftChild=NULL;p->rightChild=NULL;

if(BT==NULL)(4)___；elseif(k==1)top(s)->leftChild=p;elsetop(s)->rightChild=p;

}

(5)____;}}

67.判斷帶頭結(jié)點的雙向循環(huán)鏈表L是否對稱相等的算法如下所示，請在劃線處填上正確的語句

FUNCTIONequal(l:pointer):boolean;VARp,q:pointer;result:Boolean;

BEGINresult=true;p:=l^.link;q:=l^.pre;WHILE(pq)AND((1)_______)DO

IFp^.data=q^.dataTHENBEGIN(2)___;(3)____;END；ELSEresult=false;return(result);

END;

68．下列是先序遍歷二叉樹的非遞歸子程序，請閱讀子程序（C語言與PASCAL語言過程功能完全相同，任

選其一），填充空格，使其成為完整的算法。C語言函數(shù)：PASCAL語言過程voidexample(b)PROCEDUREexample(b:btree);btree*b;VARstack:ARRAY[1..20]OFbtree;{btree*stack[20],*p；top:integer;p:btree;inttop;BEGINif(b!=null)IFbNILTHEN{top=1;stack[top]=b;BEGINtop:=1;stack[top]:=b;while(top>0)WHILEtop>0DO{p=stack[top];top--;BEGINprintf(“%d〞,p->data);p:=stack[top];top:=top-1;if(p->rchild!=null)write(p^.data);{(1)___;(2)___;IFp^.rchildNIL}if(p->lchild!=null)(3)___;(4)__;}}}}THENBEGIN(1)__;(2)_;END;IFp^,lchildNILTHENBEGIN(3)__;4)__;ENDENDENDEND;69．下述是一個由二叉樹的前序序列和中序序列構(gòu)造該二叉樹的算法，其中，數(shù)組A[1..n]存放前序序列，數(shù)組B[1..n]存放中序序列，s為根結(jié)點指針，i,j為樹s的前序序列在A[1..n]中的開始位置和結(jié)束位置，x,y為樹s的中序序列在B[1..n]中的開始位置和結(jié)束位置。所生成的二叉樹采用二叉鏈表存儲結(jié)構(gòu)，其結(jié)點的形式為（lchild,data,rchild）。請在算法的空框中填入適當(dāng)語句，使其成為一個完整的算法。PROCEDUREcreatBT(i,j,x,y:integer;VARs:link);VARk,L:integer;BEGINs:=NIL;

IF(1)__THEN

BEGINnew(s);s^.data:=a[i];k:=x;WHILE(2)_______DOk:=k+1;L:=(3)____;IFk=xTHENs^.lchild:=NIL;ELSE(4)_______;IFk=yTHENs^.rchild:=NIL;ELSE(5)_______；END

END;

70．已知中序遍歷bt所指二叉樹算法如下，s為存儲二叉樹結(jié)點指針的工作棧，請在劃線處填入一條所缺語句。

PROCinorder(bt:bitreptr);inistack(s);(1)_______;WHILENOTempty(s)DO

[WHILEgettop(s)NILDOpush(s,gettop(s)↑.lchild);(2)_______;

IFNOTempty(s)THEN[visit(gettop(s)^);p:=pop(s);(3)_______]]ENDP;{inorder}

71．以下程序是二叉鏈表樹中序遍歷的非遞歸算法，請?zhí)羁帐怪晟啤６鏄滏湵淼慕Y(jié)點類型的定義如下：typedefstructnode/*C語言/

{chardata;structnode*lchild,*rchild;}*bitree;

voidvst(bitreebt)/*bt為根結(jié)點的指針*/{bitreep;p=bt;initstack(s);/*初始化棧s為空棧*/

while(p||!empty(s))/*棧s不為空*/if(p){push(s,p);(1)___;}/*P入棧*/

else{p=pop(s);printf(“%c〞,p->data);(2)____;}/*棧頂元素出棧*/}

72．二叉樹存儲結(jié)構(gòu)同上題，以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦?/p>

intdepth(bitreebt)/*bt為根結(jié)點的指針*/{inthl,hr;

if(bt==NULL)return((1)___);

hl=depth(bt->lchild);hr=depth(bt->rchild);if((2)___)(3)_____；return(hr+1);

}

73．n個結(jié)點的完全二叉樹存儲在數(shù)組a中，下面為非遞歸的先序遍歷算法。

PROCpreorder(a);BEGINtop:=0;t:=1;

WHILE(t0THENBEGINt:=s[top]*2+1;top:=(3)__;END;END;

END;

74．后序遍歷二叉樹的非遞歸算法，bt是二叉樹的根，S是一個棧，maxsize是棧的最大容量。

TYPEbitreptr=^bnodetp;

bnodetp=RECORDdata:datatype;lchild,rchild:bitreptrEND;

TYPEstacktyp=RECORDdata:ARRAY[1..maxsize]OFbitreptr；top：0..maxsize；END；PROCEDUREposterorder（bt：bitreptr）；BEGINS.top:=0；p:=bt；REPEAT

WHILEpNILDOBEGINS.top:=S.top+1;IFS.top>maxsizeTHENstackfull

ELSEBEGINS.data[S.top]:=p；(1)__;END

END;

IFS.data[S.top]^.rchildNILTHEN(2)__

ELSEBEGINREPEATwrite(S.data[S.top]^.data);S.top=S.top-1;UNTILS.top=0ORS.data[S.top]^.rchildS.data[S.top+1];IFS.data[S.top]^.rchildS.data[S.top+1]THEN(3)__;

END；

UNTIL(4)___;

END；

75．由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。

#defineMAX100typedefstructNode

{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv)

{TNODE*root;

if(argcinfo=(1)_______;

for((2)_______;rposllink=restore(ppos+1,(4)_______,k);

ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}

postorder(TNODE*ptr){if(ptr=NULL)return;

postorder(ptr->llink);postorder(ptr->rlink);printf(“%c〞,ptr->info);}76．已給如下關(guān)于二叉樹的類型說明：

TYPEtree=^node;

node=RECORDdata:integer;left,right:treeEND;以下過程實現(xiàn)對二叉樹t前序遍歷的非遞歸算法：

PROCEDUREpreorder(t:tree);

VARstack:ARRAY[1..100]OFtree;nd:tree;top:integer;

BEGINtop:=1;stack[top]:=t;WHILE(1)___DO

BEGINnd:=stack[top];top:=top-1;write(nd^.data);

IF(nd^.rightNIL)THENBEGINtop:=top+1;(2)___END;

IF(3)___THENBEGIN(4)；stack[top]:=nd^.left；ENDEND

END;

77．下面是中序線索樹的遍歷算法，樹有頭結(jié)點且由指針thr指向。樹的結(jié)點有五個域，分別為數(shù)據(jù)域data，

左、右孩子域lchild、rchild和左、右標(biāo)志域ltag,rtag。規(guī)定，標(biāo)志域為1是線索，O是指向孩子的指針。

inordethread(thr){p=thr->lchild;while((1)______)

{while((2)_____)p=(3)___;

printf(p->data);

while((4)_________){p=(5)___；printf(p->data);}p=(6)_;}

}

78．下面的算法在中序線索樹中找由指針?biāo)附Y(jié)點的后繼并由指針指向該后繼結(jié)點，試補(bǔ)充完整（線索樹的結(jié)點有五個域data,lchild,rchild,左、右標(biāo)志域ltag、rtag，并規(guī)定標(biāo)志0指向孩子，1指向線索。

PROCinorder_next(p);(1)__;

IFp＾.rtag=0THENWHILE(2)____DOq:=(3)___；return(q)ENDP;

79．線索二叉樹有數(shù)據(jù)域data，左右孩子域lchild和rchild，左右標(biāo)志ltag及rtag，規(guī)定標(biāo)志為1對應(yīng)的孩子域是線索，0則為指向孩子的指針。規(guī)定在儲存線索二叉樹時，完成下面中序線索化過程。（存儲線索二叉樹，不增加頭結(jié)點，只在原有的由tree指向的二叉樹中增加線索，此處也不考慮c語言的具體語法與約定，線索化前所有的標(biāo)志tag都是0）。

/*pre是同tree類型一致的指針，初值是null*/thread_inorder(tree){if(tree!=null)

{thread_inorder((1)____);

if(tree->lchild==(2)______){tree->ltag=1;tree->lchild=pre;}if((3)___==null){(4)_______;(5)_______;}

pre=p;thread-inorder((6)_______);

}

}

80．如下的算法分別是后序線索二叉樹求給定結(jié)點node的前驅(qū)結(jié)點與后繼結(jié)點的算法，請在算法空格處填上正確的語句。設(shè)線索二叉樹的結(jié)點數(shù)據(jù)結(jié)構(gòu)為(lflag,left,data,right,rflag)，其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驅(qū)；rflag=0，right指向其右孩子，rflag=1，right指向其后繼。

prior(node,x)

{if(node!=null)

if((1)_____)*x=node->right;else*x=node->left;}

next(bt,node,x)/*bt是二叉樹的樹根*/{(2)_____;

if(node!=bt(4)_______;while(*x==node);*x=t;}}

四、應(yīng)用題

1．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。

2．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？3．請分析線性表、樹、廣義表的主要結(jié)構(gòu)特點，以及相互的差異與關(guān)聯(lián)。

4.設(shè)有一棵算術(shù)表達(dá)式樹，用什么方法可以對該樹所表示的表達(dá)式求值？5．將算術(shù)表達(dá)式（（a+b）+c*(d+e)+f）*(g+h)轉(zhuǎn)化為二叉樹。6.一棵有n(n>0)個結(jié)點的d度樹,若用多重鏈表表示,樹中每個結(jié)點都有d個鏈域,則在表示該樹的多重鏈表中有多少個空鏈域?為什么?

7.一棵二叉樹中的結(jié)點的度或為0或為2，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點的個數(shù)。

類似此題的另外表達(dá)有：

（1）若二叉樹中度為1的結(jié)點數(shù)為0，則該二叉樹的總分支數(shù)為2（n0-1），其中n0為葉結(jié)點數(shù)。

8．一個深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有K棵非空子樹，假使按層次順序從1開始對全部結(jié)點進(jìn)行編號，求：

1）各層的結(jié)點的數(shù)目是多少？2）編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是多少？3）編號為n的結(jié)點的第i個孩子結(jié)點（若存在）的編號是多少？

4）編號為n的結(jié)點有右兄弟的條件是什么？假使有，其右兄弟的編號是多少？請給出計算和推導(dǎo)過程。

類似此題的另外表達(dá)有：（1）一棵高度為h的滿k叉樹有如下性質(zhì)：根據(jù)結(jié)點所在層次為0；第h層上的結(jié)點都是葉子結(jié)點；其余各層上每個結(jié)點都有k棵非空子樹，假使按層次自頂向下，同一層自左向右,順序從1開始對全部結(jié)點進(jìn)行編號，試問：

1)各層的結(jié)點個數(shù)是多少?(3分)2)編號為i的結(jié)點的雙親結(jié)點（若存在）的編號是多少?(3分)3)編號為i的結(jié)點的第m個孩子結(jié)點（若存在）的編號是多少？（3分）

4)編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟結(jié)點的編號是多少？（3分)

9．證明任一結(jié)點個數(shù)為n的二叉樹的高度至少為O(logn).10．有n個結(jié)點并且其高度為n的二叉樹的數(shù)目是多少?

11．已知完全二叉樹的第七層有10個葉子結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是多少？

12．高度為10的二叉樹，其結(jié)點最多可能為多少？

13．任意一個有n個結(jié)點的二叉樹，已知它有m個葉子結(jié)點，試證明非葉子結(jié)點有（m-1）個度為2，其余度為1。

14.已知A[1..N]是一棵順序存儲的完全二叉樹，如何求出A[i]和A[j]的最近的共同祖先？

15．給定K(K>=1),對一棵含有N個結(jié)點的K叉樹（N＞０）、請?zhí)接懫淇赡艿淖畲蟾叨群妥钚「叨取?/p>

16．已知一棵滿二叉樹的結(jié)點個數(shù)為20到40之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？

17．一棵共有n個結(jié)點的樹，其中所有分支結(jié)點的度均為K，求該樹中葉子結(jié)點的個數(shù)。

18．如在內(nèi)存中存放一個完全二叉樹，在樹上只進(jìn)行下面兩個操作：（1）尋覓某個結(jié)點雙親（2）尋覓某個結(jié)點的兒子；

請問應(yīng)當(dāng)用何種結(jié)構(gòu)來存儲該二叉樹？

19．求含有n個結(jié)點、采用順序存儲結(jié)構(gòu)的完全二叉樹中的序號最小的葉子結(jié)點的下標(biāo)。要求寫出簡要步驟。

20．設(shè)二叉樹T中有n個頂點，其編號為1，2，3，?,n,若編號滿足如下性質(zhì)：（1）T中任一頂點v的編號等于左子樹中最我號減1；

（2）對T中任一頂點v,其右子樹中最我號等于其左子樹中的最大編號加1。試說明對二叉樹中頂點編號的規(guī)則（按何種順序編號）。

21．若一棵樹中有度數(shù)為1至m的各種結(jié)點數(shù)為n1,n2,?,nm(nm表示度數(shù)為m的結(jié)點個數(shù))請推導(dǎo)出該樹中共有多少個葉子結(jié)點n0的公式。

22．若一棵完全二叉樹中葉子結(jié)點的個數(shù)為n,且最底層結(jié)點數(shù)≧2，則此二叉樹的深度H=？

23．已知完全二叉樹有30個結(jié)點，則整個二叉樹有多少個度為0的結(jié)點？

24．在一棵表示有序集S的二叉探尋樹(binarysearchtree)中,任意一條從根到葉結(jié)點的路徑將S分為3部分：在該路徑左邊結(jié)點中的元素組成的集合Sl；在該路徑上的結(jié)點中的元素組成的集合S2；在該路徑右邊結(jié)點中的元素組成的集合S3。S=S1∪S2∪S3。若對于任意的a∈Sl,b∈S2，c∈S3是否總有a≤b≤c?為什么?

25．試證明,在具有n(n>=1)個結(jié)點的m次樹中,有n(m-1)+1個指針是空的。26．對于任何一棵非空的二叉樹,假設(shè)葉子結(jié)點的個數(shù)為n0,而次數(shù)為2的結(jié)點個數(shù)為n2,請給出n0和n2之間所滿足的關(guān)系式n0=f(n2).要求給出推導(dǎo)過程。

27．對于任意一棵非空的二叉樹T，我們用n0表示T中葉子結(jié)點的個數(shù)，用n2表示T中有兩棵非空子樹的結(jié)點的個數(shù)。（1）給出n0和n2所滿足的關(guān)系式。（2）證明你在（1）中給出的關(guān)系式成立。

28．試求有n個葉結(jié)點的非滿的完全二叉樹的高度;29．對于具有n個葉子結(jié)點，且所有非葉子結(jié)點都有左右孩子的二叉樹，(1)試問這種二叉樹的結(jié)點總數(shù)是多少？（5分）

(2)試證明=1。其中:li表示第i個葉子結(jié)點所在的層號(設(shè)根結(jié)點所在層號為1)。(10分)

30．假設(shè)高度為H的二叉樹上只有度為0和度為2的結(jié)點，問此類二叉樹中的結(jié)點數(shù)可能達(dá)到的最大值和最小值各為多少？

31．一棵滿k叉樹，按層次遍歷存儲在一維數(shù)組中，試計算結(jié)點下標(biāo)的u的結(jié)點的第i個孩子的下標(biāo)以及結(jié)點下標(biāo)為v的結(jié)點的父母結(jié)點的下標(biāo)。

32．二叉樹有n個頂點，編號為1，2，3，?，n，設(shè)：*T中任一頂點V的編號等于左子樹中最我號減1；

*T中任一頂點V的右子樹中的最我號等于其左子樹中的最大編號加1；試描繪該二叉樹。

33．設(shè)T是具有n個內(nèi)結(jié)點的擴(kuò)展二叉樹，I是它的內(nèi)路徑長度，E是它的外路徑長度。（1）試?yán)脷w納法證明E=I+2n,n>=0.（5分)

（2）利用（1）的結(jié)果試說明：成功查找的平均比較次數(shù)s與不成功查找的平均比較次數(shù)u之間的關(guān)系可用公式表示s=(1+1/n)u-1,n>=1。

34．一棵非空的有向樹中恰有一個頂點入度為0,其它頂點入度為1,但一個恰有一個頂點入度為0,

其它頂點入度為1的有向圖卻不一定是一棵有向樹,請舉例說明。

35．試給出以下有關(guān)并查集（mfsets）的操作序列的運(yùn)算結(jié)果：

union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9),union(1,8),union(3,10),union(3,11),union(3,12),union(3,13),union(14,15),union(16,0),union(14,16),union(1,3),union(1,14).

(union是合并運(yùn)算，在以前的書中命名為merge)

要求

（1）對于union(i,j),以i作為j的雙親；（5分)

（2）按i和j為根的樹的高度實現(xiàn)union(i,j),高度大者為高度小者的雙親；（5分)（3）按i和j為根的樹的結(jié)點個數(shù)實現(xiàn)union(i,j),結(jié)點個數(shù)大者為結(jié)點個數(shù)小者的雙親。（5分)

36．證明：在任何一棵非空二叉樹中有下面的等式成立：葉結(jié)點的個數(shù)=二度結(jié)點的個數(shù)+1

37.對于一個堆棧，若其入棧序列為1，2，3，?，n，不同的出入棧操作將產(chǎn)生不同的出棧序列。其出棧序列的個數(shù)正好等于結(jié)點個數(shù)為n的二叉樹的個數(shù)，且與不同形態(tài)的二叉樹一一對應(yīng)。請簡要表達(dá)一種從堆棧輸入（固定為1，2，3??n）/輸出序列對應(yīng)一種二叉樹形態(tài)的方法，并以入棧序列1，2，3（即n=3）為例加以說明。

38.假使給出了一個二叉樹結(jié)點的前序序列和對稱序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。假使給出了一個二叉樹結(jié)點的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。

類似此題的另外表達(dá)有：

（1）二叉樹的中序與后序序列能唯一地定義一棵二叉樹嗎?這里所指序列中的符號代表樹結(jié)點中的標(biāo)識符嗎？二叉樹的前序與后序序列能唯一地定義一棵二叉樹嗎?為什么?

39．試證明:同一棵二叉樹的所有葉子結(jié)點，在前序序列。對稱序序列以及后序序列中都按一致的相對位置出現(xiàn)（即先后順序一致），例如前序abc,后序bca對稱序bac。

40.由二叉樹的中序序列及前序序列能唯一的建立二叉樹，試問中序序列及后序序列是否也能唯一的建立二叉樹，不能則說明理由，若能對中序序列DBEAFGC和后序序列DEBGFCA構(gòu)造二叉樹。

41.證明，由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。設(shè)一棵二叉樹的前序序列為ABDGECFH，中序序列為：DGBEAFHC。試畫出該二叉樹。類似此題的另外表達(dá)有：

(1)證明：由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。

（2）證明：由二叉樹的中序遍歷序列和后序遍歷序列可唯一地確定出該二叉樹。

（3）二叉樹已知其中序掃描序列和后序掃描序列如何確定這一棵二叉樹,并舉例說明.

42．試證明：僅僅已知一棵二叉樹的后序遍歷序列和先序遍歷序列，不能唯一地確定這棵二叉樹。類似此題的另外表達(dá)有：

(1)由二叉樹的前序遍歷和后序遍歷結(jié)果能否唯一確定一棵二叉樹？解釋你的論斷。

(2)假定某二叉樹的前序遍歷序列為ABCDEFGHIJ,后序遍歷序列為CEFDBJIHGA,據(jù)此兩個序列能否唯一確定此二叉樹?若不能,試畫出兩樣具有同樣上述遍歷序列的二叉樹.

43.①試找出滿足以下條件的二叉樹

1）先序序列與后序序列一致2）中序序列與后序序列一致

3）先序序列與中序序列一致4）中序序列與層次遍歷序列一致

②已知一棵二叉樹的中序序列和后序序列分別為DBEAFIHCG和DEBHIFGCA，畫出這棵二叉樹。

類似此題的另外表達(dá)有：（1）試畫出在先根次序和中根次序下結(jié)點排列順序皆一致的所有類型的二叉樹形。

試畫出在先根次序和后根次序下結(jié)點排列順序皆一致的所有類型的二叉樹形。

（2）找出所有的二叉樹，其結(jié)點在以下兩種遍歷下恰好都有同樣的遍歷序列。

1）先序遍歷和中序遍歷2）先序遍歷和后序遍歷（3）找出所有的二叉樹，其結(jié)點在以下兩種遍歷下，恰好都是以同樣的順序出現(xiàn)：

1）前序遍歷和中序遍歷。2）前序遍歷和后序遍歷。（4）試找出分別滿足以下條件的所有二叉樹。

1）先序序列和中序序列一致2）中序序列和后序序列一致3）先序序列和后序序列一致（5）找出所有滿足以下條件的二叉樹：

1）它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列一致；2）它們在后序遍歷和中序遍歷時，得到的結(jié)點訪問序列一致；3）它們在先序遍歷和后序遍歷時，得到的結(jié)點訪問序列一致；44．將以下由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）

ABCDEFKHLGIJMNO

P

45.閱讀以下說明和流程圖，回復(fù)問題（1）和問題（2）。

說明：流程圖是用來實現(xiàn)中序遍歷，二叉樹存放在數(shù)組tree中，每個數(shù)組元素存放樹中一個結(jié)點，每個

結(jié)點的形式為（值，左指針，右指針），分別用tree[i].v，tree[i].l，tree[i].r來表示第i個結(jié)點的值，左指針，右指針，其中左，右指針的值為所指結(jié)點在數(shù)組中的下標(biāo)，若指針的值為0，表示它指向空樹，圖中指針root用以指向二叉樹的根結(jié)點。問題：

（1）填充流程圖中的①、②、③，使其按中序遍歷二叉樹。

（2）把流程圖中的（A）框移至哪個位置（圖中Ⅰ～Ⅸ）使流程圖的算法從中序遍歷變成后序遍歷。

46．設(shè)一棵二叉樹的先序、中序遍歷序列分別為

先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC（1）畫出這棵二叉樹。

（2）畫出這棵二叉樹的后序線索樹。（3）將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。47．已知一棵二叉樹的對稱序和后序序列如下：對稱序：GLDHBEIACJFK后序：LGHDIEBJKFCA(1)（2分)給出這棵二叉樹：(2)（2分)轉(zhuǎn)換為對應(yīng)的森林：

(3)（4分)畫出該森林的帶右鏈的先根次序表示法：

Itag=

(4)(4分)畫出該森林帶度數(shù)的后根次序表示法：

(5)(4分)在帶度數(shù)的后根次序表示法中，不包含指針，但仍能完全反映樹的結(jié)構(gòu)。寫出以結(jié)點x為根的子樹在后根次序序列中的前驅(qū)的求法。（用語言表達(dá)，不用寫算法）

48．設(shè)某二叉樹的前序遍歷序列為:ABCDEFGGI，中序遍歷序列為:BCAEDGHFI：（1）試畫出該二叉樹；

（2）寫出由給定的二叉樹的前序遍歷序列和中序遍歷序列構(gòu)造出該二叉樹的算法。

（3）設(shè)具有四個結(jié)點的二叉樹的前序遍歷序列為ａｂｃｄ；Ｓ為長度等于四的由ａ，ｂ，ｃ，ｄ排列構(gòu)成的字符序列，若任?。幼鳛樯鲜鏊惴ǖ闹行虮闅v序列，試問是否一定能構(gòu)造出相應(yīng)的二叉樹，為什么？試列出具有四個結(jié)點二叉樹的全部形態(tài)及相應(yīng)的中序遍歷序列。

類似此題的另外表達(dá)有：（1）已知二叉樹的先序序列:CBHEGAF,中序序列:HBGEACF,試構(gòu)造該二叉樹

（2）已知二叉樹按中序排列為BFDAEGC，按前序排列為ABDFCEG，要求畫出該二叉樹。

（3）已知一棵二叉樹的前序序列A,B,D,C,E,F，中序序列B,D,A,E,F,C.畫出這棵二叉樹。

（4）已知一棵二叉樹的前序遍歷結(jié)果是：ABCDEFGHIJ,中序遍歷的結(jié)果是：BCEDAGHJIF,試畫出這棵二叉樹。

（5）已知二叉樹BT各結(jié)點的先序、中序遍歷序列分別為ABCDEGF和CBAEDF，試畫出該二叉樹。

49.假設(shè)一棵二叉樹的前序序列為ABCD,它的中序序列可能是DABC嗎?

類似此題的另外表達(dá)有：（1）一棵前序序列為1，2，3，4，的二叉樹，其中序序列可能是4，1，2，3嗎？設(shè)一棵二叉樹的前序序列為1，2，3，4，5，6，7，8，9，其中序序列為2，3，1，5，4，7，8，6，9，試畫出該二叉樹。

50．一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二叉樹的形狀。

51．已知一棵二叉樹的后序遍歷序列為EICBGAHDF，同時知道該二叉樹的中序遍歷序列為CEIFGBADH，試畫出該二叉樹。

類似此題的另外表達(dá)有：（1）已知二叉樹ＢＴ各結(jié)點的中序和后序序列分別為ＤＦＢＡＣＥＧ和ＦＤＢＧＥＣＡ，試構(gòu)造出該二叉樹ＢＴ，并作簡要說明。

（2）已知二叉樹的中序遍歷序列為GFBEANHM，后序遍歷的結(jié)點序列為GEBFHNMA，畫出此二叉樹的形態(tài)。

（3）已知二叉樹的后序序列為ABCDEFG和中序序列為ACBGEDF，構(gòu)造出該二叉樹。

（4）已知某二叉樹的后序遍歷和中序遍歷如下，構(gòu)造出該二叉樹。

后序遍歷序列：GDBEIHFCA中序遍歷序列：DGBAECHIF

（1）求出二叉樹的高度。

（2）求出每個結(jié)點的層號（根結(jié)點層號為1），并填入D(i)中。（可采用任何高級語言，但要注明你所采用的語言名稱）。

h

9．已知深度為h的二叉樹采用順序存儲結(jié)構(gòu)已存放于數(shù)組BT[1:2-1]中，請寫一非遞歸算法，產(chǎn)生該二叉樹的二叉鏈表結(jié)構(gòu)。設(shè)二叉鏈表中鏈結(jié)點的構(gòu)造為(lchild,data,rchild),根結(jié)點所在鏈結(jié)點的指針由T給出。

10.二叉樹的動態(tài)二叉鏈表結(jié)構(gòu)中的每個結(jié)點有三個字段：data，lchild，rchild。其中指針lchild

下標(biāo)datalchildrchild1ABCEDFG234567ABCDEFG23050006400070和rchild的類型為bitre。靜態(tài)二叉鏈表是用數(shù)組作為存儲空間，每個數(shù)組元素存儲二叉樹的一個結(jié)點，也有三個字段：data，lchild，rchild。所不同的是，lchild和rdhild為integer型，分別用于存儲左右孩子的下標(biāo)，假使沒有左右孩子，則相應(yīng)的值為0。例如，下面左圖所示的二叉樹的靜態(tài)二叉鏈表如右圖所示。

編寫算法由二叉樹的動態(tài)二叉鏈表構(gòu)造出相應(yīng)的靜態(tài)二叉鏈表a[1..n]，并寫出其調(diào)用形式和有關(guān)的類型描述。其中n為一個確定的整數(shù)。

11．假設(shè)以雙親表示法作樹的存儲結(jié)構(gòu)，寫出雙親表示的類型說明，并編寫求給定的樹的深度的算法。（注:已知樹中結(jié)點數(shù)）

12．試編寫算法求出二叉樹的深度。二叉樹的存儲結(jié)構(gòu)為如下說明的二叉鏈表:TYPEbtre=↑bnode

bnode=RECORDdata:datatype;lch,rch:btreEND;13．二叉樹采用二叉鏈表存儲：

（1）編寫計算整個二叉樹高度的算法（二叉樹的高度也叫二叉樹的深度）。

（2）編寫計算二叉樹最大寬度的算法（二叉樹的最大寬度是指二叉樹所有層中結(jié)點個數(shù)的最大值）。

14．以孩子兄弟鏈表為存儲結(jié)構(gòu)，請設(shè)計遞歸和非遞歸算法求樹的深度。

類似此題的另外表達(dá)有：

（1）設(shè)T是一棵n元樹，Tb是T的孩子兄弟表示（二叉鏈表）的二叉樹，試編程，由Tb計算T的高度（要求用非遞歸方法實現(xiàn)）。

15．設(shè)一棵二叉樹的結(jié)點結(jié)構(gòu)為(LLINK,INFO,RLINK),ROOT為指向該二叉樹根結(jié)點的指針，p和q分別為指向該二叉樹中任意兩個結(jié)點的指針，試編寫一算法ANCESTOR（ROOT，p,q,r）,該算法找到p和q的最近共同祖先結(jié)點r。

16．已知一棵二叉樹按順序方式存儲在數(shù)組A[1..n]中。設(shè)計算法，求出下標(biāo)分別為i和j的兩個結(jié)點的最近的公共祖先結(jié)點的值。

17．設(shè)計這樣的二叉樹，用它可以表示父子、夫妻和兄弟三種關(guān)系，并編寫一個查找任意父親結(jié)點的所有兒子的過程。

18．在二叉樹中查找值為x的結(jié)點，試編寫算法（用C語言）打印值為x的結(jié)點的所有祖先，假設(shè)值為x的結(jié)點不多于一個，最終試分析該算法的時間繁雜度（若不加分析，直接寫出結(jié)果，按零分算）。

類似此題的另外表達(dá)有：

（1）在二叉樹中查找值為x的結(jié)點，請編寫一算法用以打印值為x的結(jié)點的所有祖先，假設(shè)值為x的結(jié)點不多于1個。注：采用非遞歸算法。

（2）設(shè)二叉樹中結(jié)點的數(shù)據(jù)域的值互不一致，試設(shè)計一個算法將數(shù)據(jù)域值為x的結(jié)點的所有祖先結(jié)點的數(shù)據(jù)域打印出來。

（3）設(shè)二叉樹根指針為t,且樹中結(jié)點值各不一致，寫出算法disp_f(t,x),查找樹中值為t的結(jié)點，并顯示出其所有祖先結(jié)點的值。

A（4）若一棵二叉樹中沒有數(shù)據(jù)域值一致的結(jié)點，設(shè)計算法

BC打印數(shù)據(jù)域值為x的所有祖先結(jié)點的數(shù)據(jù)域。假使根結(jié)點的ADE數(shù)據(jù)域值為x或不存在數(shù)據(jù)域值為x的結(jié)點，則什么也不打CB印。例如右圖所示的二叉樹，則打印結(jié)點序列為A、C、E。FGXFDEHI19．利用棧的基本操作寫出先序遍歷二叉樹的非遞歸算法

GHI要求進(jìn)棧的元素最少，并指出以下(最右圖)二叉樹中需進(jìn)棧18(4)題圖

K的元素。

20．設(shè)一棵完全二叉樹使用順序存儲在數(shù)組bt[1..n]中,請寫19題圖出進(jìn)行非遞歸的前序遍歷算法。

21．若二叉樹用以下存儲結(jié)構(gòu)表示，試給出求前序遍歷的算法：

TYPETree:=ARRAY[1..max]OFRECORDdata:char;parent:integer;END;A下標(biāo)123456C數(shù)據(jù)DCABBEF父母-5302E-3-2DF

22．設(shè)計算法返回二叉樹T的先序序列的最終一個結(jié)點的指針，要求采用非遞歸形式，且不許用棧。

23．已知一棵高度為Ｋ具有ｎ個結(jié)點的二叉樹，按順序方式存儲：（1）編寫用先根遍歷樹中每個結(jié)點的遞歸算法；

（2）編寫將樹中最大序號葉子結(jié)點的祖先結(jié)點全部打印輸出的算法。。24．對于二叉樹的鏈接實現(xiàn),完成非遞歸的中序遍歷過程。類似此題的另外表達(dá)有：

（1）寫出中序遍歷二叉樹的非遞歸算法及遞推算法。。（2）設(shè)計一個中序遍歷算法，應(yīng)用棧來存儲樹結(jié)點，要求結(jié)點僅能進(jìn)棧和出棧一次。（此題指中序遍歷二叉樹）（3）用非遞歸方式寫出二叉樹中序遍歷算法。25．已知二叉樹用下面的順序存儲結(jié)構(gòu)，寫出中序遍歷該二叉樹的算法。TYPEARRAY[1..maxn]OFRECORDdata:char;//存儲結(jié)點值

Lc,Rc;integer;END;//存左孩子右孩子的下標(biāo)，0表示無左、右孩子。123456789dataABCDEFGHILc240008000Rc356079000如樹T=A（B（D，E,(#,G)），C（#，F(xiàn)（H，I）））存儲如上圖。

26．試給出二叉樹的自下而上、自右而左的層次遍歷算法。

27．在一棵以二叉鏈表表示的二叉樹上，試寫出用按層次順序遍歷二叉樹的方法，統(tǒng)計樹中具有度為1的結(jié)點數(shù)目的算法。二叉鏈表的類型定義為：

TYPEbitreptr=^bnodetp;

bnodetp=RECORDdata:char;lchild,rchild:bitreptrEND;

類似此題的另外表達(dá)有：

（1）請設(shè)計算法按層次順序遍歷二叉樹。（2）試以二叉鏈表作存儲結(jié)構(gòu)，編寫按層次順序遍歷二叉樹的算法。（3）已知一棵以二叉鏈表作存儲結(jié)構(gòu)的二叉樹，編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。

（4）設(shè)二叉樹用二叉鏈表存儲，試編寫按層輸出二叉樹結(jié)點的算法。（5）寫出按層次順序打印任意二叉樹T中結(jié)點的程序。二叉樹采用雙鏈結(jié)構(gòu)，結(jié)點形式為（LSON，DATA，RSON）可采用任何你熟悉的算法語言，設(shè)T指向二叉樹的根結(jié)點。

28．設(shè)一棵二叉樹以二叉鏈表為存貯結(jié)構(gòu)，結(jié)點結(jié)構(gòu)為(lchild,data,rchild)，設(shè)計一個算法將二叉樹中所有結(jié)點的左，右子樹相互交換。

類似此題的另外表達(dá)有：

（1）設(shè)t為一棵二叉樹的根結(jié)點地址指針，試設(shè)計一個非遞歸的算法完成把二叉樹中每個結(jié)點的左右孩子位置交換。

（2）寫一個將二叉樹中每個結(jié)點的左右孩子交換的算法。（統(tǒng)考生做）29．設(shè)T是一棵滿二叉樹，編寫一個將T的先序遍歷序列轉(zhuǎn)換為后序遍歷序列的遞歸算法。

30．已知一棵二叉樹的中序序列和后序序列，寫一個建立該二叉樹的二叉鏈表存儲結(jié)構(gòu)的算法。

31．設(shè)二叉樹采用二叉鏈表作為存儲結(jié)構(gòu)。試用類PASCAL語言實現(xiàn)按前序遍歷順序輸出二叉樹中結(jié)點的非遞歸算法。要求定義所