第6章_數(shù)據(jù)結(jié)構(gòu)習題題目及答案_樹和二叉樹_參考答案

1、一、基礎知識題6.1設樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1，求樹T中的葉子數(shù)。【解答】 設度為m的樹中度為0,1,2,m的結(jié)點數(shù)分別為n0, n1, n2, nm，結(jié)點總數(shù)為n，分枝數(shù)為B，則下面二式成立n= n0+n1+n2+nm (1)n=B+1= n1+2n2+mnm+1 (2)由(1)和(2)得葉子結(jié)點數(shù)n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉樹上有1001個結(jié)點，求葉子結(jié)點的個數(shù)?！窘獯稹恳驗樵谌我舛鏄渲卸葹? 的結(jié)點數(shù)n2和葉子結(jié)點數(shù)n0有如下關(guān)系：n2=n0-1,所以設二叉樹的結(jié)

2、點數(shù)為n, 度為1的結(jié)點數(shù)為n1，則 n= n0+ n1+ n2 n=2n0+n1-1 1002=2n0+n1由于在完全二叉樹中，度為1的結(jié)點數(shù)n1至多為1，葉子數(shù)n0是整數(shù)。本題中度為1的結(jié)點數(shù)n1只能是0，故葉子結(jié)點的個數(shù)n0為501.注：解本題時要使用以上公式，不要先判斷完全二叉樹高10，前9層是滿二叉樹，第10層都是葉子，。雖然解法也對，但步驟多且復雜，極易出錯。6.3 一棵124個葉結(jié)點的完全二叉樹，最多有多少個結(jié)點?！窘獯稹坑晒絥=2n0+n1-1,當n1為1時，結(jié)點數(shù)達到最多248個。6.4一棵完全二叉樹有500個結(jié)點，請問該完全二叉樹有多少個葉子結(jié)點？有多少個度為1的結(jié)點？有

3、多少個度為2的結(jié)點？如果完全二叉樹有501個結(jié)點，結(jié)果如何？請寫出推導過程。【解答】由公式n=2n0+n1-1，帶入具體數(shù)得，500=2n0+n1-1，葉子數(shù)是整數(shù)，度為1的結(jié)點數(shù)只能為1，故葉子數(shù)為250，度為2的結(jié)點數(shù)是249。若完全二叉樹有501個結(jié)點，則葉子數(shù)251，度為2的結(jié)點數(shù)是250，度為1的結(jié)點數(shù)為0。6.5某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是多少?！窘獯稹坑晒絥=2n0+n1-1，得該二叉樹的總結(jié)點數(shù)是69。6.6 求一棵具有1025個結(jié)點的二叉樹的高h。【解答】該二叉樹最高為1025（只有一個葉子結(jié)點），最低高為11。因為210-11

4、025211-1，故1025個結(jié)點的二叉樹最低高為11。6.7 一棵二叉樹高度為h，所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有多少結(jié)點?！窘獯稹康谝粚又灰粋€根結(jié)點，其余各層都兩個結(jié)點，這棵二叉樹最少結(jié)點數(shù)是2h-1。6.8將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度是多少?！窘獯稹吭O含n個結(jié)點的完全三叉樹的高度為h，則有nn2n0)的滿二叉樹對應的森林由多少棵樹構(gòu)成?！窘獯稹恳驗樵诙鏄滢D(zhuǎn)換為森林時，二叉樹的根結(jié)點，根結(jié)點的右子女，右子女的右子女，都是樹的根，所以，高度為h(h0)的滿二叉樹對應的森林由h棵樹構(gòu)成。6.11 某二叉樹結(jié)點的中序序列為BDAECF，后

5、序序列為DBEFCA，則該二叉樹對應的森林包括幾棵樹？【解答】3棵樹。（本題不需畫出完整的二叉樹，更不需要畫出森林，只需畫出二叉樹的右子樹就可求解。如上題所述，二叉樹的根結(jié)點，根結(jié)點的右子女，右子女的右子女，在二叉樹轉(zhuǎn)為森林時，都是樹的根。）6.12 對任意一棵樹，設它有n個結(jié)點，這n個結(jié)點的度數(shù)之和為多少？【解答】n-1。度數(shù)其實就是分支個數(shù)。根結(jié)點無分支所指，其余結(jié)點有且只有一個分支所指。6.13 一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是多少？【解答】對二叉樹線索化時，只有空鏈域才可加線索。一棵左子樹為空的二叉樹在先序線索化時，根結(jié)點的左鏈為空，應加上指向前驅(qū)的線索，但根

