【正文】 單詞1的長度為L，且與單詞2從第N位開始不一致，則說單詞1相對于單詞2的差為LN+1，這是描述單詞相似程度的量。文件總長度不超過32K，至少有一行數(shù)據(jù)。4．例如圖3左邊的單詞列表就對應(yīng)于右邊的單詞查找樹。為此，引入一個隊列來存儲等待訪問的子結(jié)點，設(shè)一個隊首和隊尾指針分別表示出隊、進(jìn)隊的下標(biāo)。按照先序遍歷思想編寫的遞歸過程如下：Procedure tra1(t,m) {訪問以t為根結(jié)點的含有m棵子樹的過程}BeginIf t Nil Then Begin Write(t^.data,’ ’)； {訪問根結(jié)點} For I:=1 To m Do {前序遍歷各子樹}tra1(t^.child[I],m)；End；End；也可以用堆棧的方法編寫這個程序，留給讀者作為練習(xí)。圖1先序遍歷的結(jié)果為：{1，2，5，6，3，4，7，8，9}；2．后序（根）遍歷：先從左到右遍歷各棵子樹，再訪問根結(jié)點。3．父親孩子表示法：利用雙鏈表結(jié)構(gòu)，每個結(jié)點包括一個數(shù)據(jù)域和二個指針域，一個指向該結(jié)點的若干孩子結(jié)點，一個指向其父結(jié)點。當(dāng)樹的度越大時，空指針域所占比例也越大，給存儲空間造成很大浪費。1．父親表示法：定義一個數(shù)組，每個數(shù)組元素為一個記錄，除了存放一個結(jié)點的數(shù)據(jù)信息外，還存放該結(jié)點的父結(jié)點編號。6．森林（forest）是m(m=0)棵互不相交的樹的集合。如圖1中，結(jié)點1和結(jié)點8之間存在著一條路徑，并可用（8）表示這條路徑，該條路徑的長度為3。又如對于一棵反映了父子關(guān)系的家族樹，兄弟結(jié)點之間是按照排行大小而有序排列的，所以它是一棵有序樹。一棵樹中所有結(jié)點的層次的最大值稱為樹的深度（depth），圖1所示這棵樹的深度為4。稱以某個結(jié)點為根的子樹中的任一結(jié)點都是該結(jié)點的子孫。2．在用上述圖形表示的樹結(jié)構(gòu)中，對兩個用線段（稱為樹枝）連接的相關(guān)聯(lián)的結(jié)點，稱上端的結(jié)點為下端結(jié)點的父結(jié)點，稱下端的結(jié)點為上端結(jié)點的子結(jié)點，稱同一個父結(jié)點的多個子結(jié)點為兄弟結(jié)點。度為0的結(jié)點稱為葉結(jié)點（又稱樹葉leaf，如結(jié)點9）。在樹型結(jié)構(gòu)中，二叉樹是最常用的結(jié)構(gòu)，它的分支個數(shù)確定，又可以為空，具有良好的遞歸特性，特別適宜于程序設(shè)計，因此我們常常將一般樹型結(jié)構(gòu)轉(zhuǎn)換成二叉樹進(jìn)行處理。20Jsoi2006春季函授 B層次講義（3） 常州市第一中學(xué) 林厚從 20樹和二叉樹的基本知識樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，用它能很好地描述有分支和層次特性的數(shù)據(jù)集合。在許多算法中，常用樹型結(jié)構(gòu)描述問題的求解過程、所有解的狀態(tài)和求解的對策等。從樹的定義可以看出：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。樹中各結(jié)點的度的最大值稱為這棵樹的度（又稱寬度），圖1所示這棵樹的（寬）度為3。如結(jié)點7是結(jié)點8的祖先。如結(jié)點4的層次為2，結(jié)點7的層次為3，結(jié)點9的層次為4。例如，對于下面圖2中的兩棵樹，若看作為無序樹，則是相同的；若看作為有序樹，則是不同的，因為根結(jié)點A的兩棵子樹的次序不同?？捎寐窂剿?jīng)過的結(jié)點序列表示路徑，路徑的長度等于路徑上的結(jié)點個數(shù)減1。但是，如果把樹看成是一個圖的話(可以把樹理解為是圖的一個子類)，那么我們就可以繼承圖的路徑的定義，認(rèn)為不同子樹上的兩個結(jié)點應(yīng)該是有路徑的（圖論意義上的路徑）。樹的存儲結(jié)構(gòu)也有多種形式，其中使用較多的采是鏈?zhǔn)酱鎯Y(jié)構(gòu)，下面給出幾種常見的存儲樹的數(shù)據(jù)結(jié)構(gòu)。由于一般樹的各個結(jié)點的孩子數(shù)不確定，所以指針數(shù)應(yīng)該等于整棵樹的度。由于每個結(jié)點都只存放各自孩子結(jié)點的編號，所以這種方法只能從根（父）結(jié)點遍歷到子結(jié)點，不能從某個子結(jié)點返回到它的父結(jié)點。遍歷一般按照從左向右的順序，常用的遍歷方法有：1．先序（根）遍歷：先訪問根結(jié)點，再從左到右按照先序思想遍歷各棵子樹。圖1按照這個思想訪問的結(jié)果為：{5，6，3，8，9}；很明顯，先序遍歷和后序遍歷兩種方法的定義是遞歸的，所以在程序?qū)崿F(xiàn)時往往也是采用遞歸的思想，既通常所說的“深度優(yōu)先搜索”。順序訪問各層次上結(jié)點，直至不再有未訪問過的結(jié)點。單詞列表中的每個單詞，都是該單詞查找樹某個結(jié)點所對應(yīng)的單詞；3．在滿足上述條件下，該單詞查找樹的結(jié)點數(shù)最少。每個單詞僅由大寫的英文字母組成，長度不超過63個字母 。對于當(dāng)前被處理的單詞和當(dāng)前樹：在根結(jié)點的子結(jié)點中找單詞的第一位字母，若存在則進(jìn)而在該結(jié)點的子結(jié)點中尋找第二位……如此下去直到單詞結(jié)束，即不需要在該樹中添加結(jié)點；或單詞的第n位不能被找到，即將單詞的第n位及其后的字母依次加入單詞查找樹中去。于是，得出建樹的等效算法：① 讀入文件；② 對單詞列表進(jìn)行字典順序排序；③ 依次計算每個單詞對前一單詞的差，并把差累加起來。因為單詞不重復(fù)，所以長度為1的單詞（單個字母）最多26個；長度為2的單詞最多為26*26=676個；因為每個單詞后都要一個換行符（換行符在計算機(jī)中占2個字節(jié)），所以總共已經(jīng)占用的空間為：（1+2）*26+（2+2）*676=2782字節(jié)；剩余字節(jié)（327682782=29986字節(jié)）分配給長度為3的單詞（長度為3的單詞最多有 26*26*26=17576個）有29986/（3+2）≈5997。另外為了排序，再設(shè)一個數(shù)組index:array[1.. 6700] of integer；存放每個單詞在a中的起始位置。)； Reset(Input)； Assign(Output,39。； {前一個單詞} For i:=1 To n Do {統(tǒng)計} Begin now := 39。二、二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i1個結(jié)點（i=1）。圖5可以對滿二叉樹的結(jié)點進(jìn)行連續(xù)編號，約定編號從根結(jié)點起，自上而下，從左到右，由此引出完全二叉樹的定義：深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為trunc(LOG2n)+1 （trunc為取整函數(shù)）性質(zhì)5：一棵n個結(jié)點的完全二叉樹，對于任一編號為i結(jié)點，有：1．如果i=1,則結(jié)點i為根，無父結(jié)點；如果i1,則其父結(jié)點編號為trunc(i/2)。1．鏈?zhǔn)酱鎯Y(jié)構(gòu):單鏈表結(jié)構(gòu)或雙鏈表結(jié)構(gòu)，基本數(shù)據(jù)結(jié)構(gòu)定義如下：Type tree=^node； {單鏈表結(jié)構(gòu)} node=Record data:Char； {數(shù)據(jù)域} lchild,rchild:tree {指針域：分別指向左、右孩子} End；Var bt:tree；Type tree=^node； {雙鏈表結(jié)構(gòu)} node=Record data:Char； {數(shù)據(jù)域} lchild,rchild,father:tree {指針域：分別指向左、右孩子及父結(jié)點} End；Var bt:tree；如圖9左邊所示的一棵二叉樹用單鏈表就可以表示成右邊的形式。這樣的二叉樹稱為表達(dá)式樹，如表達(dá)式（a+b/c）*(de)就可以表示成圖10。接下來的n行每行描述了一個結(jié)點的狀況，包含三個整數(shù)，整數(shù)之間用空格（一個或多個）分隔，其中：第一個數(shù)為居民人口數(shù)；第二個數(shù)為左鏈接，為0表示無鏈接；第三個數(shù)為右鏈接。[參考程序]Program p2(Input, Output)；Var a : Array [1..100] Of Longint； g : Array [1..100, 1..100] Of Longint； n, i, j, k,