【正文】 個指針指向該結(jié)點(diǎn)的下一個兄弟結(jié)點(diǎn)?？朔松鲜龅?種存儲方法的缺點(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)解決問題時，往往需要按照某種次序獲得樹中全部結(jié)點(diǎn)的信息，這種操作叫做“樹的遍歷”。遍歷一般按照從左向右的順序，常用的遍歷方法有：1．先序（根）遍歷：先訪問根結(jié)點(diǎn)，再從左到右按照先序思想遍歷各棵子樹。圖1先序遍歷的結(jié)果為：{1，2，5，6，3，4，7，8，9}；2．后序（根）遍歷：先從左到右遍歷各棵子樹，再訪問根結(jié)點(diǎn)。圖1后序遍歷的結(jié)果為：{5，6，2，3，8，9，7，4，1}；3．層次遍歷：按層次從小到大逐個訪問，同一層次按照從左到右的次序。圖1層次遍歷的結(jié)果為：{1，2，3，4，5，6，7，8，9}；4．葉結(jié)點(diǎn)遍歷：有時我們把所有的數(shù)據(jù)信息都存放在葉結(jié)點(diǎn)中，而其余結(jié)點(diǎn)都是用來表示數(shù)據(jù)之間的某種分支或?qū)哟侮P(guān)系，這種情況就用這種方法。圖1按照這個思想訪問的結(jié)果為：{5，6，3，8，9}；很明顯，先序遍歷和后序遍歷兩種方法的定義是遞歸的，所以在程序?qū)崿F(xiàn)時往往也是采用遞歸的思想，既通常所說的“深度優(yōu)先搜索”。按照先序遍歷思想編寫的遞歸過程如下：Procedure tra1(t,m) {訪問以t為根結(jié)點(diǎn)的含有m棵子樹的過程}BeginIf t Nil Then Begin Write(t^.data,’ ’)； {訪問根結(jié)點(diǎn)} For I:=1 To m Do {前序遍歷各子樹}tra1(t^.child[I],m)；End；End；也可以用堆棧的方法編寫這個程序，留給讀者作為練習(xí)。層次遍歷應(yīng)用也較多，實(shí)際上就是我們所說的“廣度優(yōu)先搜索”。思想如下：若某個結(jié)點(diǎn)被訪問，則該結(jié)點(diǎn)的子結(jié)點(diǎn)應(yīng)被記錄下來，等待被訪問。順序訪問各層次上結(jié)點(diǎn)，直至不再有未訪問過的結(jié)點(diǎn)。為此，引入一個隊(duì)列來存儲等待訪問的子結(jié)點(diǎn)，設(shè)一個隊(duì)首和隊(duì)尾指針分別表示出隊(duì)、進(jìn)隊(duì)的下標(biāo)。程序框架如下：Const n=100；Var head,tail,i:integer； q:array[1..n] of tree； p:tree；Begin tail:=1；head:=1； {初始化} q[tail]:=t；tail:=tail+1； {t進(jìn)隊(duì)} While ( headtail) do Begin {隊(duì)列非空} p:=q[head]；head:=head+1； {取出隊(duì)首結(jié)點(diǎn)} Write(p^.data,‘ ‘)； {訪問某結(jié)點(diǎn)} For i:=1 To m Do {該結(jié)點(diǎn)的所有子結(jié)點(diǎn)按順序進(jìn)隊(duì)} If p^.child[i]Nil Then Begin q[tail]:=p^.child[I]；tail:=tail+1； End； End；End；例1：單詞查找樹[問題描述] 在進(jìn)行文法分析的時候，通常需要檢測一個單詞是否在我們的單詞列表里。為了提高查找和定位的速度，通常都畫出與單詞列表所對應(yīng)的單詞查找樹，其特點(diǎn)如下：1．根結(jié)點(diǎn)不包含字母，除根結(jié)點(diǎn)外每一個結(jié)點(diǎn)都僅包含一個大寫英文字母；2．從根結(jié)點(diǎn)到某一結(jié)點(diǎn)，路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列，稱為該結(jié)點(diǎn)對應(yīng)的單詞。單詞列表中的每個單詞，都是該單詞查找樹某個結(jié)點(diǎn)所對應(yīng)的單詞；3．在滿足上述條件下，該單詞查找樹的結(jié)點(diǎn)數(shù)最少。4．例如圖3左邊的單詞列表就對應(yīng)于右邊的單詞查找樹。注意，對一個確定的單詞列表，請統(tǒng)計(jì)對應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)（包含根結(jié)點(diǎn)）。[問題輸入] ，該文件為一個單詞列表，每一行僅包含一個單詞和一個換行/回車符。每個單詞僅由大寫的英文字母組成，長度不超過63個字母 。文件總長度不超過32K，至少有一行數(shù)據(jù)。[問題輸出] ，該文件中僅包含一個整數(shù)，該整數(shù)為單詞列表對應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)。 [樣例輸入] AANASPASASCASCIIBASBASIC [樣例輸出] 13 圖3[算法分析]首先要對建樹的過程有一個了解。對于當(dāng)前被處理的單詞和當(dāng)前樹：在根結(jié)點(diǎn)的子結(jié)點(diǎn)中找單詞的第一位字母，若存在則進(jìn)而在該結(jié)點(diǎn)的子結(jié)點(diǎn)中尋找第二位……如此下去直到單詞結(jié)束，即不需要在該樹中添加結(jié)點(diǎn)；或單詞的第n位不能被找到，即將單詞的第n位及其后的字母依次加入單詞查找樹中去。但，本問題只是問你結(jié)點(diǎn)總數(shù)，而非建樹方案，且有32K文件，所以應(yīng)該考慮能不能通過不建樹就直接算出結(jié)點(diǎn)數(shù)？為了說明問題的本質(zhì)，我們給出一個定義：一個單詞相對于另一個單詞的差：設(shè)單詞1的長度為L，且與單詞2從第N位開始不一致，則說單詞1相對于單詞2的差為LN+1，這是描述單詞相似程度的量?？梢?，將一個單詞加入單詞樹的時候，須加入的結(jié)點(diǎn)數(shù)等于該單詞樹中已有單詞的差的最小值。單詞的字典順序排列后的序列則具有類似的特性，即在一個字典順序序列中，第m個單詞相對于第m1個單詞的差必定是它對于前m1個單詞的差中最小的。于是，得出建樹的等效算法：① 讀入文件；② 對單詞列表進(jìn)行字典順序排序；③ 依次計(jì)算每個單詞對前一單詞的差，并把差累加起來。注意：第一個單詞相對于“空”的差為該單詞的長度；④ 累加和再加上1（根結(jié)點(diǎn)），輸出結(jié)果。就給定的樣例，按照這個算法求結(jié)點(diǎn)數(shù)的過程如下表：表1原單詞列表排序后的列表差值總計(jì)輸出AA11213ANAN1ASPAS1ASASC1ASCASCII2ASCIIASP1BASBAS3BASICBASIC2[數(shù)據(jù)結(jié)構(gòu)] 先確定32K（32*1024=32768字節(jié)）的文件最多有多少單詞和字母。當(dāng)然應(yīng)該盡可能地存放較短的單詞。因?yàn)閱卧~不重復(fù)，所以長度為1的單詞（單個字母）最多26個；長度為2的單詞最多為26*26=676個；因?yàn)槊總€單詞后都要一個換行符（換行符在計(jì)算機(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ù)量最多為26+676+5997=6699。定義一個數(shù)組：a：array[1..32767] of char；把所有單詞連續(xù)存放起來，文件中每個單詞后的換行符轉(zhuǎn)換成數(shù)組中的一個“空格”字符。這樣既省略了一個存放單詞長度的數(shù)組，又方便且節(jié)省了一點(diǎn)空間。另外為了排序，再設(shè)一個數(shù)組index:array[1.. 6700] of integer；存放每個單詞在a中的起始位置。這樣，排序時用a比較，但只要交換index的值就可以了。[參考程序]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]