6、結(jié)點無前驅(qū)，故該鏈域為空。同樣分析知道最后遍歷的結(jié)點的右鏈域為空。故一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是2個。6.14 一棵左、右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是多少?【解答】1個。6.15 設B是由森林F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有幾個？【解答】n+1。森林中任何一個非終端結(jié)點在轉(zhuǎn)換成二叉樹時，其第一個子女結(jié)點成為該非終端結(jié)點的左子女，其余子女結(jié)點成為剛生成的左子女結(jié)點的右子女，右子女結(jié)點的右子女，最右子女結(jié)點的右鏈域為空。照此分析，n個非終端結(jié)點在轉(zhuǎn)換后，其子女結(jié)點中共有n個空鏈域。另外，森林中各棵樹的根結(jié)點

7、可以看做互為兄弟，轉(zhuǎn)換成二叉樹后也產(chǎn)生1個空鏈域。因此，本題的答案是n+1。6.16 試分別找出滿足以下條件的所有二叉樹： (1)二叉樹的前序序列與中序序列相同； (2) 二叉樹的中序序列與后序序列相同； (3)二叉樹的前序序列與后序序列相同；(4) 二叉樹的前序序列與層次序列相同；(5) 二叉樹的前序、中序與后序序列均相同?！窘獯稹壳靶虮闅v二叉樹的順序是“根左子樹右子樹”，中序遍歷的順序是“左子樹根右子樹”，后序遍歷順序是：“左子樹右子樹根，根據(jù)以上原則，本題解答如下：若前序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹。若中序序列與后序序列相同，則或為空樹，或為任一結(jié)點

8、至多只有左子樹的二叉樹。若前序序列與后序序列相同，則或為空樹，或為只有根結(jié)點的二叉樹。若二叉樹的前序、中序與后序序列均相同，則或為空樹，或為只有根結(jié)點的二叉樹。6.17 已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試畫出這棵二叉樹，對二叉樹進行中序線索化，并將該二叉樹轉(zhuǎn)換為森林?！窘獯稹?.18 已知一棵二叉樹的后序遍歷序列為EICBGAHDF，同時知道該二叉樹的中序遍歷序列為CEIFGBADH，試畫出該二叉樹。6.19設二叉樹中每個結(jié)點均用一個字母表示，若一個結(jié)點的左子樹或右子樹為空，用#表示，現(xiàn)前序遍歷二叉樹，訪問的結(jié)點序列為ABD#C#E#

9、F#，寫出中序和后序遍歷二叉樹時結(jié)點的訪問序列?！窘獯稹恐行虮闅v二叉樹時結(jié)點的訪問序列：#D#B#C#E#A#F#后序遍歷二叉樹時結(jié)點的訪問序列。#D#ECB#FA6.20有n個結(jié)點的k叉樹（k2）用k叉鏈表表示時，有多少個空指針？【解答】k叉樹（k2）用k叉鏈表表示時,每個結(jié)點有k個指針，除根結(jié)點沒有指針指向外，其余每個結(jié)點都有一個指針指向，故空指針的個數(shù)為： nk-(n-1)=n(k-1)+16.21 一棵高度為h的滿k叉樹有如下性質(zhì)：根結(jié)點所在層次為0；第h層上的結(jié)點都是葉子結(jié)點；其余各層上每個結(jié)點都有k棵非空子樹，如果按層次自頂向下，同一層自左向右，順序從1開始對全部結(jié)點進行編號，試問

10、：(1)各層的結(jié)點個數(shù)是多少?(2)編號為i的結(jié)點的雙親結(jié)點（若存在）的編號是多少?(3)編號為i的結(jié)點的第m個孩子結(jié)點（若存在）的編號是多少？(4)編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟結(jié)點的編號是多少？【解答】(1)kl(l為層數(shù)，按題意，根結(jié)點為0層)（2）因為該樹每層上均有kl個結(jié)點，從根開始編號為1，則結(jié)點i的從右向左數(shù)第個孩子的結(jié)點編號為ki。設n 為結(jié)點i的子女，則關(guān)系式(i-1)k+2=n1)的前一結(jié)點編號為i-1（其最右邊子女編號是(i-1)*k+1），故結(jié)點 i的第 m個孩子的編號是(i-1)*k+1+m。(4) 根據(jù)以上分析，結(jié)點i有右兄弟的條件是，它不是雙親的從右

