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