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