11、數(shù)的第一子女，即 (i-1)%k!=0，其右兄弟編號是i+1。6.22證明任一結(jié)點個數(shù)為n(n0) 的二叉樹的高度至少為(logn)+1?！窘獯稹孔畹透叨榷鏄涞奶攸c是，除最下層結(jié)點個數(shù)不滿外，其余各層的結(jié)點數(shù)都應達到各層的最大值。設n個結(jié)點的二叉樹的最低高度是h，則n應滿足2h-1n2h-1關(guān)系式。解此不等式，并考慮h是整數(shù)，則有h=logn+1，即任一結(jié)點個數(shù)為n 的二叉樹的高度至少為(logn)+1。6.23 已知A1.N是一棵順序存儲的完全二叉樹，如何求出Ai和Aj的最近的共同祖先？【解答】根據(jù)順序存儲的完全二叉樹的性質(zhì)，編號為i的結(jié)點的雙親的編號是i/2，故Ai和Aj的最近公共祖先可

12、如下求出： while(i/2!=j/2)if(ij) i=i/2;elsej=j/2;退出while后，若i/2=0,則最近公共祖先為根結(jié)點，否則最近公共祖先是i/2。6.24已知一棵滿二叉樹的結(jié)點個數(shù)為20到40之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？【解答】結(jié)點個數(shù)在20到40的滿二叉樹且結(jié)點數(shù)是素數(shù)的數(shù)是31，其葉子數(shù)是16。6.25求含有n個結(jié)點、采用順序存儲結(jié)構(gòu)的完全二叉樹中的序號最小的葉子結(jié)點的下標。要求寫出簡要步驟?！窘獯稹扛鶕?jù)完全二叉樹的性質(zhì)，最后一個結(jié)點（編號為n）的雙親結(jié)點的編號是n/2，這是最后一個分枝結(jié)點，在它之后是第一個終端（葉子）結(jié)點，故序號最小的葉子結(jié)點的下標是

13、n/2+1。6.26 試證明:同一棵二叉樹的所有葉子結(jié)點，在前序序列、中序序列以及后序序列中都按相同的相對位置出現(xiàn)（即先后順序相同），例如前序abc，后序bca，中序bac?！咀C明】前序遍歷是“根左右”，中序遍歷是“左根右”，后序遍歷是“左右根”。三種遍歷中只是訪問“根”結(jié)點的時機不同，對左右子樹均是按左右順序來遍歷的，因此所有葉子都按相同的相對位置出現(xiàn)。6.27設具有四個結(jié)點的二叉樹的前序遍歷序列為；為長度等于4的由，排列構(gòu)成的字符序列，若任取作為上述算法的中序遍歷序列，試問是否一定能構(gòu)造出相應的二叉樹，為什么？試列出具有四個結(jié)點二叉樹的全部形態(tài)及相應的中序遍歷序列?！窘獯稹咳羟靶蛐蛄惺莂b

14、cd，并非由這四個字母的任意組合（4!=24）都能構(gòu)造出二叉樹。因為以abcd為輸入序列，通過棧只能得到1/(n+1)*2n!/(n!*n!)=14 種，即以abcd為前序序列的二叉樹的數(shù)目是14。任取以abcd作為中序遍歷序列，并不全能與前序的abcd序列構(gòu)成二叉樹。例如：若取中序序列dcab就不能。該14棵二叉樹的形態(tài)及中序序列略。6.28已知某二叉樹的每個結(jié)點，要么其左、右子樹皆為空，要么其左、右子樹皆不空。又知該二叉樹的前序序列為：JFDBACEHXIK；后序序列為：ACBEDXIHFKJ。請給出該二叉樹的中序序列，并畫出相應的二叉樹樹形。【解答】一般說來，僅僅知道二叉樹的前序遍歷序列

15、和后序遍歷序列并不能確定這棵二叉樹，因為并不知道左子樹和右子樹兩部分各有多少個結(jié)點。但本題有特殊性，即每個結(jié)點“要么其左、右子樹皆為空，要么其左、右子樹皆不空”。具體說，前序序列的第一個結(jié)點是二叉樹的根，若該結(jié)點后再無其它結(jié)點，則二叉樹只有根結(jié)點；否則，該結(jié)點必有左右子樹，且根結(jié)點后的第一個結(jié)點就是“左子樹的根”。到后序序列中查找這個“左子樹的根”，它將后序序列分成左右兩部分：左部分(包括所查到的“左子樹的根結(jié)點”)是二叉樹的左子樹(可能為空)，右部分(除去最后的根結(jié)點)則是右子樹(可能為空)。這樣，在確定根結(jié)點后，就可以將后序遍歷序列（從而也將前序遍歷序列）分成左子樹和右子樹兩部分了。本題中

