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