第六章樹和二叉樹習題_數(shù)據(jù)結(jié)構(gòu)

1、習題六 樹和二叉樹一、單項選擇題1 以下說法錯誤的是 ( )A樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前趨B線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼C樹形結(jié)構(gòu)可以表達(組織)更復雜的數(shù)據(jù)D樹(及一切樹形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)E任何只含一個結(jié)點的集合是一棵樹2下列說法中正確的是 ( )A任何一棵二叉樹中至少有一個結(jié)點的度為2B任何一棵二叉樹中每個結(jié)點的度都為2C任何一棵二叉樹中的度肯定等于2D任何一棵二叉樹中的度可以小于23討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）A借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B將樹、森林按二叉樹的存儲方式進行存儲C將樹、森林轉(zhuǎn)換成二叉樹

2、D體現(xiàn)一種技巧，沒有什么實際意義4樹最適合用來表示 ( )A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之間無聯(lián)系的數(shù)據(jù)5若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ ）A9 B11 C15 D不確定 6設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（ ）。AM1 BM1+M2 CM3 DM2+M37一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）A 250 B 500 C254 D505 E以上答案都不對 8. 設(shè)給定權(quán)值總數(shù)有n 個，其哈夫曼樹的結(jié)

3、點總數(shù)為( ) A不確定 B2n C2n+1 D2n-19二叉樹的第I層上最多含有結(jié)點數(shù)為（ ）A2I B 2I-1-1 C 2I-1 D2I -110一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有( )結(jié)點A2h B2h-1 C2h+1 Dh+1 11. 利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空14在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（ ）A都不相同 B完全相同 C先序和中序相同，而與后序不同 D中序和后序相同，而與先序不同 15在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒（ ）。A左子結(jié)點

4、B右子結(jié)點 C左子結(jié)點和右子結(jié)點 D左子結(jié)點，右子結(jié)點和兄弟結(jié)點16在下列情況中，可稱為二叉樹的是（ ）A每個結(jié)點至多有兩棵子樹的樹 B. 哈夫曼樹 C每個結(jié)點至多有兩棵子樹的有序樹 D. 每個結(jié)點只有一棵右子樹 E以上答案都不對 17. 一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：( )。A. 0 B. 1 C. 2 D. 不確定 18. 引入二叉線索樹的目的是（ ）A加快查找結(jié)點的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一19n個結(jié)點的線索二叉樹上含有的線索數(shù)為（ ）A2n Bnl Cnl Dn 21下面幾個

5、符號串編碼集合中，不是前綴編碼的是（ ）。A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc 22. 一棵有n個結(jié)點的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A1.n中，則二叉樹中第i個結(jié)點（i從1開始用上述方法編號）的右孩子在數(shù)組A中的位置是（ ）AA2i(2i<=n) BA2i+1(2i+1<=n) CAi-2 D條件不充分，無法確定23、以下說法錯誤的是 ( )A哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。B若一個二叉樹的樹葉是某子樹的中序遍歷

6、序列中的第一個結(jié)點，則它必是該子樹的后序遍歷序列中的第一個結(jié)點。C已知二叉樹的前序遍歷和后序遍歷序列并不能惟一地確定這棵樹，因為不知道樹的根結(jié)點是哪一個。D在前序遍歷二叉樹的序列中，任何結(jié)點的子樹的所有結(jié)點都是直接跟在該結(jié)點的之后。二、判斷題（在各題后填寫“”或“×”）1. 完全二叉樹一定存在度為1的結(jié)點。( )2對于有N個結(jié)點的二叉樹，其高度為log2n。( )3. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。( )4. 一棵一般樹的結(jié)點的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點前序遍歷和后序遍歷是一致的。( )5. 用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。( )6