16、，先看前序遍歷序列，第一個結(jié)點是J，所以J是二叉樹的根，J后面還有結(jié)點，說明J有左、右子樹，J后面的F必是左子樹的根。到后序遍歷序列中找到F,F將后序遍歷序列分成兩部分：左面ACBEDXIH，說明FACBEDXIH是根J的左子樹；右面K(K的右面J已知是根)，說明K是根J的右子樹。這樣，問題就轉(zhuǎn)化為“以前序序列FDBACEHXI和后序序列ACBEDXIHF去構(gòu)造根J的左子樹”，以及“以前序序列K和后序序列K去構(gòu)造根J的右子樹”了。如此構(gòu)造下去，所構(gòu)造的二叉樹如下。易見，中序序列為ABCDEFXHIJK。6.29 已知一個森林的先序序列和后序序列如下，請構(gòu)造出該森林。先序序列：ABCDEFGHI

17、JKLMNO后序序列：CDEBFHIJGAMLONK【解答】森林的先序序列和后序序列對應其轉(zhuǎn)換的二叉樹的先序序列和中序序列，應先據(jù)此構(gòu)造二叉樹，再構(gòu)造出森林。6.30 畫出同時滿足下列兩條件的兩棵不同的二叉樹。(1)按先根序遍歷二叉樹順序為ABCDE。(2)高度為5其對應的樹（森林）的高度最大為4?！窘獯稹?6.31用一維數(shù)組存放的一棵完全二叉樹；ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的結(jié)點訪問序列?！窘獯稹亢笮虮闅v該二叉樹的結(jié)點訪問序列為：DECGHFBKJLIA6.32一棵二叉樹的先序、中序和后序序列如下，其中有部分未標出，試構(gòu)造出該二叉樹。先序序列為：C D E G H I K

18、中序序列為：C B F A _ J K I G后序序列為：E F D B J I H A【解答】6.33設樹形T在后根次序下的結(jié)點排列和各結(jié)點相應的度數(shù)如下：后根次序：次數(shù)：請畫出的樹形結(jié)構(gòu)圖?！窘獯稹吭跇湓诤蟾闅v次序下，根結(jié)點在最后，任何結(jié)點的子樹的所有結(jié)點都直接排在該結(jié)點之前。例如，挨著根結(jié)點的是根結(jié)點的最右邊的子女。每棵子樹的所有結(jié)點都聚集在一起，中間不會插入其它結(jié)點，也不會丟掉子樹的任何結(jié)點。按照這種理論解答本題，在遍歷次序中從右到左分析，A是根，它有4個子女，H是它的最右邊的子女（第4子女）。H有2個子女，L是H的最右邊的子女，L無子女，故I是H的第1子女。I又有2個子女：K和J，

19、二者均無子女。由此推斷出下一個結(jié)點G是根結(jié)點A的第3子女。，繼續(xù)構(gòu)造，直至最左面的結(jié)點B，結(jié)果樹形如下：6.34 若森林共有n個結(jié)點和b條邊(blchild & t-rchild) n2+;else if(t-lchild & !t-rchild | !t-lchild & t-rchild) n1+;elsen0+;if(t-lchild!=null) Count(t-lchild);if(t-rchild!=null) Count(t-rchild); Count6.38一棵n個結(jié)點的完全二叉樹存放在二叉樹的順序存儲結(jié)構(gòu)中，試編寫非遞歸算法對該樹進行先序遍歷?！绢}目分析】二叉樹的順序存儲是

20、按完全二叉樹的順序存儲，雙親與子女結(jié)點下標間有確定關(guān)系。順序存儲結(jié)構(gòu)的二叉樹用結(jié)點下標大于n（完全二叉樹）或0（對一般二叉樹的“虛結(jié)點”）判空。本題是完全二叉樹。【算法6.38】voidPreOrder(ElemType bt,intn)對以順序結(jié)構(gòu)存儲的完全二叉樹bt進行前序遍歷inti=1,top=0,s;top是棧s的棧頂指針，棧容量足夠大while(i0)while(i=n)printf(bti); 訪問根結(jié)點；if(2*i+10) i=stop-; 取出棧頂元素while結(jié)束PreOrder6.39以二叉鏈表作為存儲結(jié)構(gòu)的二叉樹，按后序遍歷時輸出的結(jié)點順序為a1， a2，an。試編寫

