【正文】 定義如下：若二叉樹為空，則空操作，否則① 后序遍歷左子樹② 后序遍歷右子樹③ 訪問根結(jié)點可以根據(jù)以上方法，得出上圖后序遍歷的結(jié)果為：{7，4，5，2，8，9，6，3，1}顯然，以上3種遍歷方法都是采用遞歸的思想，下面以先序遍歷為例給出遞歸算法：Procedure preorder(bt:tree)；{先序遍歷根結(jié)點為bt的二叉樹的遞歸算法}Begin If btNil Then BeginWrite(bt^.data)；preorder(bt^.lchild)；preorder(bt^.rchild)； End；End；我們也可以把遞歸過程改成用棧實現(xiàn)的非遞歸過程，下面給出先序遍歷的非遞歸過程。第一節(jié)中的圖1所示的普通樹轉(zhuǎn)換成二叉樹的過程如圖12所示：圖12同樣我們可以把森林也轉(zhuǎn)換成二叉樹處理，假設F={T1，T2，…，Tm}是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B=(root,lb,rb)。)； Reset(Input)；Assign(Output, 39。現(xiàn)在要求在某個結(jié)點上建立一個醫(yī)院，使所有居民所走的路程之和為最小，同時約定，相鄰接點之間的距離為1。3．如果2*i+1n，則結(jié)點i無右孩子；否則右孩子編號為2*i+1。特別地，一棵深度為k且有2k –1個結(jié)點的二叉樹稱為滿二叉樹。)；Rewrite(Output)； Fillchar(a, sizeof(a), 0)； n := 0；{單詞個數(shù)} k := 0；{下標} While (Not Eof) Do {讀入文件中的單詞并且存儲到數(shù)組中} Begin Readln(s)； n := n+1； index[n] := k+1；{第n個單詞的首字母起點下標} For i:=1 To Length(s) Do {存入一個單詞} a[k+i] := s[i]； k := k+i+1； {為下個單詞的下標設定好初值,i即為當前單詞的長度} End； For i:=1 To n Do {n個單詞的字典排序} For j:=i+1 To n Do If cmp(index[i], index[j]) Then Begin t := index[i]；index[i] := index[j]；index[j] := t；End； tot := 0； {計數(shù)器} pre := 39。定義一個數(shù)組：a：array[1..32767] of char；把所有單詞連續(xù)存放起來，文件中每個單詞后的換行符轉(zhuǎn)換成數(shù)組中的一個“空格”字符。可見，將一個單詞加入單詞樹的時候，須加入的結(jié)點數(shù)等于該單詞樹中已有單詞的差的最小值。注意，對一個確定的單詞列表，請統(tǒng)計對應的單詞查找樹的結(jié)點數(shù)（包含根結(jié)點）。層次遍歷應用也較多，實際上就是我們所說的“廣度優(yōu)先搜索”?？朔松鲜龅?種存儲方法的缺點，假設樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10；Type tree=^node； node=Record data:Char； child:Array[1..m] Of tree； father:treeEnd；Var t:tree；4．孩子兄弟表示法：有些程序中需要對兄弟結(jié)點進行處理，這種情況下，可以使用另外一種雙鏈表結(jié)構(gòu)，每個結(jié)點包括一個數(shù)據(jù)域和二個指針域，一個指針指向該結(jié)點的第一個孩子結(jié)點，一個指針指向該結(jié)點的下一個兄弟結(jié)點。數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10； {樹的結(jié)點數(shù)}Type node=Record data:Integer； {數(shù)據(jù)域} parent:Integer； {指針域} End；Var tree:Array[1..m] Of node；這種方法充分利用了樹中除根結(jié)點外每個結(jié)點都有唯一的父結(jié)點這個性質(zhì)，很容易找到樹根（可以規(guī)定根結(jié)點的父結(jié)點為0），但找孩子時卻需要遍歷整個線性表。從根結(jié)點出發(fā)，到樹中的其余結(jié)點一定存在著一條路徑。4．若樹中各結(jié)點的子樹是按照一定的次序從左向右安排的，它們之間的次序不能互換，這樣的樹稱之為有序樹，否則稱之為無序樹。如結(jié)點1是結(jié)點4的父結(jié)點，結(jié)點 4都是結(jié)點1的子結(jié)點，它們又是兄弟結(jié)點，同時結(jié)點2又是結(jié)點6的父結(jié)點。第一節(jié) 樹一、樹的定義一棵樹（tree）是由n（n0）個元素組成的有限集合，其中：1．每個元素稱為結(jié)點(node)；2．有一個特定的結(jié)點，稱為根結(jié)點或樹根（root）；3．除根結(jié)點外，其余結(jié)點被分成m（m=0）個互不相交的有限集合T0,T1,T2,……Tm1，而每一個子集Ti又都是一棵樹（稱為原樹的子樹subtree）。樹在計算機領(lǐng)域中也有廣泛應用，如在編譯系統(tǒng)中，用樹表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)是數(shù)據(jù)庫層次模型的基礎(chǔ)，也是各種索引和目錄的主要組織形式。根結(jié)點以外的分支結(jié)點又稱為內(nèi)部結(jié)點（如結(jié)點7）。3．定義一棵樹的根結(jié)點的層次（level）為1，其它結(jié)點的層次等于它的父結(jié)點的層次數(shù)加1。圖2，如果從一個結(jié)點出發(fā)，按層次自上而下沿著一個個樹枝能到達另一結(jié)點，稱它們之間存在著一條路徑。用括號表示法表示圖1的步驟如下：=（T）=（1（T1，T2 ，T3 ）） {A是根結(jié)點，有3棵子樹，用逗號隔開}=（1（2（T11，T12），3，4（T31））） {分別對3棵子樹做同樣的操作}=（1（2（5，6），3，4（7（T311，T312））））=（1（2（5，6），3，4（7（8，9））））實際上，以上方法是按照樹的層次逐步展開，直到所有結(jié)點都已列出。有興趣的同學可以參考有關(guān)書籍與程序。圖1層次遍歷的結(jié)果為：{1，2，3，4，5，6，7，8，9}；4．葉結(jié)點遍歷：有時我們把所有的數(shù)據(jù)信息都存放在葉結(jié)點中，而其余結(jié)點都是用來表示數(shù)據(jù)之間的某種分支或?qū)哟侮P(guān)系，這種情況就用這種方法。為了提高查找和定位的速度，通常都畫出與單詞列表所對應的單詞查找樹，其特點如下：1．根結(jié)點不包含字母，除根結(jié)點外每一個結(jié)點都僅包含一個大寫英文字母；2．從根結(jié)點到某一結(jié)點，路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列，稱為該結(jié)點對應的單詞。 [樣例輸入] AANASPASASCASCIIBASBASIC [樣例輸出] 13 圖3[算法分析]首先要對建樹的過程有一個了解。當然應該盡可能地存放較短的單詞。39。它有如下5種基本形態(tài)：圖4第一節(jié)講述的樹的一些術(shù)語、概念也基本適用于二叉樹，但二叉樹與樹也有很多不同，如：二叉樹的每個結(jié)點至多只能有兩個結(jié)點，二叉樹一定是有序的，二叉樹可以為空（但樹不能為空，至少要有1個結(jié)點）。圖7和圖8所示的兩棵二叉樹就不是完全二叉樹，請讀者思考為什么？ 圖7 圖8性質(zhì)3：對任何一棵二叉樹，如果其葉結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則一定滿足：n0=n2+1。二叉樹在處理表達式時經(jīng)常用到，一般用葉結(jié)點表示運算數(shù)，分支結(jié)點表示運算符。當然也可以用雙鏈表結(jié)構(gòu)或帶父結(jié)點信息的數(shù)組存儲結(jié)構(gòu)來解決，但實際操作稍微麻煩了一點。除了簡單的窮舉法外，還有更好的時間復雜度為O(n)的算法，我們講在后面的章節(jié)中繼續(xù)討論。遍歷方法共有3種：先序（根）遍歷，中序（根）遍歷， 圖13后序（根）遍歷。在n很小時，很容易得出，B0=1，B1=1，B2=2，B3=5（見圖15）。所以結(jié)點root正好把中序遍歷結(jié)果分成了兩部分，root之前的應該是左子