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

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

2、點(diǎn)數(shù)為n, 度為1的結(jié)點(diǎn)數(shù)為n1，則 n= n0+ n1+ n2 n=2n0+n1-1 1002=2n0+n1由于在完全二叉樹(shù)中，度為1的結(jié)點(diǎn)數(shù)n1至多為1，葉子數(shù)n0是整數(shù)。本題中度為1的結(jié)點(diǎn)數(shù)n1只能是0，故葉子結(jié)點(diǎn)的個(gè)數(shù)n0為501.注：解本題時(shí)要使用以上公式，不要先判斷完全二叉樹(shù)高10，前9層是滿(mǎn)二叉樹(shù)，第10層都是葉子，。雖然解法也對(duì)，但步驟多且復(fù)雜，極易出錯(cuò)。6.3 一棵124個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，最多有多少個(gè)結(jié)點(diǎn)。【解答】由公式n=2n0+n1-1,當(dāng)n1為1時(shí)，結(jié)點(diǎn)數(shù)達(dá)到最多248個(gè)。6.4一棵完全二叉樹(shù)有500個(gè)結(jié)點(diǎn)，請(qǐng)問(wèn)該完全二叉樹(shù)有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)度為1的結(jié)點(diǎn)？有

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

4、025211-1，故1025個(gè)結(jié)點(diǎn)的二叉樹(shù)最低高為11。6.7 一棵二叉樹(shù)高度為h，所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹(shù)最少有多少結(jié)點(diǎn)。【解答】第一層只一個(gè)根結(jié)點(diǎn)，其余各層都兩個(gè)結(jié)點(diǎn)，這棵二叉樹(shù)最少結(jié)點(diǎn)數(shù)是2h-1。6.8將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度是多少?！窘獯稹吭O(shè)含n個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度為h，則有nn2n0)的滿(mǎn)二叉樹(shù)對(duì)應(yīng)的森林由多少棵樹(shù)構(gòu)成。【解答】因?yàn)樵诙鏄?shù)轉(zhuǎn)換為森林時(shí)，二叉樹(shù)的根結(jié)點(diǎn)，根結(jié)點(diǎn)的右子女，右子女的右子女，都是樹(shù)的根，所以，高度為h(h0)的滿(mǎn)二叉樹(shù)對(duì)應(yīng)的森林由h棵樹(shù)構(gòu)成。6.11 某二叉樹(shù)結(jié)點(diǎn)的中序序列為BDAECF，后

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

6、結(jié)點(diǎn)無(wú)前驅(qū)，故該鏈域?yàn)榭铡Ｍ瑯臃治鲋雷詈蟊闅v的結(jié)點(diǎn)的右鏈域?yàn)榭?。故一棵左子?shù)為空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是2個(gè)。6.14 一棵左、右子樹(shù)均不空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是多少?【解答】1個(gè)。6.15 設(shè)B是由森林F變換得的二叉樹(shù)。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有幾個(gè)？【解答】n+1。森林中任何一個(gè)非終端結(jié)點(diǎn)在轉(zhuǎn)換成二叉樹(shù)時(shí)，其第一個(gè)子女結(jié)點(diǎn)成為該非終端結(jié)點(diǎn)的左子女，其余子女結(jié)點(diǎn)成為剛生成的左子女結(jié)點(diǎn)的右子女，右子女結(jié)點(diǎn)的右子女，最右子女結(jié)點(diǎn)的右鏈域?yàn)榭?。照此分析，n個(gè)非終端結(jié)點(diǎn)在轉(zhuǎn)換后，其子女結(jié)點(diǎn)中共有n個(gè)空鏈域。另外，森林中各棵樹(shù)的根結(jié)點(diǎn)

