【正文】 [輸出格式] ，僅一行，表示樹的后序遍歷序列。但，已知一棵二叉樹的先序遍歷結(jié)果和后序遍歷結(jié)果卻不能確定一棵二叉樹，為什么？你可以舉出反例嗎？例如已知一棵二叉樹的先序遍歷結(jié)果為ABCDEFG，中序遍歷結(jié)果為CBEDAFG。再結(jié)合中序遍歷，因?yàn)橹行虮闅v是先遍歷左子樹，再訪問根，最后遍歷右子樹。即具有n個(gè)結(jié)點(diǎn)的不同形態(tài)的樹有Cn12n2 /n棵。二叉樹的計(jì)數(shù)問題就是討論具有n個(gè)結(jié)點(diǎn)、互不相似的二叉樹的數(shù)目Bn。={1，2，3，4，5，6，7，8，9} {所有結(jié)點(diǎn)}={1，{2，4，5，7}，{3，6，8，9}} {按先序思想遍歷，將根結(jié)點(diǎn)單獨(dú)列出，左右子樹分別用括號(hào)括起來}={1，{2，{4，7}，{5}}，{3，{}，{6，8，9}}} {再對(duì)以3結(jié)點(diǎn)為根的樹先序遍歷}={1，{2，{4，{7}，{}，5}，{3，{}，6，{8}，{9}}} {再對(duì)以6結(jié)點(diǎn)為根的樹先序遍歷，遇到無左、右子樹的情況就用一對(duì)空括號(hào)，遇到葉子結(jié)點(diǎn)就脫到本層括號(hào)，遇到空括號(hào)就省略}={1，2，4，7，5，3，6，8，9} {去掉內(nèi)層所有括號(hào)，得到結(jié)果}2．中序遍歷的操作定義如下：若二叉樹為空，則空操作，否則① 中序遍歷左子樹② 訪問根結(jié)點(diǎn)③ 中序遍歷右子樹可以根據(jù)以上方法，得出上圖中序遍歷的結(jié)果為：{7，4，2，5，1，3，8，6，9}3．后序遍歷的操作定義如下：若二叉樹為空，則空操作，否則① 后序遍歷左子樹② 后序遍歷右子樹③ 訪問根結(jié)點(diǎn)可以根據(jù)以上方法，得出上圖后序遍歷的結(jié)果為：{7，4，5，2，8，9，6，3，1}顯然，以上3種遍歷方法都是采用遞歸的思想，下面以先序遍歷為例給出遞歸算法：Procedure preorder(bt:tree)；{先序遍歷根結(jié)點(diǎn)為bt的二叉樹的遞歸算法}Begin If btNil Then BeginWrite(bt^.data)；preorder(bt^.lchild)；preorder(bt^.rchild)； End；End；我們也可以把遞歸過程改成用棧實(shí)現(xiàn)的非遞歸過程，下面給出先序遍歷的非遞歸過程?！霸L問”的含義很廣，可以是對(duì)結(jié)點(diǎn)作各種處理，如輸出結(jié)點(diǎn)的信息等。第一節(jié)中的圖1所示的普通樹轉(zhuǎn)換成二叉樹的過程如圖12所示：圖12同樣我們可以把森林也轉(zhuǎn)換成二叉樹處理，假設(shè)F={T1，T2，…，Tm}是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B=(root,lb,rb)。X公司（或者是政府）決定在某一個(gè)城市建立一個(gè)醫(yī)院/酒廠/游樂場……，問：將它建在哪里，可以使得所有的居民移動(dòng)到那里的總耗費(fèi)最小？這種題目都是本題的“變型”，一般稱為“樹的中心點(diǎn)問題”。)； Reset(Input)；Assign(Output, 39。 [樣例輸入]513 2 34 0 012 4 520 0 040 0 0[樣例輸出]81[問題分析] 這是一道簡單的二叉樹應(yīng)用問題，問題中的結(jié)點(diǎn)數(shù)并不多，數(shù)據(jù)規(guī)模也不大，采用鄰接矩陣存儲(chǔ)，用Floyed法求出任意兩結(jié)點(diǎn)之間的最短路徑長，然后窮舉醫(yī)院可能建立的n個(gè)結(jié)點(diǎn)位置，找出一個(gè)最小距離的位置即可。現(xiàn)在要求在某個(gè)結(jié)點(diǎn)上建立一個(gè)醫(yī)院，使所有居民所走的路程之和為最小，同時(shí)約定，相鄰接點(diǎn)之間的距離為1。其實(shí)如果樹的結(jié)點(diǎn)較少，也可采用鄰接矩陣的方法，這樣操作起來也很方便。3．如果2*i+1n，則結(jié)點(diǎn)i無右孩子；否則右孩子編號(hào)為2*i+1。圖6完全二叉樹具有如下特征：葉結(jié)點(diǎn)只可能出現(xiàn)在最下面兩層上；對(duì)任一結(jié)點(diǎn)，若其右子樹深度為m，則其左子樹的深度必為m或m+1。特別地，一棵深度為k且有2k –1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。； j := index[i]； {第i個(gè)單詞的首字母在a數(shù)組中的下標(biāo)為j} While (Ord(a[j])0) Do {換行符換成了空格} Begin now := now + a[j]；j := j+1；End； {當(dāng)前處理的單詞存入now中} j := 1； While ((pre[j]=now[j]) And (j=length(pre))) Do Inc(j)；{求兩個(gè)單詞的差} tot := tot+(Length(now)j+1)； {累加} pre := now；{把當(dāng)前單詞作為下次比較的前一個(gè)單詞} End； Writeln(tot+1)； Close(Input)；Close(Output)；End.第二節(jié) 二叉樹一、二叉樹的概念二叉樹（binary tree,簡寫成BT）是一種特殊的樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹，即二叉樹中不存在度大于2的結(jié)點(diǎn)，而且二叉樹的子樹有左子樹、右子樹之分，孩子有左孩子、右孩子之分，其次序不能顛倒，所以二叉樹是一棵有序樹。)；Rewrite(Output)； Fillchar(a, sizeof(a), 0)； n := 0；{單詞個(gè)數(shù)} k := 0；{下標(biāo)} While (Not Eof) Do {讀入文件中的單詞并且存儲(chǔ)到數(shù)組中} Begin Readln(s)； n := n+1； index[n] := k+1；{第n個(gè)單詞的首字母起點(diǎn)下標(biāo)} For i:=1 To Length(s) Do {存入一個(gè)單詞} a[k+i] := s[i]； k := k+i+1； {為下個(gè)單詞的下標(biāo)設(shè)定好初值,i即為當(dāng)前單詞的長度} End； For i:=1 To n Do {n個(gè)單詞的字典排序} 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； {計(jì)數(shù)器} pre := 39。[參考程序]Program p1(Input, Output)；Var a:Array[1..32767] Of Char； index:Array[1..6700] Of Integer； n,k,i,j,tot,t:Integer； s,pre,now:String；Function cmp(i, j:Longint):Boolean；{比較從a[i]開始的字符串和從a[j]開始的字符串Begin 大小，小于則返回False，否則返回True} While ((a[i]=a[j]) And (Ord(a[i])32) And (Ord(a[j])32)) Do Begin Inc(i)；Inc(j)；End； If (a[i]a[j]) Then cmp := False Else cmp := True；End；Begin {main} Assign(Input,39。定義一個(gè)數(shù)組：a：array[1..32767] of char；把所有單詞連續(xù)存放起來，文件中每個(gè)單詞后的換行符轉(zhuǎn)換成數(shù)組中的一個(gè)“空格”字符。就給定的樣例，按照這個(gè)算法求結(jié)點(diǎn)數(shù)的過程如下表：表1原單詞列表排序后的列表差值總計(jì)輸出AA11213ANAN1ASPAS1ASASC1ASCASCII2ASCIIASP1BASBAS3BASICBASIC2[數(shù)據(jù)結(jié)構(gòu)] 先確定32K（32*1024=32768字節(jié)）的文件最多有多少單詞和字母?？梢?，將一個(gè)單詞加入單詞樹的時(shí)候，須加入的結(jié)點(diǎn)數(shù)等于該單詞樹中已有單詞的差的最小值。[問題輸出] ，該文件中僅包含一個(gè)整數(shù)，該整數(shù)為