【正文】 [樣例輸入]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é)點(diǎn)一律用小寫字母表示。構(gòu)造出這棵二叉樹(shù)的步驟如圖16：圖16例3: 二叉樹(shù)的遍歷問(wèn)題[問(wèn)題描述] 輸入一棵二叉樹(shù)的先序和中序遍歷序列，輸出其后序遍歷序列?？梢酝硗瞥觯阂阎豢枚鏄?shù)的后序遍歷結(jié)果和中序遍歷結(jié)果也可以確定一棵二叉樹(shù)。所以結(jié)點(diǎn)root正好把中序遍歷結(jié)果分成了兩部分，root之前的應(yīng)該是左子樹(shù)上的結(jié)點(diǎn)，root之后的應(yīng)該是右子樹(shù)上的結(jié)點(diǎn)，依次類推，便可遞歸得到一棵完整的、確定的二叉樹(shù)。即在二叉樹(shù)的先序遍歷結(jié)果中，第一個(gè)結(jié)點(diǎn)必是根，假設(shè)為root。八、由遍歷結(jié)果確定二叉樹(shù)的形態(tài)問(wèn)題下面我們換個(gè)角度考慮這個(gè)問(wèn)題，從二叉樹(shù)的遍歷已經(jīng)知道，任意一棵二叉樹(shù)的先序遍歷結(jié)果和中序遍歷結(jié)果都是唯一的。由于n個(gè)結(jié)點(diǎn)的樹(shù)可以轉(zhuǎn)換成根結(jié)點(diǎn)固定的、下面有n1個(gè)結(jié)點(diǎn)的二叉樹(shù),所以可以推出：Tn=B（n1）。在n很小時(shí)，很容易得出，B0=1，B1=1，B2=2，B3=5（見(jiàn)圖15）。“等價(jià)二叉樹(shù)”是指兩者不僅相似，而且所有對(duì)應(yīng)結(jié)點(diǎn)上的數(shù)據(jù)元素均相同。Procedure inorder(bt:tree)； {先序遍歷bt所指的二叉樹(shù)} Var stack:Array[1..n] Of tree； {棧}top:integer； {棧頂指針}p:tree；Begintop:=0；While Not ((bt=Nil)And(top=0)) DoBegin While btNil Do Begin {非葉結(jié)點(diǎn)}Write(bt^.data)； {訪問(wèn)根}top:=top+1； {右子樹(shù)壓棧}stack[top]:=bt^.rchild；bt:=bt^.lchild； {遍歷左子樹(shù)}End；If top0 Then Begin {棧中所有元素出棧，遍歷完畢} b:=stack[top]；top:=top1； End； End； End；關(guān)于前面講的表達(dá)式樹(shù)，我們可以分別用先序、中序、后序的遍歷方法得出完全不同的遍歷結(jié)果，對(duì)于圖14采用三種遍歷后的結(jié)果如下，它們正好對(duì)應(yīng)著表達(dá)式的三種表示方法： +a*bcd/ef (前綴表示、波蘭式)a+b*cde/f (中綴表示、代數(shù)式)abcd*+ef/ (后綴表示、逆波蘭式) 圖14六、二叉樹(shù)的其它重要操作：除了“遍歷”以外，二叉樹(shù)的其它重要操作還有：建立一棵二叉樹(shù)、插入一個(gè)結(jié)點(diǎn)到二叉樹(shù)中、刪除結(jié)點(diǎn)或子樹(shù)等，下面分別給出基本算法框架。1．先序遍歷的操作定義如下： 若二叉樹(shù)為空，則空操作，否則① 訪問(wèn)根結(jié)點(diǎn)② 先序遍歷左子樹(shù)③ 先序遍歷右子樹(shù)很明顯，這是一種遞歸定義，下面給出一種手工方法（括號(hào)法）求先序遍歷的結(jié)果。遍歷方法共有3種：先序（根）遍歷，中序（根）遍歷， 圖13后序（根）遍歷。所謂二叉樹(shù)的遍歷是指按一定的規(guī)律和次序訪問(wèn)樹(shù)中的各個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。1．若F為空，即m=0，則 B為空樹(shù)；2．若F非空，即m0，則B的根root即為森林中第一棵樹(shù)的根root(T1)；B的左子樹(shù)lb是從T1中根結(jié)點(diǎn)的子樹(shù)森林F1={T11，T12，…，T1m1}轉(zhuǎn)換而成的二叉樹(shù)；其右子樹(shù)rb是從森林F’ ={T2，T3，…，Tm}轉(zhuǎn)換而成的二叉樹(shù)。如何轉(zhuǎn)換呢？一般方法如下：1．將樹(shù)中每個(gè)結(jié)點(diǎn)除了最左邊的一個(gè)分支保留外，其余分支都去掉；2．從最左邊結(jié)點(diǎn)開(kāi)始畫一條線，把同一層上的兄弟結(jié)點(diǎn)都連起來(lái)；3．以整棵樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針大致旋轉(zhuǎn)45度。除了簡(jiǎn)單的窮舉法外，還有更好的時(shí)間復(fù)雜度為O(n)的算法，我們講在后面的章節(jié)中繼續(xù)討論。每個(gè)城市里面都有一定數(shù)量的居民，但是數(shù)量并不一定相等，每條公路的長(zhǎng)度也不一定相等。39。39。當(dāng)然也可以用雙鏈表結(jié)構(gòu)或帶父結(jié)點(diǎn)信息的數(shù)組存儲(chǔ)結(jié)構(gòu)來(lái)解決，但實(shí)際操作稍微麻煩了一點(diǎn)。[輸出格式] ，該文件只有一個(gè)整數(shù)，表示最小距離和。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和=4*2+13+20+40=81……[輸入格式] ，其中第一行一個(gè)整數(shù)n，表示樹(shù)的結(jié)點(diǎn)數(shù)（n=100）。 bt 圖10例2：醫(yī)院設(shè)置 [問(wèn)題描述] 設(shè)有一棵二叉樹(shù)（如圖11），其中圈中的數(shù)字表示結(jié)點(diǎn)中居民的人口，圈邊上數(shù)字表示結(jié)點(diǎn)編號(hào)。二叉樹(shù)在處理表達(dá)式時(shí)經(jīng)常用到，一般用葉結(jié)點(diǎn)表示運(yùn)算數(shù)，分支結(jié)點(diǎn)表示運(yùn)算符。 bt圖92．順序存儲(chǔ)結(jié)構(gòu):即幾個(gè)數(shù)組加一個(gè)指針變量，一般用在滿二叉樹(shù)和完全二叉樹(shù)中，將每個(gè)結(jié)點(diǎn)編號(hào)后作為數(shù)組的下標(biāo)變量值，基本數(shù)據(jù)結(jié)構(gòu)定義如下：Const n=10； {最多10個(gè)結(jié)點(diǎn)}Var data:Array[1..n] Of Char； {n個(gè)結(jié)點(diǎn)的數(shù)據(jù)域} lchild:Array[1..n] Of Integer； {n個(gè)結(jié)點(diǎn)的左孩子} rchild:Array[1..n] Of Integer； { n個(gè)結(jié)點(diǎn)的右孩子} bt:Integer； {根結(jié)點(diǎn)指針}這種結(jié)構(gòu)可以很方便地從根結(jié)點(diǎn)往下遍歷，但是如果想從某個(gè)分支結(jié)點(diǎn)或葉結(jié)點(diǎn)遍歷整棵樹(shù)，則還需設(shè)置一個(gè)父結(jié)點(diǎn)數(shù)組，操作也教麻煩。三、 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)與普通樹(shù)的存儲(chǔ)結(jié)構(gòu)基本相同，有鏈?zhǔn)胶晚樞虼鎯?chǔ)兩種方法。2．如果2*in，則結(jié)點(diǎn)i為葉結(jié)點(diǎn)；否則左孩子編號(hào)為2*i。圖7和圖8所示的兩棵二叉樹(shù)就不是完全二叉樹(shù)，請(qǐng)讀者思考為什么？ 圖7 圖8性質(zhì)3：對(duì)任何一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則一定滿足：n0=n2+1。 如圖6就是一個(gè)深度為4，結(jié)點(diǎn)數(shù)為12的完全二叉樹(shù)。圖5是深度為4的滿二叉樹(shù)，這種樹(shù)的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都達(dá)到了最大值。性質(zhì)2：深度為k的二叉樹(shù)至多有2k –1個(gè)結(jié)點(diǎn)（k=1）。它有如下5種基本形態(tài)：圖4第一節(jié)講述的樹(shù)的一些術(shù)語(yǔ)、概念也基本適用于二叉樹(shù)，但二叉樹(shù)與樹(shù)也有很多不同，如：二叉樹(shù)的每個(gè)結(jié)點(diǎn)至多只能有兩個(gè)結(jié)點(diǎn)，二叉樹(shù)一定是有序的，二叉樹(shù)可以為空（但樹(shù)不能為空，至少要有1個(gè)結(jié)點(diǎn)）。39。39。39。39。這樣，排序時(shí)用a比較，但只要交換index的值就可以了。這樣既省略了一個(gè)存放單詞長(zhǎng)度的數(shù)組，又方便且節(jié)省了一點(diǎn)空間。所以單詞數(shù)量最多為26+676+5997=6699。當(dāng)然應(yīng)該盡可能地存放較短的單詞。注意：第一個(gè)單詞相對(duì)于“空”的差為該單詞的長(zhǎng)度；④ 累加和再加上1（根結(jié)點(diǎn)），輸出結(jié)果。單詞的字典順序排列后的序列則具有類似的特性，即在一個(gè)字典順序序列中，第m個(gè)單詞相對(duì)于第m1個(gè)單詞的差必定是它對(duì)于前m1個(gè)單詞的差中最小的。但，本問(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ì)于單詞