【正文】 字母組成，長度不超過63個字母 。順序訪問各層次上結(jié)點，直至不再有未訪問過的結(jié)點。遍歷一般按照從左向右的順序，常用的遍歷方法有：1．先序（根）遍歷：先訪問根結(jié)點，再從左到右按照先序思想遍歷各棵子樹。由于一般樹的各個結(jié)點的孩子數(shù)不確定，所以指針數(shù)應(yīng)該等于整棵樹的度。但是，如果把樹看成是一個圖的話(可以把樹理解為是圖的一個子類)，那么我們就可以繼承圖的路徑的定義，認(rèn)為不同子樹上的兩個結(jié)點應(yīng)該是有路徑的（圖論意義上的路徑）。例如，對于下面圖2中的兩棵樹，若看作為無序樹，則是相同的；若看作為有序樹，則是不同的，因為根結(jié)點A的兩棵子樹的次序不同。如結(jié)點7是結(jié)點8的祖先。從樹的定義可以看出：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。20Jsoi2006春季函授 B層次講義（3） 常州市第一中學(xué) 林厚從 20樹和二叉樹的基本知識樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，用它能很好地描述有分支和層次特性的數(shù)據(jù)集合。度為0的結(jié)點稱為葉結(jié)點（又稱樹葉leaf，如結(jié)點9）。稱以某個結(jié)點為根的子樹中的任一結(jié)點都是該結(jié)點的子孫。又如對于一棵反映了父子關(guān)系的家族樹，兄弟結(jié)點之間是按照排行大小而有序排列的，所以它是一棵有序樹。6．森林（forest）是m(m=0)棵互不相交的樹的集合。當(dāng)樹的度越大時，空指針域所占比例也越大，給存儲空間造成很大浪費。圖1先序遍歷的結(jié)果為：{1，2，5，6，3，4，7，8，9}；2．后序（根）遍歷：先從左到右遍歷各棵子樹，再訪問根結(jié)點。為此，引入一個隊列來存儲等待訪問的子結(jié)點，設(shè)一個隊首和隊尾指針分別表示出隊、進(jìn)隊的下標(biāo)。文件總長度不超過32K，至少有一行數(shù)據(jù)。注意：第一個單詞相對于“空”的差為該單詞的長度；④ 累加和再加上1（根結(jié)點），輸出結(jié)果。這樣，排序時用a比較，但只要交換index的值就可以了。39。 如圖6就是一個深度為4，結(jié)點數(shù)為12的完全二叉樹。 bt圖92．順序存儲結(jié)構(gòu):即幾個數(shù)組加一個指針變量，一般用在滿二叉樹和完全二叉樹中，將每個結(jié)點編號后作為數(shù)組的下標(biāo)變量值，基本數(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ù)組，操作也教麻煩。[輸出格式] ，該文件只有一個整數(shù)，表示最小距離和。每個城市里面都有一定數(shù)量的居民，但是數(shù)量并不一定相等，每條公路的長度也不一定相等。所謂二叉樹的遍歷是指按一定的規(guī)律和次序訪問樹中的各個結(jié)點，而且每個結(jié)點僅被訪問一次?！暗葍r二叉樹”是指兩者不僅相似，而且所有對應(yīng)結(jié)點上的數(shù)據(jù)元素均相同。即在二叉樹的先序遍歷結(jié)果中，第一個結(jié)點必是根，假設(shè)為root。樹的結(jié)點一律用小寫字母表示。構(gòu)造出這棵二叉樹的步驟如圖16：圖16例3: 二叉樹的遍歷問題[問題描述] 輸入一棵二叉樹的先序和中序遍歷序列，輸出其后序遍歷序列。八、由遍歷結(jié)果確定二叉樹的形態(tài)問題下面我們換個角度考慮這個問題，從二叉樹的遍歷已經(jīng)知道，任意一棵二叉樹的先序遍歷結(jié)果和中序遍歷結(jié)果都是唯一的。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 {非葉結(jié)點}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；關(guān)于前面講的表達(dá)式樹，我們可以分別用先序、中序、后序的遍歷方法得出完全不同的遍歷結(jié)果，對于圖14采用三種遍歷后的結(jié)果如下，它們正好對應(yīng)著表達(dá)式的三種表示方法： +a*bcd/ef (前綴表示、波蘭式)a+b*cde/f (中綴表示、代數(shù)式)abcd*+ef/ (后綴表示、逆波蘭式) 圖14六、二叉樹的其它重要操作：除了“遍歷”以外，二叉樹的其它重要操作還有：建立一棵二叉樹、插入一個結(jié)點到二叉樹中、刪除結(jié)點或子樹等，下面分別給出基本算法框架。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)換而成的二叉樹。39。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和=4*2+13+20+40=81……[輸入格式] ，其中第一行一個整數(shù)n，表示樹的結(jié)點數(shù)（n=100）。三、 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)與普通樹的存儲結(jié)構(gòu)基本相同，有鏈?zhǔn)胶晚樞虼鎯煞N方法。圖5是深度為4的滿二叉樹，這種樹的特點是每層上的結(jié)點數(shù)都達(dá)到了最大值。39。這樣既省略了一個存放單詞長度的數(shù)組，又方便且節(jié)省了一點空間。單詞的字典順序排列后的序列則具有類似的特性，即在一個字典順序序列中，第m個單詞相對于第m1個單詞的差必定是它對于前m1個單詞的差中最小的。[問題輸入] ，該文件為一個單詞列表，每一行僅包含一個單詞和一個換行/回車符。思想如下：若某個結(jié)點被訪問，則該結(jié)點的子結(jié)點應(yīng)被記錄下來，等待被訪問?？朔松鲜龅?種存儲方法的缺點，假設(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é)點的信息，這種操作叫做“樹的遍歷”。2．孩子表示法：利用單鏈表，每個結(jié)點包括一個數(shù)據(jù)域和若干個指針域，每個指針都指向一個孩子結(jié)點。注意，不同子樹上的結(jié)點之間不存在路徑。所以，樹雖然是非線性結(jié)構(gòu)，但也是有序結(jié)構(gòu)。稱從根結(jié)點到某個子結(jié)點所經(jīng)過的所有結(jié)點為這個子結(jié)點的祖先。圖1圖1就是一棵典型的樹結(jié)構(gòu)。樹型結(jié)構(gòu)在現(xiàn)實世界中廣泛存在，如把一個家族看作為一棵樹，樹中的結(jié)點為家族成員的姓名及相關(guān)信息，樹中的關(guān)系為父子關(guān)系，即父親是兒子的前驅(qū)，兒子是父親的后繼；把一個國家或一個地區(qū)的各級行政區(qū)劃分看作為一棵樹，樹中的結(jié)點為行政區(qū)的名稱及相關(guān)信息，樹中的關(guān)系為上下級關(guān)系，如一個