7、中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列。 ( )7完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。( )8. 二叉樹只能用二叉鏈表表示。( )9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。( )10. 用鏈表(llink-rlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n-1個空指針。( )11樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系。( )12將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹。( )13度為二的樹就是二叉樹。( )14. 二叉樹中序線索化后，不存在空指針域。( )15霍夫曼樹的結(jié)點個數(shù)不能是偶數(shù)。( )16哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的

8、結(jié)點離根較近。( )三、填空題1在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是_ _。2深度為k的完全二叉樹至少有_ _個結(jié)點，至多有_ _個結(jié)點。3高度為8的完全二叉樹至少有_個葉子結(jié)點。4.具有n個結(jié)點的二叉樹中,一共有_個指針域,其中只有_個用來指向結(jié)點的左右孩子，其余的_個指針域為NULL。5樹的主要遍歷方法有_、_、_等三種。6一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是_ _；編號是i的結(jié)點所在的層次號是_ _（根所在的層次號規(guī)定為1層）。7如果結(jié)點A有 3個兄弟，而且B是A的雙親，則B的度是_。8二叉樹的先序序

9、列和中序序列相同的條件是_ _。9一個無序序列可以通過構(gòu)造一棵_ _樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。10若一個二叉樹的葉子結(jié)點是某子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的_ _序列中的最后一個結(jié)點。11若以4，5，6，7，8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是_。12以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請在橫線處填充適當?shù)恼Z句。Void countleaf(bitreptr t,int *count)/*根指針為t，假定葉子數(shù)count的初值為0*/ if(t!=NULL) if(t->lchild=NULL)&&

10、amp;(t->rchild=NULL)_; countleaf(t->lchild,&count); _ 13以下程序是二叉鏈表樹中序遍歷的非遞歸算法，請?zhí)羁帐怪晟?。二叉樹鏈表的結(jié)點類型的定義如下： typedef struct node /*C語言/ char data; struct node *lchild,*rchild;*bitree;void vst(bitree bt) /*bt為根結(jié)點的指針*/ bitree p; p=bt; initstack(s); /*初始化棧s為空棧*/while(p | !empty(s) /*棧s不為空*/ if(p) pu

11、sh (s,p); (1)_ ; /*P入棧*/else p=pop(s); printf(“%c”,p->data);(2)_ _; /*棧頂元素出棧*/ 14二叉樹存儲結(jié)構(gòu)同上題，以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦?int depth(bitree bt) /*bt為根結(jié)點的指針*/int hl,hr; if (bt=NULL) return(1)_ _); hl=depth(bt->lchild); hr=depth(bt->rchild); if(2)_ _) (3)_ _； return(hr+1); 15將二叉樹bt中每一個結(jié)點的左右子樹互換的C語言

12、算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進隊，出隊和判別隊列是否為空的函數(shù)，請?zhí)顚懰惴ㄖ械每瞻滋?，完成其功能。typedef struct node int data ; struct node *lchild, *rchild; btnode; void EXCHANGE(btnode *bt)btnode *p, *q; if (bt)ADDQ(Q,bt); while(!EMPTY(Q) p=DELQ(Q); q=(1)_ _; p->rchild=(2)_ _; (3)_ _=q;if(p->lchild) (4)_ _; if(p->

13、;rchild) (5)_ _; /四、應(yīng)用題1樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？2分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。3分別給出下圖所示二叉樹的先根、中根和后根序列。4一個深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有K棵非空子樹，如果按層次順序從1開始對全部結(jié)點進行編號，求：1）各層的結(jié)點的數(shù)目是多少？ 2）編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是多少？3）編號為n的結(jié)點的第i 個孩子結(jié)點（若存在）的編號是多少？4）編號為n的結(jié)點有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？請給出計算和推導過程。5將下列由三棵樹組成的森林轉(zhuǎn)

14、換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）NPGHJMOLIKEDFBAC 6設(shè)二叉樹BT的存儲結(jié)構(gòu)如下: 1 2 3 4 5 6 7 8 9 10Lchild 0 0 2 3 7 5 8 0 10 1DataJ H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中BT為樹根結(jié)點的指針，其值為6,Lchild,Rchild分別為結(jié)點的左、右孩子指針域,data為結(jié)點的數(shù)據(jù)域。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu);（3）畫出二叉樹的后序線索樹。五、算法設(shè)計題1要求二叉樹按二叉鏈表形式存儲，（1）寫一個建立二叉樹的算法。（2）寫一個判別給定的二叉樹