21、一算法，要求輸出后序序列的逆序an，an-1，a2，a1?！绢}目分析】二叉樹后序遍歷是按“左子樹右子樹根結(jié)點”的順序遍歷二叉樹，根據(jù)題意，若將遍歷順序改為“根結(jié)點右子樹左子樹”，就可以實現(xiàn)題目要求?！舅惴?.39】voidPostOrder(BiTree bt)/對二叉樹bt進行先右后左的“先根”遍歷if(bt) printf(bt-data); /訪問根結(jié)點 PostOrder(bt-rchild);/先根遍歷右子樹 PostOrder(bt-lchild);/先根遍歷左子樹 6.40以二叉鏈表作為存儲結(jié)構(gòu)，設計算法交換二叉樹中所有結(jié)點的左、右子樹?！舅惴?.40】voidexchange(

22、BiTree bt)將二叉樹bt所有結(jié)點的左右子樹交換if(bt)BiTree s；s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; 左右子女交換exchange(bt-lchild);交換左子樹上所有結(jié)點的左右子樹exchange(bt-rchild);交換右子樹上所有結(jié)點的左右子樹if 結(jié)束【算法討論】將上述算法中兩個遞歸調(diào)用語句放在前面，將交換語句放在最后，則是以后序遍歷方式交換所有結(jié)點的左右子樹。中序遍歷方式不適合本題。6.41以二叉鏈表為存儲結(jié)構(gòu)，寫出在二叉樹中求值為x的結(jié)點在樹中層次數(shù)的算法。題目分析按層次遍歷，設一隊列Q，用front和

23、rear分別指向隊頭和隊尾元素，last指向各層最右結(jié)點位置?！舅惴?.41】intLevel_x(BiTree bt，ElemType x)求值為x的結(jié)點在樹中層次數(shù)if(bt!=null)intfront=0,last=1,rear=1,level=1;level記層次數(shù)BiTree Q;Q1=bt;根結(jié)點入隊while(frontdata=x)printf(“%3dn”,level); return level;值為x的結(jié)點在樹中層次數(shù)if(bt-lchild!=null) Q+rear=bt-lchild;左子女入隊列if(bt-rchild!=null) Q+rear=bt-rchi

24、ld;右子女入隊列if(front=last) last=rear; level+; 本層最后一個結(jié)點已處理完 算法結(jié)束6.42已知深度為h的二叉樹以一維數(shù)組作為存儲結(jié)構(gòu)。試編寫算法求該二叉樹中葉子的個數(shù)。【題目分析】按完全二叉樹形式順序存儲二叉樹時，無元素的位置要當作“虛結(jié)點”。設虛結(jié)點取二叉樹結(jié)點以外的值（這里設為0）。設結(jié)點序號為i,則當i(2h-1)/2時，若i位置不是虛結(jié)點，則必為葉子結(jié)點。【算法6.42】intLeaves(intBT,int n)計算深度為h以一維數(shù)組BT作為存儲結(jié)構(gòu)的二叉樹的葉子結(jié)點數(shù)，n為數(shù)組長度intnum=0;記葉子結(jié)點數(shù)for(i=0;in;i+)if(

25、BTi!=0)if(i=n/2)if(BT2*i=0 & 2*i+1=n & BT2*i+1=0) num+;若結(jié)點無孩子，則是葉子else if(BTi!=0) num+;存儲在數(shù)組后一半的元素是葉子結(jié)點returnnum;結(jié)束Leaves6.43已知二叉樹以一維數(shù)組作為存儲結(jié)構(gòu)。試編寫算法求下標為i和j的兩個結(jié)點的最近共同祖先結(jié)點的值。【題目分析】二叉樹順序存儲，是按完全二叉樹的格式存儲，利用完全二叉樹雙親結(jié)點與子女結(jié)點編號間的關(guān)系，求下標為i和j的兩結(jié)點的雙親，雙親的雙親，等等，直至找到最近的公共祖先?！舅惴?.43】voidAncestor(ElemType bt,intn,i,j,)

