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