【正文】 樹(shù)上的結(jié)點(diǎn)，root之后的應(yīng)該是右子樹(shù)上的結(jié)點(diǎn)，依次類(lèi)推，便可遞歸得到一棵完整的、確定的二叉樹(shù)。[樣例輸入]abdecdbeac[樣例輸出]debca[參考程序]Program p3(Input, Output)；Var s1, s2 : String；Procedure try(l1, r1, l2, r2 : Integer)； {遞歸、后序}Var m : Integer；Begin m := pos(s1[l1], s2)； {求l1的第一個(gè)字符在l2中的位置可以同理推出：已知一棵二叉樹(shù)的后序遍歷結(jié)果和中序遍歷結(jié)果也可以確定一棵二叉樹(shù)。由于n個(gè)結(jié)點(diǎn)的樹(shù)可以轉(zhuǎn)換成根結(jié)點(diǎn)固定的、下面有n1個(gè)結(jié)點(diǎn)的二叉樹(shù),所以可以推出：Tn=B（n1）。1．先序遍歷的操作定義如下： 若二叉樹(shù)為空，則空操作，否則① 訪問(wèn)根結(jié)點(diǎn)② 先序遍歷左子樹(shù)③ 先序遍歷右子樹(shù)很明顯，這是一種遞歸定義，下面給出一種手工方法（括號(hào)法）求先序遍歷的結(jié)果。如何轉(zhuǎn)換呢？一般方法如下：1．將樹(shù)中每個(gè)結(jié)點(diǎn)除了最左邊的一個(gè)分支保留外，其余分支都去掉；2．從最左邊結(jié)點(diǎn)開(kāi)始畫(huà)一條線，把同一層上的兄弟結(jié)點(diǎn)都連起來(lái)；3．以整棵樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針大致旋轉(zhuǎn)45度。39。 bt 圖10例2：醫(yī)院設(shè)置 [問(wèn)題描述] 設(shè)有一棵二叉樹(shù)（如圖11），其中圈中的數(shù)字表示結(jié)點(diǎn)中居民的人口，圈邊上數(shù)字表示結(jié)點(diǎn)編號(hào)。2．如果2*in，則結(jié)點(diǎn)i為葉結(jié)點(diǎn)；否則左孩子編號(hào)為2*i。性質(zhì)2：深度為k的二叉樹(shù)至多有2k –1個(gè)結(jié)點(diǎn)（k=1）。39。所以單詞數(shù)量最多為26+676+5997=6699。但，本問(wèn)題只是問(wèn)你結(jié)點(diǎn)總數(shù)，而非建樹(shù)方案，且有32K文件，所以應(yīng)該考慮能不能通過(guò)不建樹(shù)就直接算出結(jié)點(diǎn)數(shù)？為了說(shuō)明問(wèn)題的本質(zhì)，我們給出一個(gè)定義：一個(gè)單詞相對(duì)于另一個(gè)單詞的差：設(shè)單詞1的長(zhǎng)度為L(zhǎng)，且與單詞2從第N位開(kāi)始不一致，則說(shuō)單詞1相對(duì)于單詞2的差為L(zhǎng)N+1，這是描述單詞相似程度的量。4．例如圖3左邊的單詞列表就對(duì)應(yīng)于右邊的單詞查找樹(shù)。按照先序遍歷思想編寫(xiě)的遞歸過(guò)程如下：Procedure tra1(t,m) {訪問(wèn)以t為根結(jié)點(diǎn)的含有m棵子樹(shù)的過(guò)程}BeginIf t Nil Then Begin Write(t^.data,’ ’)； {訪問(wèn)根結(jié)點(diǎn)} For I:=1 To m Do {前序遍歷各子樹(shù)}tra1(t^.child[I],m)；End；End；也可以用堆棧的方法編寫(xiě)這個(gè)程序，留給讀者作為練習(xí)。3．父親孩子表示法：利用雙鏈表結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和二個(gè)指針域，一個(gè)指向該結(jié)點(diǎn)的若干孩子結(jié)點(diǎn)，一個(gè)指向其父結(jié)點(diǎn)。1．父親表示法：定義一個(gè)數(shù)組，每個(gè)數(shù)組元素為一個(gè)記錄，除了存放一個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息外，還存放該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)。如圖1中，結(jié)點(diǎn)1和結(jié)點(diǎn)8之間存在著一條路徑，并可用（8）表示這條路徑，該條路徑的長(zhǎng)度為3。一棵樹(shù)中所有結(jié)點(diǎn)的層次的最大值稱(chēng)為樹(shù)的深度（depth），圖1所示這棵樹(shù)的深度為4。2．在用上述圖形表示的樹(shù)結(jié)構(gòu)中，對(duì)兩個(gè)用線段（稱(chēng)為樹(shù)枝）連接的相關(guān)聯(lián)的結(jié)點(diǎn)，稱(chēng)上端的結(jié)點(diǎn)為下端結(jié)點(diǎn)的父結(jié)點(diǎn)，稱(chēng)下端的結(jié)點(diǎn)為上端結(jié)點(diǎn)的子結(jié)點(diǎn)，稱(chēng)同一個(gè)父結(jié)點(diǎn)的多個(gè)子結(jié)點(diǎn)為兄弟結(jié)點(diǎn)。在樹(shù)型結(jié)構(gòu)中，二叉樹(shù)是最常用的結(jié)構(gòu)，它的分支個(gè)數(shù)確定，又可以為空，具有良好的遞歸特性，特別適宜于程序設(shè)計(jì)，因此我們常常將一般樹(shù)型結(jié)構(gòu)轉(zhuǎn)換成二叉樹(shù)進(jìn)行處理。在許多算法中，常用樹(shù)型結(jié)構(gòu)描述問(wèn)題的求解過(guò)程、所有解的狀態(tài)和求解的對(duì)策等。樹(shù)中各結(jié)點(diǎn)的度的最大值稱(chēng)為這棵樹(shù)的度（又稱(chēng)寬度），圖1所示這棵樹(shù)的（寬）度為3。如結(jié)點(diǎn)4的層次為2，結(jié)點(diǎn)7的層次為3，結(jié)點(diǎn)9的層次為4?？捎寐窂剿?jīng)過(guò)的結(jié)點(diǎn)序列表示路徑，路徑的長(zhǎng)度等于路徑上的結(jié)點(diǎn)個(gè)數(shù)減1。樹(shù)的存儲(chǔ)結(jié)構(gòu)也有多種形式，其中使用較多的采是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，下面給出幾種常見(jiàn)的存儲(chǔ)樹(shù)的數(shù)據(jù)結(jié)構(gòu)。由于每個(gè)結(jié)點(diǎn)都只存放各自孩子結(jié)點(diǎn)的編號(hào)，所以這種方法只能從根（父）結(jié)點(diǎn)遍歷到子結(jié)點(diǎn)，不能從某個(gè)子結(jié)點(diǎn)返回到它的父結(jié)點(diǎn)。圖1按照這個(gè)思想訪問(wèn)的結(jié)果為：{5，6，3，8，9}；很明顯，先序遍歷和后序遍歷兩種方法的定義是遞歸的，所以在程序?qū)崿F(xiàn)時(shí)往往也是采用遞歸的思想，既通常所說(shuō)的“深度優(yōu)先搜索”。單詞列表中的每個(gè)單詞，都是該單詞查找樹(shù)某個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的單詞；3．在滿足上述條件下，該單詞查找樹(shù)的結(jié)點(diǎn)數(shù)最少。對(duì)于當(dāng)前被處理的單詞和當(dāng)前樹(shù)：在根結(jié)點(diǎn)的子結(jié)點(diǎn)中找單詞的第一位字母，若存在則進(jìn)而在該結(jié)點(diǎn)的子結(jié)點(diǎn)中尋找第二位……如此下去直到單詞結(jié)束，即不需要在該樹(shù)中添加結(jié)點(diǎn)；或單詞的第n位不能被找到，即將單詞的第n位及其后的字母依次加入單詞查找樹(shù)中去。因?yàn)閱卧~不重復(fù)，所以長(zhǎng)度為1的單詞（單個(gè)字母）最多26個(gè)；長(zhǎng)度為2的單詞最多為26*26=676個(gè)；因?yàn)槊總€(gè)單詞后都要一個(gè)換行符（換行符在計(jì)算機(jī)中占2個(gè)字節(jié)），所以總共已經(jīng)占用的空間為：（1+2）*26+（2+2）*676=2782字節(jié)；剩余字節(jié)（327682782=29986字節(jié)）分配給長(zhǎng)度為3的單詞（長(zhǎng)度為3的單詞最多有 26*26*26=17576個(gè)）有29986/（3+2）≈5997。)； Reset(Input)； Assign(Output,39。二、二叉樹(shù)的性質(zhì)：性質(zhì)1：在二叉樹(shù)的第i層上至多有2i1個(gè)結(jié)點(diǎn)（i=1）。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為trunc(LOG2n)+1 （trunc為取整函數(shù)）性質(zhì)5：一棵n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，對(duì)于任一編號(hào)為i結(jié)點(diǎn)，有：1．如果i=1,則結(jié)點(diǎn)i為根，無(wú)父結(jié)點(diǎn)；如果i1,則其父結(jié)點(diǎn)編號(hào)為trunc(i/2)。這樣的二叉樹(shù)稱(chēng)為表達(dá)式樹(shù)，如表達(dá)式（a+b/c）*(de)就可以表示成圖10。[參考程序]Program p2(Input, Output)；Var a : Array [1..100] Of Longint； g : Array [1..100, 1..100] Of Longint； n, i, j, k, l, r, min, total : Longint；Begin Assign(Input, 39。四、普通樹(shù)轉(zhuǎn)換成二叉樹(shù)由于二叉樹(shù)是有序的，而且操作和應(yīng)用更廣泛，所以在實(shí)際使用時(shí)，我們經(jīng)常把普通樹(shù)轉(zhuǎn)換成二叉樹(shù)進(jìn)行操作。下面以圖13所示的二叉樹(shù)為例分別講解這3種方法。圖15一般情況，一棵具有n(n0)個(gè)結(jié)點(diǎn)的二叉樹(shù)可以看成是由一個(gè)根結(jié)點(diǎn)、一棵具有i個(gè)結(jié)點(diǎn)的左子樹(shù)、和一棵具有ni1個(gè)結(jié)點(diǎn)的右子樹(shù)組成，其中0（無(wú)左子樹(shù)）=i=n1（無(wú)右子樹(shù)）,i=0表示無(wú)左子樹(shù)，i=n1表示無(wú)右子樹(shù)，根據(jù)乘法原理可以得出具有n個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹(shù)有Bn棵：Bn = （n0）特別地：Bn = 1 (n=0)我們可以利用生成函數(shù)（有興趣的同學(xué)自己查閱相關(guān)書(shū)籍）討論這個(gè)遞歸公式，得出：Bn=Cn2n /(n+1)。即：已知一棵二叉樹(shù)的先序遍歷結(jié)果和中序遍歷結(jié)果可以確定一棵二叉樹(shù)。} If m l2 Then try(l1 + 1, l1 + m l2, l2, m 1)； {遍歷第m個(gè)的左半邊} If m r2 Then try(l1 + m l2 + 1, r1, m + 1, r2)； {遍歷第m個(gè)的右半邊} Write(s1[l1]) End；Begin {main} Assign(Input，’’)； Reset(Input)；Assign(Onput，’’)；Rewrite(Onput)；Readln(s1)；Readln(s2)； try(1, Length(s1), 1, Length(s2))； Writeln Close(Input)；Close(Output)；End.20