26、求順序存儲在bt1.n的二叉樹中下標為i和j的兩個結(jié)點的最近公共祖先結(jié)點if(i1 | jj) i=i/2; 下標為i的結(jié)點的雙親結(jié)點的下標elsej=j/2;下標為j的結(jié)點的雙親結(jié)點的下標printf(“所查結(jié)點的最近公共祖先的下標是%d，值是%d”,i,Ai);設元素類型整型。Ancestor6.44已知一棵完全二叉樹順序存儲于向量s1.n中，試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。【算法6.44】BiTree Creat(ElemType A,inti)n個結(jié)點的完全二叉樹存于一維數(shù)組A中，本算法建立二叉鏈表表示的完全二叉樹BiTree tree;if(idata=Ai;if(

27、2*in) tree-lchild=null；elsetree-lchild=Creat(A,2*i)；if(2*i+1n) tree-rchild=null；elsetree-rchild=Creat(A,2*i+1)；return(tree)；Creat【算法討論】初始調(diào)用時,i=1。6.45編寫算法判別給定二叉樹是否為完全二叉樹?！绢}目分析】判定是否是完全二叉樹，可以使用隊列，在遍歷中利用完全二叉樹“若某結(jié)點無左子女就不應有右子女”的原則進行判斷。具體說，在層次遍歷時，若碰到一個空指針后，在遍歷結(jié)束前又碰到結(jié)點，則結(jié)論為該二叉樹不是完全二叉樹。【算法6.45】intJudgeComple

28、te(BiTree bt)判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0inttag=0; 出現(xiàn)空指針時，置tag=1BiTree 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);左子女入隊elseif(p-lchild)return0; 前邊已有結(jié)點空，本結(jié)點不空 elsetag=1; 首次出現(xiàn)結(jié)點為空

29、if(p-rchild & !tag) QueueIn(Q,p-rchild);右子女入隊elseif(p-rchild)return0;elsetag=1; whilereturn1; JudgeComplete算法討論完全二叉樹證明還有其它方法。判斷時易犯的錯誤是證明其左子樹和右子樹都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯誤結(jié)論。6.46設樹以雙親表示法存儲，編寫計算樹的深度的算法?！绢}目分析】以雙親表示法作樹的存儲結(jié)構(gòu)，對每一結(jié)點，找其雙親，雙親的雙親，直至（根）結(jié)點,就可求出每一結(jié)點的層次，取其結(jié)點的最大層次就是樹的深度?！舅惴?.46】intDepth(Ptree t)求

30、以雙親表示法為存儲結(jié)構(gòu)的樹的深度intmaxdepth=0;for(i=1;i0)temp+; f=t.nodesf.parent; 深度加1,并取新的雙親if(tempmaxdepth)maxdepth=temp;最大深度更新return(maxdepth);返回樹的深度 結(jié)束Depth6.47已知在二叉樹中，*root為根結(jié)點，*p和*q為二叉樹中兩個結(jié)點，試編寫求距離它們最近的共同祖先的算法?！绢}目分析】后序遍歷最后訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸遍歷。棧中存放二叉樹結(jié)點的指針，當訪問到某結(jié)點時，棧中所有元素均為該結(jié)點的祖先。本題要找p和q 的最近共同祖先結(jié)點r

31、 ,不失一般性，設p在q的左邊。后序遍歷必然先遍歷到結(jié)點p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配（相等）的元素就是結(jié)點p 和q的最近公共祖先。【算法6.47】先設二叉樹的結(jié)點結(jié)構(gòu)為：typedefstructBiTree t;inttag;tag=0表示結(jié)點的左子女已訪問，tag=1為右子女已訪問stack;stack s,s1;棧，容量足夠大BiTree Ancestor(BiTree root, BiTree p, BiTree q, BiTree r)求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點rtop=0;

32、bt=root;while(bt!=null |top0)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;i0;i-)將棧中元素的樹結(jié)點到s1去匹配pp=si.t;for(j=top1;j0;j-)if(s1j.t=pp)printf(“共同的祖先已找到n”)；return(pp);while(top!=0 & stop.tag=1) top-; 退棧if(top!=0)stop.tag=1;

