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