15、是否是完全二叉樹的算法。完全二叉樹定義為：深度為K，具有N個結(jié)點的二叉樹的每個結(jié)點都與深度為K的滿二叉樹中編號從1至N的結(jié)點一一對應(yīng)。此題以此定義為準。2設(shè)一棵二叉樹的結(jié)點結(jié)構(gòu)為 (LLINK,INFO,RLINK),ROOT為指向該二叉樹根結(jié)點的指針，p和q分別為指向該二叉樹中任意兩個結(jié)點的指針，試編寫一算法ANCESTOR（ROOT，p,q,r）,該算法找到p和q的最近共同祖先結(jié)點r。3有一二叉鏈表，試編寫按層次順序遍歷二叉樹的算法。4已知二叉樹按照二叉鏈表方式存儲，利用棧的基本操作寫出先序遍歷非遞歸形式的算法。5對于二叉樹的鏈接實現(xiàn),完成非遞歸的中序遍歷過程。6試寫出復制一棵二叉樹的算法

16、。二叉樹采用標準鏈接結(jié)構(gòu)。7請設(shè)計一個算法，要求該算法把二叉樹的葉子結(jié)點按從左到右的順序連成一個單鏈表，表頭指針為head。 二叉樹按二叉鏈表方式存儲，鏈接時用葉子結(jié)點的右指針域來存放單鏈表指針。分析你的算法的時、空復雜度。8已知二叉樹以二叉鏈表存儲，編寫算法完成：對于樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的空間。9設(shè)一棵二叉樹的根結(jié)點指針為T，C為計數(shù)變量，初值為0，試寫出對此二叉樹中結(jié)點計數(shù)的算法：BTLC（T，C）。10分別寫出算法，實現(xiàn)在中序線索二叉樹T中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在后序線索二

17、叉樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)。第六章 樹和二叉樹一、單項選擇題1.A2.D3A4C5B6D7E 8. D9C10B11. C12A13D14B15C16B 17. B18. A19C20D21B22. D23C二、判斷題（在各題后填寫“”或“×”）1. 完全二叉樹一定存在度為1的結(jié)點。×2. 對于有N個結(jié)點的二叉樹，其高度為log2n。×3. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。4. 一棵一般樹的結(jié)點的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點前序遍歷和后序遍歷是一致的。×5. 用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點

18、。×6中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列 7完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。8. 二叉樹只能用二叉鏈表表示。×9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。10. 用鏈表(llink-rlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n-1個空指針。×11樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系。12將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹。×13度為二的樹就是二叉樹。×14. 二叉樹中序線索化后，不存在空指針域。×15霍夫曼樹的結(jié)點個數(shù)不能是偶數(shù)。16哈夫曼樹是帶權(quán)路徑長度最短的樹，路

19、徑上權(quán)值較大的結(jié)點離根較近。三、填空題1p->lchild=null && p->rchlid=null 2.(1)2k-1 (2)2k-13644. 2n n-1 n+1 5 先序遍歷 后序遍歷 中序遍歷 6.(1)2k-2+1（第k層1個結(jié)點，總結(jié)點個數(shù)是2H-1，其雙親是2H-1/2=2k-2）(2) ëlog2iû+1748任何結(jié)點至多只有右子女的二叉樹。9二叉排序樹10前序116912 *count+, countleaf(l->rchile,count)13(1) p=p->lchild / 沿左子樹向下 （2）p=p-&

20、gt;rchild 14(1)0 （2）hl>hr (3)hr=hl15(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild)四、應(yīng)用題1樹和二叉樹邏輯上都是樹形結(jié)構(gòu)，樹和二叉樹的區(qū)別有三：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個別書上允許為空）。二叉樹不是樹的特例。2【解答】具有3個結(jié)點的樹 具有3個結(jié)點的二叉樹3解答：

21、先根序列：A B C D E F G H I J;中根序列：B C D A F E H J I G;后根序列：D C B F J I H G E A。4(1)kh-1(h為層數(shù))（2）因為該樹每層上均有Kh-1個結(jié)點，從根開始編號為1，則結(jié)點i的從右向左數(shù)第個孩子的結(jié)點編號為ki。設(shè)n 為結(jié)點i的子女，則關(guān)系式(i-1)k+2<=n<=ik+1成立，因i是整數(shù)，故結(jié)點n的雙親i的編號為ën-2)/kû+1。 (3) 結(jié)點n(n>1)的前一結(jié)點編號為n-1（其最右邊子女編號是(n-1)*k+1），故結(jié)點 n的第 i個孩子的編號是(n-1)*k+1+i。(4)