33、bt=stop.t-rchild;沿右分枝向下遍歷結(jié)束while(bt!=null |top0)return(null);、p無公共祖先結(jié)束Ancestor6.48以二叉鏈表作為存儲結(jié)構(gòu)，設計按層次遍歷二叉樹的算法。【算法6.48】voidLevel(BiTree bt) 層次遍歷二叉樹if(bt)QueueInit(Q); Q是以二叉樹結(jié)點指針為元素的隊列QueueIn(Q,bt)；while(!QueueEmpty(Q)p=QueueOut(Q);出隊printf(p-data);訪問結(jié)點if(p-lchild) QueueIn(Q,p-lchild); 非空左子女入隊if(p-rchil

34、d) QueueIn(Q,p-rchild); 非空右子女入隊if(bt)6.49編寫算法查找二叉鏈表中數(shù)據(jù)域值為x的結(jié)點（假定各結(jié)點的數(shù)據(jù)域值各不相同），并打印出x所有祖先的數(shù)據(jù)域值。【題目分析】后序遍歷最后訪問根結(jié)點，當訪問到值為x的結(jié)點時，棧中所有元素均為該結(jié)點的祖先。【算法6.49】voidSearch(BiTree bt,ElemType x)在二叉樹bt中，查找值為x的結(jié)點，并打印其所有祖先typedefstructBiTree t;inttag;tag=0表示左子女被訪問，tag=1右子女被訪問stack;stack s;棧容量足夠大top=0;while(bt!=null|to

35、p0)while(bt!=null & bt-data!=x)結(jié)點入棧 s+top.t=bt; stop.tag=0; bt=bt-lchild;沿左分枝向下if(bt-data=x)printf(“所查結(jié)點的所有祖先結(jié)點的值為:n”);找到x for(i=1;idata);return; 輸出祖先值后結(jié)束while(top!=0 & stop.tag=1) top-;退棧（空遍歷）if(top!=0)stop.tag=1;bt=stop.t-rchild; 沿右分枝向下遍歷while(bt!=null|top0) 結(jié)束search6.50設計這樣的二叉樹，用它可以表示父子、夫妻和兄弟三種關(guān)系

36、，并編寫一個查找任意父親結(jié)點的所有兒子結(jié)點的過程?！绢}目分析】用二叉樹表示出父子，夫妻和兄弟三種關(guān)系，可以用根結(jié)點表示父（祖先），根結(jié)點的左子女表示妻，妻的右子女表示子。這種二叉樹可以看成類似樹的孩子兄弟鏈表表示法；根結(jié)點是父，根無右子女，左子女表示妻，妻的右子女（右子女的右子女等）均可看成兄弟（即父的所有兒子），兄弟結(jié)點又成為新的父，其左子女是兄弟（父的兒子）妻，妻的右子女（右子女的右子女等）又為兒子的兒子等等。首先遞歸查找某父親結(jié)點，若查找成功，則其左子女是妻，妻的右子女及右子女的右子女等均為父親的兒子?！舅惴?.50】BiTree Search(BiTree t,ElemType fat

37、her)在二叉樹上查找值為father的結(jié)點inttag=0;if(t=null) p=null;二叉樹上無father結(jié)點elseif(t-data=father)tag=1; p=t;查找成功elsep=Search(t-lchild,father);if(tag=0)p=Search(t-rchild,father);returnp;結(jié)束SearchvoidPrintSons(BiTree t,ElemType x)在二叉樹上查找結(jié)點值為x的所有的兒子p=Serach(t,x); 在二叉樹t上查找父結(jié)點xif(p & p-lchild) 存在父結(jié)點,且有妻q=p-lchild; q=q-

38、rchild;先指向其妻結(jié)點，再找到第一個兒子while(q!=null)printf(q-data); q=q-rchild;輸出父的所有兒子 結(jié)束PrintSons6.51 編寫遞歸算法判定兩棵二叉樹是否相等?！绢}目分析】首先判斷二叉樹的根是否相等，如是，再判斷其左、右子樹是否相等?！舅惴?.51】intBTEqual(BiTree t, BiTree x)判定二叉樹t和二叉樹x是否相等if(!t & !x)returntrue; if(t & x & t-data=x-data & BTEqual(t-lchild,x-lchild) & BTEqual(t-rchild,x-rchil

39、d)returnture; else returnfalse;6.52已知一棵高度為具有個結(jié)點的二叉樹，按順序方式存儲，編寫將樹中最大序號葉子結(jié)點的祖先結(jié)點全部打印輸出的算法?！绢}目分析】二叉樹中最大序號的葉子結(jié)點,是在順序存儲方式下編號最大的結(jié)點【算法6.52】voidAncesstor(ElemType bt)打印最大序號葉子結(jié)點的全部祖先c=m;m=2K-1while(btc=0) c-;找最大序號葉子結(jié)點,該結(jié)點存儲時在最后f=c/2; c的雙親結(jié)點fwhile(f!=0) 從結(jié)點c的雙親結(jié)點直到根結(jié)點，路徑上所有結(jié)點均為祖先結(jié)點printf(btf); f=f/2; 逆序輸出，最老的