7、可以看做互為兄弟，轉(zhuǎn)換成二叉樹(shù)后也產(chǎn)生1個(gè)空鏈域。因此，本題的答案是n+1。6.16 試分別找出滿(mǎn)足以下條件的所有二叉樹(shù)： (1)二叉樹(shù)的前序序列與中序序列相同； (2) 二叉樹(shù)的中序序列與后序序列相同； (3)二叉樹(shù)的前序序列與后序序列相同；(4) 二叉樹(shù)的前序序列與層次序列相同；(5) 二叉樹(shù)的前序、中序與后序序列均相同。【解答】前序遍歷二叉樹(shù)的順序是“根左子樹(shù)右子樹(shù)”，中序遍歷的順序是“左子樹(shù)根右子樹(shù)”，后序遍歷順序是：“左子樹(shù)右子樹(shù)根，根據(jù)以上原則，本題解答如下：若前序序列與中序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)。若中序序列與后序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)

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

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

10、：(1)各層的結(jié)點(diǎn)個(gè)數(shù)是多少?(2)編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號(hào)是多少?(3)編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？(4)編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟結(jié)點(diǎn)的編號(hào)是多少？【解答】(1)kl(l為層數(shù)，按題意，根結(jié)點(diǎn)為0層)（2）因?yàn)樵摌?shù)每層上均有kl個(gè)結(jié)點(diǎn)，從根開(kāi)始編號(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=n1)的前一結(jié)點(diǎn)編號(hào)為i-1（其最右邊子女編號(hào)是(i-1)*k+1），故結(jié)點(diǎn) i的第 m個(gè)孩子的編號(hào)是(i-1)*k+1+m。(4) 根據(jù)以上分析，結(jié)點(diǎn)i有右兄弟的條件是，它不是雙親的從右

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

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

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

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

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

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

17、JKLMNO后序序列：CDEBFHIJGAMLONK【解答】森林的先序序列和后序序列對(duì)應(yīng)其轉(zhuǎn)換的二叉樹(shù)的先序序列和中序序列，應(yīng)先據(jù)此構(gòu)造二叉樹(shù)，再構(gòu)造出森林。6.30 畫(huà)出同時(shí)滿(mǎn)足下列兩條件的兩棵不同的二叉樹(shù)。(1)按先根序遍歷二叉樹(shù)順序?yàn)锳BCDE。(2)高度為5其對(duì)應(yīng)的樹(shù)（森林）的高度最大為4?！窘獯稹?6.31用一維數(shù)組存放的一棵完全二叉樹(shù)；ABCDEFGHIJKL。請(qǐng)寫(xiě)出后序遍歷該二叉樹(shù)的結(jié)點(diǎn)訪問(wèn)序列?！窘獯稹亢笮虮闅v該二叉樹(shù)的結(jié)點(diǎn)訪問(wèn)序列為：DECGHFBKJLIA6.32一棵二叉樹(shù)的先序、中序和后序序列如下，其中有部分未標(biāo)出，試構(gòu)造出該二叉樹(shù)。先序序列為：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設(shè)樹(shù)形T在后根次序下的結(jié)點(diǎn)排列和各結(jié)點(diǎn)相應(yīng)的度數(shù)如下：后根次序：次數(shù)：請(qǐng)畫(huà)出的樹(shù)形結(jié)構(gòu)圖。【解答】在樹(shù)在后根遍歷次序下，根結(jié)點(diǎn)在最后，任何結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都直接排在該結(jié)點(diǎn)之前。例如，挨著根結(jié)點(diǎn)的是根結(jié)點(diǎn)的最右邊的子女。每棵子樹(shù)的所有結(jié)點(diǎn)都聚集在一起，中間不會(huì)插入其它結(jié)點(diǎn)，也不會(huì)丟掉子樹(shù)的任何結(jié)點(diǎn)。按照這種理論解答本題，在遍歷次序中從右到左分析，A是根，它有4個(gè)子女，H是它的最右邊的子女（第4子女）。H有2個(gè)子女，L是H的最右邊的子女，L無(wú)子女，故I是H的第1子女。I又有2個(gè)子女：K和J，

19、二者均無(wú)子女。由此推斷出下一個(gè)結(jié)點(diǎn)G是根結(jié)點(diǎn)A的第3子女。，繼續(xù)構(gòu)造，直至最左面的結(jié)點(diǎn)B，結(jié)果樹(shù)形如下：6.34 若森林共有n個(gè)結(jié)點(diǎn)和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個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存放在二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中，試編寫(xiě)非遞歸算法對(duì)該樹(shù)進(jìn)行先序遍歷?！绢}目分析】二叉樹(shù)的順序存儲(chǔ)是

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

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

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

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

