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

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

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

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

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

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

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

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

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

9、列和中序序列相同的條件是_ _。9一個(gè)無序序列可以通過構(gòu)造一棵_ _樹而變成一個(gè)有序序列，構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。10若一個(gè)二叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹的_ _序列中的最后一個(gè)結(jié)點(diǎn)。11若以4，5，6，7，8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是_。12以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請(qǐng)?jiān)跈M線處填充適當(dāng)?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以下程序是二叉鏈表樹中序遍歷的非遞歸算法，請(qǐng)?zhí)羁帐怪晟?。二叉樹鏈表的結(jié)點(diǎn)類型的定義如下： typedef struct node /*C語言/ char data; struct node *lchild,*rchild;*bitree;void vst(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/ 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二叉樹存儲(chǔ)結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法，請(qǐng)?zhí)羁胀晟浦?int depth(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/int hl,hr; if (bt=NULL) return(1)_ _); hl=depth(bt->lchild); hr=depth(bt->rchild); if(2)_ _) (3)_ _； return(hr+1); 15將二叉樹bt中每一個(gè)結(jié)點(diǎn)的左右子樹互換的C語言

12、算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請(qǐng)?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個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。3分別給出下圖所示二叉樹的先根、中根和后根序列。4一個(gè)深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有K棵非空子樹，如果按層次順序從1開始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào)，求：1）各層的結(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)是多少？4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？如果有，其右兄弟的編號(hào)是多少？請(qǐng)給出計(jì)算和推導(dǎo)過程。5將下列由三棵樹組成的森林轉(zhuǎn)

14、換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）NPGHJMOLIKEDFBAC 6設(shè)二叉樹BT的存儲(chǔ)結(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é)點(diǎn)的指針，其值為6,Lchild,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域,data為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu);（3）畫出二叉樹的后序線索樹。五、算法設(shè)計(jì)題1要求二叉樹按二叉鏈表形式存儲(chǔ)，（1）寫一個(gè)建立二叉樹的算法。（2）寫一個(gè)判別給定的二叉樹

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

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

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

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

19、徑上權(quán)值較大的結(jié)點(diǎn)離根較近。三、填空題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個(gè)結(jié)點(diǎn)，總結(jié)點(diǎn)個(gè)數(shù)是2H-1，其雙親是2H-1/2=2k-2）(2) ëlog2iû+1748任何結(jié)點(diǎn)至多只有右子女的二叉樹。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，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個(gè)別書上允許為空）。二叉樹不是樹的特例。2【解答】具有3個(gè)結(jié)點(diǎn)的樹 具有3個(gè)結(jié)點(diǎn)的二叉樹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）因?yàn)樵摌涿繉由暇蠯h-1個(gè)結(jié)點(diǎn)，從根開始編號(hào)為1，則結(jié)點(diǎn)i的從右向左數(shù)第個(gè)孩子的結(jié)點(diǎn)編號(hào)為ki。設(shè)n 為結(jié)點(diǎn)i的子女，則關(guān)系式(i-1)k+2<=n<=ik+1成立，因i是整數(shù)，故結(jié)點(diǎn)n的雙親i的編號(hào)為ën-2)/kû+1。 (3) 結(jié)點(diǎn)n(n>1)的前一結(jié)點(diǎn)編號(hào)為n-1（其最右邊子女編號(hào)是(n-1)*k+1），故結(jié)點(diǎn) n的第 i個(gè)孩子的編號(hào)是(n-1)*k+1+i。(4)

22、 根據(jù)以上分析，結(jié)點(diǎn)n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即 (n-1)%k!=0，其右兄弟編號(hào)是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è)計(jì)題1題目分析二叉樹是遞歸定義的，以遞歸方式建立最簡單。判定是否是完全二叉樹，可以使用隊(duì)列，在遍歷中利用完全二叉樹“若某結(jié)點(diǎn)無左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。BiTree Creat

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

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

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

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

27、0)while(bt!=null && bt!=p && bt!=q) /結(jié)點(diǎn)入棧s+top.t=bt; stop.tag=0; bt=bt->lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左側(cè),遇結(jié)點(diǎn)p時(shí)，棧中元素均為p的祖先結(jié)點(diǎn)for(i=1;i<=top;i+) s1i=si; top1=top; /將棧s的元素轉(zhuǎn)入輔助棧s1 保存if(bt=q) /找到q 結(jié)點(diǎn)。for(i=top;i>0;i-)/；將棧中元素的樹結(jié)點(diǎn)到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解答：本算法要借用隊(duì)列來完成，其基本思想是，只要隊(duì)列不為空，就出隊(duì)列，然后判斷該結(jié)點(diǎn)是否有左孩子和右孩子，如有就依次輸出左、右孩子的值，然后讓左、右孩子進(jìn)隊(duì)列。void layorder (bitre

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

30、->data); enqueue (q, p->rchild); /*入隊(duì)列*/ 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é)點(diǎn)指針的棧，容量足夠大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)/復(fù)制二叉樹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é)點(diǎn)只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。LinkedList head,pre=null; /全局變量LinkedList InOrder(BiTree bt)/中序遍歷二叉樹bt，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head if(bt)InOrder(bt->lchil

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

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

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