40、祖先最后輸出結(jié)束6.53設二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，編寫算法對二叉樹進行非遞歸的中序遍歷。【算法6.53】voidInOrder(BiTree bt)對二叉樹進行非遞歸中序遍歷 BiTree s,p=bt;s是元素為二叉樹結(jié)點指針的棧，容量足夠大inttop=0;while(p | top0) while(p) s+top=p; bt=p-lchild; 沿左子樹向下if(top0)p=stop-; printf(p-data); p=p-rchild; 退棧，訪問，轉(zhuǎn)右子樹結(jié)束6.54設T是一棵滿二叉樹，寫一個把T的后序遍歷序列轉(zhuǎn)換為先序遍歷序列的遞歸算法。【題目分析】對一般二叉樹，僅根

41、據(jù)一個先序（或中序、或后序）遍歷，不能確定另一個遍歷序列。但由于滿二叉樹“任一結(jié)點的左右子樹均含有數(shù)量相等的結(jié)點”，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列。【算法6.54】voidPostToPre(ElemType post,pre,intl1,h1,l2,h2)將滿二叉樹的后序序列轉(zhuǎn)為先序序列，l1,h1,l2,h2是序列初始和最后結(jié)點的下標。if(h1=l1)prel2=posth1;根結(jié)點visit(prel2);訪問根結(jié)點half=(h1-l1)/2;左或右子樹的結(jié)點數(shù)PostToPre(post,pre,l1,l1+half-1,l2+1,l2+half)將左子樹后序序列轉(zhuǎn)為

42、先序序列PostToPre(post,pre,l1+half,h1-1,l2+half+1,h2)將右子樹后序序列轉(zhuǎn)為先序序列 PostToPre t6.55若二叉樹BT的每個結(jié)點，其左、右子樹都為空，或者其左、右子樹都不空，這種二叉樹有時稱為“嚴格二叉樹”。由“嚴格二叉樹”的前序序列和后序序列可以唯一確定該二叉樹。寫出根據(jù)這種二叉樹的前序序列和后序序列確定該二叉樹的遞歸算法。【問題分析】前序序列的第一個結(jié)點是二叉樹的根，若該結(jié)點后再無其它結(jié)點，則該結(jié)點是葉子；否則，該結(jié)點必有左、右子樹，且根結(jié)點后的第一個結(jié)點就是左子樹的根。到后序序列中查找這個左子樹的根，它將后序序列分成左、右兩部分：左部分

43、(包括所查到的結(jié)點)是二叉樹的左子樹(可能為空)，右部分(除去最后的根結(jié)點)則是右子樹(可能為空)。這樣，在確定根結(jié)點后，可遞歸確定左、右子樹?！舅惴?.55】void creat(BiTree *BT,char pren,char postn,int l1,int h1,int l2,int h2)由嚴格二叉樹的前序序列pre(l1:h1)和后序序列post(l2:h2)建立二叉樹 BiTree p=*BT;if(l1data=prel1;前序序列的第一個元素是根if(l1=h1) p-lchild=p-rchild=null; 葉子結(jié)點else分支結(jié)點 for(int i=l2;ilchi

44、ld), pre,post,l1+1,l1+L,l2,i);creat(&(p-rchild), pre,post,l1+L+1,h1,i+1,h2-1);elseif結(jié)束6.56編寫一個遞歸算法，利用葉結(jié)點中空的右鏈指針域rchild，將所有葉結(jié)點自左至右鏈接成一個單鏈表，算法返回最左葉結(jié)點的地址（鏈頭）。【題目分析】葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設置前驅(qū)結(jié)點指針pre，初始為空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點的rchild為空?！舅惴?.56】LinkedList head,pre=null;全局變

45、量LinkedList InOrder(BiTree bt)中序遍歷二叉樹bt，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為headif(bt)InOrder(bt-lchild);中序遍歷左子樹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; 設置鏈表尾return(head); InOrder6.57已知有一棵二叉鏈表表示的二叉樹，編寫算法，輸出從根結(jié)點到葉子結(jié)點的最長一枝上的所有結(jié)點?！绢}目分析】后序遍歷時棧中保留當前結(jié)點的祖先的信息，用一變量保存棧的最高棧頂