22、 根據(jù)以上分析，結(jié)點n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即 (n-1)%k!=0，其右兄弟編號是n+1。HGDACJIBFEMPONKOL5.6（l）圖略；（2） 前序序列：J 中序序列： E C B H F D J I G A 后序序列： （3）圖略。7字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。其哈夫曼編碼如下A:1，B:000，C:01，D:0011359000111五、算法設(shè)計題1題目分析二叉樹是遞歸定義的，以遞歸方式建立最簡單。判定是否是完全二叉樹，可以使用隊列，在遍歷中利用完全二叉樹“若某結(jié)點無左子女就不應(yīng)有右子女”的原則進行判斷。BiTree Creat

23、() /建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu)ElemType x；BiTree bt;scanf(“%d”,&x); /本題假定結(jié)點數(shù)據(jù)域為整型if(x=0) bt=null;else if(x>0) bt=(BiNode *)malloc(sizeof(BiNode);bt->data=x; bt->lchild=creat(); bt->rchild=creat(); else error(“輸入錯誤”)；return(bt);/結(jié)束 BiTreeint JudgeComplete(BiTree bt) /判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0

24、int tag=0; BiTree p=bt, Q; / Q是隊列，元素是二叉樹結(jié)點指針，容量足夠大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化隊列，根結(jié)點指針入隊while (!QueueEmpty(Q)p=QueueOut(Q); /出隊 if (p->lchild && !tag) QueueIn(Q,p->lchild); /左子女入隊 else if (p->lchild) return 0; /前邊已有結(jié)點為空，本結(jié)點不空 else tag=1; /首次出現(xiàn)結(jié)點為空 if (p->

25、;rchild && !tag) QueueIn(Q,p->rchild); /右子女入隊 else if (p->rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete算法討論完全二叉樹證明還有其它方法。判斷時易犯的錯誤是證明其左子樹和右子數(shù)都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯誤結(jié)論。2.題目分析后序遍歷最后訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹結(jié)點的指針，當訪問到某結(jié)點時，棧中所有元素均為該結(jié)點的祖先。本題要找p和q 的最近共同祖先結(jié)點r ,

26、不失一般性，設(shè)p在q的左邊。后序遍歷必然先遍歷到結(jié)點p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配（即相等）的元素就是結(jié)點p 和q的最近公共祖先。typedef struct BiTree t;int tag;/tag=0 表示結(jié)點的左子女已被訪問，tag=1表示結(jié)點的右子女已被訪問stack;stack s,s1;/棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)/求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。top=0; bt=ROOT; while(bt!=null |top>

27、0)while(bt!=null && bt!=p && bt!=q) /結(jié)點入棧s+top.t=bt; stop.tag=0; bt=bt->lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左側(cè),遇結(jié)點p時，棧中元素均為p的祖先結(jié)點for(i=1;i<=top;i+) s1i=si; top1=top; /將棧s的元素轉(zhuǎn)入輔助棧s1 保存if(bt=q) /找到q 結(jié)點。for(i=top;i>0;i-)/；將棧中元素的樹結(jié)點到s1去匹配pp=si.t;for (j=top1;j>0;j-)if(s1j.t=p

28、p) printf(“p 和q的最近共同的祖先已找到”)；return (pp);while(top!=0 && stop.tag=1) top-; /退棧if (top!=0)stop.tag=1;bt=stop.t->rchild; /沿右分枝向下遍歷/結(jié)束while(bt!=null |top>0)return(null);/、p無公共祖先/結(jié)束Ancestor3解答：本算法要借用隊列來完成，其基本思想是，只要隊列不為空，就出隊列，然后判斷該結(jié)點是否有左孩子和右孩子，如有就依次輸出左、右孩子的值，然后讓左、右孩子進隊列。void layorder (bitre

29、ptr T) initqueue (q) /*隊列初始化*/ if(T!=NULL) printf(“%f”, T->data); enqueue (q, T); /*入隊列*/ while (not emptyqueue (q) ) /*若隊列非空*/ outqueue (q, p) ; /*出隊*/ if (p->lchild!=NULL) printf(“%f”, p->lchild->data); enqueue (q, p->lchild); /*入隊列*/ if (p->rchild!=NULL) printf(“%”, p->rchild

30、->data); enqueue (q, p->rchild); /*入隊列*/ 4【解答】Void PreOrder(BiTree root) /*先序遍歷二叉樹的非遞歸算法*/ InitStack(&S); p=root; while(p!=NULL | !IsEmpty(S) ) if(p!=NULL) Visit(p->data);push(&S,p);p=p->Lchild; else Pop(&S,&p); p=p->RChild;5void InOrder(BiTree bt) BiTree s,p=bt; /s是元素

31、為二叉樹結(jié)點指針的棧，容量足夠大int top=0;while(p | top>0) while(p) s+top=p; bt=p->lchild; /中序遍歷左子樹 if(top>0)p=stop-; printf(p->data); p=p->rchild; /退棧，訪問，轉(zhuǎn)右子樹 6BiTree Copy(BiTree t)/復制二叉樹tBiTree bt; if (t=null) bt=null; elsebt=(BiTree)malloc(sizeof(BiNode); bt->data=t->data;bt->lchild=Copy(

32、t->lchild);bt->rchild=Copy(t->rchild); return(bt); /結(jié)束Copy7.題目分析葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針pre，初始為空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點的rchild為空。LinkedList head,pre=null; /全局變量LinkedList InOrder(BiTree bt)/中序遍歷二叉樹bt，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為head if(bt)InOrder(bt->lchil

33、d); /中序遍歷左子樹 if(bt->lchild=null && bt->rchild=null) /葉子結(jié)點 if(pre=null) head=bt; pre=bt; /處理第一個葉子結(jié)點 elsepre->rchild=bt; pre=bt; /將葉子結(jié)點鏈入鏈表 InOrder(bt->rchild); /中序遍歷左子樹 pre->rchild=null; /設(shè)置鏈表尾 return(head); /InOrder時間復雜度為O(n),輔助變量使用head和pre,?？臻g復雜度O(n)8.題目分析 刪除以元素值x為根的子樹，只要能刪除其

34、左右子樹，就可以釋放值為x的根結(jié)點，因此宜采用后序遍歷。刪除值為x結(jié)點，意味著應(yīng)將其父結(jié)點的左(右)子女指針置空，用層次遍歷易于找到某結(jié)點的父結(jié)點。本題要求刪除樹中每一個元素值為 x的結(jié)點的子樹，因此要遍歷完整棵二叉樹。void DeleteXTree(BiTree bt) /刪除以bt為根的子樹 DeleteXTree(bt->lchild); DeleteXTree(bt->rchild);/刪除bt的左子樹、右子樹 free(bt); / DeleteXTree /釋放被刪結(jié)點所占的存儲空間void Search(B:Tree bt,ElemType x)/在二叉樹上查找所有

35、以x為元素值的結(jié)點，并刪除以其為根的子樹BiTree Q;/Q是存放二叉樹結(jié)點指針的隊列，容量足夠大 if(bt) if(bt->data=x) DeleteXTree(bt); exit(0);/若根結(jié)點的值為x，則刪除整棵樹 QueueInit(Q); QueueIn(Q,bt); while(!QueueEmpty(Q)p=QueueOut(Q);if(p->lchild) / 若左子女非空 if(p->lchild->data=x) /左子女結(jié)點值為 x,應(yīng)刪除當前結(jié)點的左子樹 DeleteXTree(p->lchild); p->lchild=null;