24、ld;右子女入隊(duì)列if(front=last) last=rear; level+; 本層最后一個(gè)結(jié)點(diǎn)已處理完 算法結(jié)束6.42已知深度為h的二叉樹(shù)以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)。試編寫(xiě)算法求該二叉樹(shù)中葉子的個(gè)數(shù)?！绢}目分析】按完全二叉樹(shù)形式順序存儲(chǔ)二叉樹(shù)時(shí)，無(wú)元素的位置要當(dāng)作“虛結(jié)點(diǎn)”。設(shè)虛結(jié)點(diǎn)取二叉樹(shù)結(jié)點(diǎn)以外的值（這里設(shè)為0）。設(shè)結(jié)點(diǎn)序號(hào)為i,則當(dāng)i(2h-1)/2時(shí)，若i位置不是虛結(jié)點(diǎn)，則必為葉子結(jié)點(diǎn)。【算法6.42】intLeaves(intBT,int n)計(jì)算深度為h以一維數(shù)組BT作為存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)，n為數(shù)組長(zhǎng)度intnum=0;記葉子結(jié)點(diǎn)數(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é)點(diǎn)無(wú)孩子，則是葉子else if(BTi!=0) num+;存儲(chǔ)在數(shù)組后一半的元素是葉子結(jié)點(diǎn)returnnum;結(jié)束Leaves6.43已知二叉樹(shù)以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)。試編寫(xiě)算法求下標(biāo)為i和j的兩個(gè)結(jié)點(diǎn)的最近共同祖先結(jié)點(diǎn)的值。【題目分析】二叉樹(shù)順序存儲(chǔ)，是按完全二叉樹(shù)的格式存儲(chǔ)，利用完全二叉樹(shù)雙親結(jié)點(diǎn)與子女結(jié)點(diǎn)編號(hào)間的關(guān)系，求下標(biāo)為i和j的兩結(jié)點(diǎn)的雙親，雙親的雙親，等等，直至找到最近的公共祖先?！舅惴?.43】voidAncestor(ElemType bt,intn,i,j,)

26、求順序存儲(chǔ)在bt1.n的二叉樹(shù)中下標(biāo)為i和j的兩個(gè)結(jié)點(diǎn)的最近公共祖先結(jié)點(diǎn)if(i1 | jj) i=i/2; 下標(biāo)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)elsej=j/2;下標(biāo)為j的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)printf(“所查結(jié)點(diǎn)的最近公共祖先的下標(biāo)是%d，值是%d”,i,Ai);設(shè)元素類(lèi)型整型。Ancestor6.44已知一棵完全二叉樹(shù)順序存儲(chǔ)于向量s1.n中，試編寫(xiě)算法由此順序存儲(chǔ)結(jié)構(gòu)建立該二叉樹(shù)的二叉鏈表?！舅惴?.44】BiTree Creat(ElemType A,inti)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存于一維數(shù)組A中，本算法建立二叉鏈表表示的完全二叉樹(shù)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)用時(shí),i=1。6.45編寫(xiě)算法判別給定二叉樹(shù)是否為完全二叉樹(shù)?！绢}目分析】判定是否是完全二叉樹(shù)，可以使用隊(duì)列，在遍歷中利用完全二叉樹(shù)“若某結(jié)點(diǎn)無(wú)左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。具體說(shuō)，在層次遍歷時(shí)，若碰到一個(gè)空指針后，在遍歷結(jié)束前又碰到結(jié)點(diǎn)，則結(jié)論為該二叉樹(shù)不是完全二叉樹(shù)?！舅惴?.45】intJudgeComple

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

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

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

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

