【正文】 中序遍歷的結(jié)果為：{7，4，2，5，1，3，8，6，9}3．后序遍歷的操作定義如下：若二叉樹為空，則空操作，否則① 后序遍歷左子樹② 后序遍歷右子樹③ 訪問根結(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é)果和后序遍歷結(jié)果卻不能確定一棵二叉樹，為什么？你可以舉出反例嗎？例如已知一棵二叉樹的先序遍歷結(jié)果為ABCDEFG，中序遍歷結(jié)果為CBEDAFG。再結(jié)合中序遍歷，因為中序遍歷是先遍歷左子樹，再訪問根，最后遍歷右子樹。“訪問”的含義很廣，可以是對結(jié)點作各種處理，如輸出結(jié)點的信息等。 [樣例輸入]513 2 34 0 012 4 520 0 040 0 0[樣例輸出]81[問題分析] 這是一道簡單的二叉樹應(yīng)用問題，問題中的結(jié)點數(shù)并不多，數(shù)據(jù)規(guī)模也不大，采用鄰接矩陣存儲，用Floyed法求出任意兩結(jié)點之間的最短路徑長，然后窮舉醫(yī)院可能建立的n個結(jié)點位置，找出一個最小距離的位置即可。圖6完全二叉樹具有如下特征：葉結(jié)點只可能出現(xiàn)在最下面兩層上；對任一結(jié)點，若其右子樹深度為m，則其左子樹的深度必為m或m+1。[參考程序]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。[問題輸出] ，該文件中僅包含一個整數(shù)，該整數(shù)為單詞列表對應(yīng)的單詞查找樹的結(jié)點數(shù)。圖1后序遍歷的結(jié)果為：{5，6，2，3，8，9，7，4，1}；3．層次遍歷：按層次從小到大逐個訪問，同一層次按照從左到右的次序。三、樹的表示方法和存儲結(jié)構(gòu)樹的表示方法有多種，如圖1采用的就是一種形象的樹形表示法；另外還有一種常用的表示方法“括號表示法”，它的表示方法歸納如下：先將整棵樹的根結(jié)點放入一對圓括號中，然后把它的子樹由左至右放入括號中，同層子樹用圓括號括在一起（同層子樹之間用逗號隔開），而對子樹也采用同樣的方法處理，直到所有的子樹都只有一個根結(jié)點為止。如結(jié)點9都是結(jié)點4的子孫。樹型結(jié)構(gòu)在現(xiàn)實世界中廣泛存在，如把一個家族看作為一棵樹，樹中的結(jié)點為家族成員的姓名及相關(guān)信息，樹中的關(guān)系為父子關(guān)系，即父親是兒子的前驅(qū)，兒子是父親的后繼；把一個國家或一個地區(qū)的各級行政區(qū)劃分看作為一棵樹，樹中的結(jié)點為行政區(qū)的名稱及相關(guān)信息，樹中的關(guān)系為上下級關(guān)系，如一個城市包含有若干個區(qū)，每個區(qū)又包含有若干個街道，每個街道又包含有若干個居委會；把一本書的結(jié)構(gòu)看作是一棵樹，樹中的結(jié)點為書、章、節(jié)的名稱及相關(guān)信息，樹中的關(guān)系為包含關(guān)系。稱從根結(jié)點到某個子結(jié)點所經(jīng)過的所有結(jié)點為這個子結(jié)點的祖先。注意，不同子樹上的結(jié)點之間不存在路徑?？朔松鲜龅?種存儲方法的缺點，假設(shè)樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：Type tree=^node； node=Record data:Char； firstchild,next: tree； End；Var t:tree；四、樹的遍歷在應(yīng)用樹結(jié)構(gòu)解決問題時，往往需要按照某種次序獲得樹中全部結(jié)點的信息，這種操作叫做“樹的遍歷”。[問題輸入] ，該文件為一個單詞列表，每一行僅包含一個單詞和一個換行/回車符。這樣既省略了一個存放單詞長度的數(shù)組，又方便且節(jié)省了一點空間。圖5是深度為4的滿二叉樹，這種樹的特點是每層上的結(jié)點數(shù)都達到了最大值。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和=4*2+13+20+40=81……[輸入格式] ，其中第一行一個整數(shù)n，表示樹的結(jié)點數(shù)（n=100）。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)換而成的二叉樹。八、由遍歷結(jié)果確定二叉樹的形態(tài)問題下面我們換個角度考慮這個問題，從二叉樹的遍歷已經(jīng)知道，任意一棵二叉樹的先序遍歷結(jié)果和中序遍歷結(jié)果都是唯一的。樹的結(jié)點一律用小寫字母表示?！暗葍r二叉樹”是指兩者不僅相似，而且所有對應(yīng)結(jié)點上的數(shù)據(jù)元素均相同。每個城市里面都有一定數(shù)量的居民，但是數(shù)量并不一定相等，每條公路的長度也不一定相等。 bt圖92．順序存儲結(jié)構(gòu):即幾個數(shù)組加一個指針變量，一般用在滿二叉樹和完全二叉樹中，將每個結(jié)點編號后作為數(shù)組的下標變量值，基本數(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ù)組，操作也教麻煩。39。注意：第一個單詞相對于“空”的差為該單詞的長度；④ 累加和再加上1（根結(jié)點），輸出結(jié)果。為此，引入一個隊列來存儲等待訪問的子結(jié)點，設(shè)一個隊首和隊尾指針分別表示出隊、進隊的下標。當樹的度越大時，空指針域所占比例也越大，給存儲空間造成很大浪費。又如對于一棵反映了父子關(guān)系的家族樹，兄弟結(jié)點之間是按照排行大小而有序排列的，所以它是一棵有序樹。度為0的結(jié)點稱為葉結(jié)點（又稱樹葉leaf，如結(jié)點9）。從樹的定義可以看出：1．樹是遞歸定義的，這就決定了樹的操作和應(yīng)用大都是采用遞歸思想來解決； 2．一棵樹中至少有1個結(jié)點，這個結(jié)點就是根結(jié)點，如上圖中的結(jié)點1；3．只有根結(jié)點沒有前趨結(jié)點，其余每個結(jié)點都有唯一的一個前趨結(jié)點；4．所有結(jié)點都可以有0或多個后繼結(jié)點；二、樹的基本概念下面以圖1為例給出樹結(jié)構(gòu)中的一些基本概念：1．一個結(jié)點的子樹個數(shù)，稱為這個結(jié)點的度（degree），如結(jié)點1的度為3，結(jié)點3的度為0。例如，對于下面圖2中的兩棵樹，若看作為無序樹，則是相同的；若看作為有序樹，則是不同的，因為根結(jié)點A的兩棵子樹的次序不同。由于一般樹的各個結(jié)點的孩子數(shù)不確定，所以指針數(shù)應(yīng)該等于整棵樹的度。順序訪問各層次上結(jié)點，直至不再有未訪問過的結(jié)點。于是，得出建樹的等效算法：① 讀入文件；② 對單詞列表進行字典順序排序；③ 依次計算每個單詞對前一單詞的差，并把差累加起來。