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