32、bt=root;while(bt!=null |top0)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;i0;i-)將棧中元素的樹(shù)結(jié)點(diǎn)到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無(wú)公共祖先結(jié)束Ancestor6.48以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)按層次遍歷二叉樹(shù)的算法。【算法6.48】voidLevel(BiTree bt) 層次遍歷二叉樹(shù)if(bt)QueueInit(Q); Q是以二叉樹(shù)結(jié)點(diǎn)指針為元素的隊(duì)列QueueIn(Q,bt)；while(!QueueEmpty(Q)p=QueueOut(Q);出隊(duì)printf(p-data);訪問(wèn)結(jié)點(diǎn)if(p-lchild) QueueIn(Q,p-lchild); 非空左子女入隊(duì)if(p-rchil

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

35、p0)while(bt!=null & bt-data!=x)結(jié)點(diǎn)入棧 s+top.t=bt; stop.tag=0; bt=bt-lchild;沿左分枝向下if(bt-data=x)printf(“所查結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的值為: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設(shè)計(jì)這樣的二叉樹(shù)，用它可以表示父子、夫妻和兄弟三種關(guān)系

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

37、her)在二叉樹(shù)上查找值為father的結(jié)點(diǎn)inttag=0;if(t=null) p=null;二叉樹(shù)上無(wú)father結(jié)點(diǎn)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)在二叉樹(shù)上查找結(jié)點(diǎn)值為x的所有的兒子p=Serach(t,x); 在二叉樹(shù)t上查找父結(jié)點(diǎn)xif(p & p-lchild) 存在父結(jié)點(diǎn),且有妻q=p-lchild; q=q-

38、rchild;先指向其妻結(jié)點(diǎn)，再找到第一個(gè)兒子while(q!=null)printf(q-data); q=q-rchild;輸出父的所有兒子 結(jié)束PrintSons6.51 編寫(xiě)遞歸算法判定兩棵二叉樹(shù)是否相等?！绢}目分析】首先判斷二叉樹(shù)的根是否相等，如是，再判斷其左、右子樹(shù)是否相等?！舅惴?.51】intBTEqual(BiTree t, BiTree x)判定二叉樹(shù)t和二叉樹(shù)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已知一棵高度為具有個(gè)結(jié)點(diǎn)的二叉樹(shù)，按順序方式存儲(chǔ)，編寫(xiě)將樹(shù)中最大序號(hào)葉子結(jié)點(diǎn)的祖先結(jié)點(diǎn)全部打印輸出的算法?！绢}目分析】二叉樹(shù)中最大序號(hào)的葉子結(jié)點(diǎn),是在順序存儲(chǔ)方式下編號(hào)最大的結(jié)點(diǎn)【算法6.52】voidAncesstor(ElemType bt)打印最大序號(hào)葉子結(jié)點(diǎn)的全部祖先c=m;m=2K-1while(btc=0) c-;找最大序號(hào)葉子結(jié)點(diǎn),該結(jié)點(diǎn)存儲(chǔ)時(shí)在最后f=c/2; c的雙親結(jié)點(diǎn)fwhile(f!=0) 從結(jié)點(diǎn)c的雙親結(jié)點(diǎn)直到根結(jié)點(diǎn)，路徑上所有結(jié)點(diǎn)均為祖先結(jié)點(diǎn)printf(btf); f=f/2; 逆序輸出，最老的

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

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

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

43、(包括所查到的結(jié)點(diǎn))是二叉樹(shù)的左子樹(shù)(可能為空)，右部分(除去最后的根結(jié)點(diǎn))則是右子樹(shù)(可能為空)。這樣，在確定根結(jié)點(diǎn)后，可遞歸確定左、右子樹(shù)?！舅惴?.55】void creat(BiTree *BT,char pren,char postn,int l1,int h1,int l2,int h2)由嚴(yán)格二叉樹(shù)的前序序列pre(l1:h1)和后序序列post(l2:h2)建立二叉樹(shù) BiTree p=*BT;if(l1data=prel1;前序序列的第一個(gè)元素是根if(l1=h1) p-lchild=p-rchild=null; 葉子結(jié)點(diǎn)else分支結(jié)點(diǎn) 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編寫(xiě)一個(gè)遞歸算法，利用葉結(jié)點(diǎn)中空的右鏈指針域rchild，將所有葉結(jié)點(diǎn)自左至右鏈接成一個(gè)單鏈表，算法返回最左葉結(jié)點(diǎn)的地址（鏈頭）。【題目分析】葉子結(jié)點(diǎn)只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。【算法6.56】LinkedList head,pre=null;全局變

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