【正文】 它的表示方法歸納如下：先將整棵樹(shù)的根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)由左至右放入括號(hào)中，同層子樹(shù)用圓括號(hào)括在一起（同層子樹(shù)之間用逗號(hào)隔開(kāi)），而對(duì)子樹(shù)也采用同樣的方法處理，直到所有的子樹(shù)都只有一個(gè)根結(jié)點(diǎn)為止。樹(shù)的存儲(chǔ)結(jié)構(gòu)也有多種形式，其中使用較多的采是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，下面給出幾種常見(jiàn)的存儲(chǔ)樹(shù)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10； {樹(shù)的結(jié)點(diǎn)數(shù)}Type node=Record data:Integer； {數(shù)據(jù)域} parent:Integer； {指針域} End；Var tree:Array[1..m] Of node；這種方法充分利用了樹(shù)中除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)都有唯一的父結(jié)點(diǎn)這個(gè)性質(zhì)，很容易找到樹(shù)根（可以規(guī)定根結(jié)點(diǎn)的父結(jié)點(diǎn)為0），但找孩子時(shí)卻需要遍歷整個(gè)線性表。由于一般樹(shù)的各個(gè)結(jié)點(diǎn)的孩子數(shù)不確定，所以指針數(shù)應(yīng)該等于整棵樹(shù)的度。假設(shè)樹(shù)的度為10，樹(shù)的結(jié)點(diǎn)僅存放字符，則這棵樹(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10； {樹(shù)的度}Type tree=^node； node=Record data:Char； {數(shù)據(jù)域} child:Array[1..m] Of tree {指針域，指向若干孩子結(jié)點(diǎn)} End；Var t:tree；注：空間上的浪費(fèi)其實(shí)可以用“虛開(kāi)實(shí)用”的方法完美地解決，在FreePascal等環(huán)境下可以用Getmem、Freemem等過(guò)程達(dá)到這個(gè)目的，這樣建立一棵普通樹(shù)的時(shí)間復(fù)雜度也是很不錯(cuò)的。由于每個(gè)結(jié)點(diǎn)都只存放各自孩子結(jié)點(diǎn)的編號(hào)，所以這種方法只能從根（父）結(jié)點(diǎn)遍歷到子結(jié)點(diǎn)，不能從某個(gè)子結(jié)點(diǎn)返回到它的父結(jié)點(diǎn)?？朔松鲜龅?種存儲(chǔ)方法的缺點(diǎn)，假設(shè)樹(shù)的度為10，樹(shù)的結(jié)點(diǎn)僅存放字符，則這棵樹(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10；Type tree=^node； node=Record data:Char； child:Array[1..m] Of tree； father:treeEnd；Var t:tree；4．孩子兄弟表示法：有些程序中需要對(duì)兄弟結(jié)點(diǎn)進(jìn)行處理，這種情況下，可以使用另外一種雙鏈表結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和二個(gè)指針域，一個(gè)指針指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)，一個(gè)指針指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。遍歷一般按照從左向右的順序，常用的遍歷方法有：1．先序（根）遍歷：先訪問(wèn)根結(jié)點(diǎn)，再?gòu)淖蟮接野凑障刃蛩枷氡闅v各棵子樹(shù)。圖1后序遍歷的結(jié)果為：{5，6，2，3，8，9，7，4，1}；3．層次遍歷：按層次從小到大逐個(gè)訪問(wèn)，同一層次按照從左到右的次序。圖1按照這個(gè)思想訪問(wèn)的結(jié)果為：{5，6，3，8，9}；很明顯，先序遍歷和后序遍歷兩種方法的定義是遞歸的，所以在程序?qū)崿F(xiàn)時(shí)往往也是采用遞歸的思想，既通常所說(shuō)的“深度優(yōu)先搜索”。層次遍歷應(yīng)用也較多，實(shí)際上就是我們所說(shuō)的“廣度優(yōu)先搜索”。順序訪問(wèn)各層次上結(jié)點(diǎn)，直至不再有未訪問(wèn)過(guò)的結(jié)點(diǎn)。程序框架如下：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è)單詞是否在我們的單詞列表里。單詞列表中的每個(gè)單詞，都是該單詞查找樹(shù)某個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的單詞；3．在滿足上述條件下，該單詞查找樹(shù)的結(jié)點(diǎn)數(shù)最少。注意，對(duì)一個(gè)確定的單詞列表，請(qǐng)統(tǒng)計(jì)對(duì)應(yīng)的單詞查找樹(shù)的結(jié)點(diǎn)數(shù)（包含根結(jié)點(diǎn)）。每個(gè)單詞僅由大寫(xiě)的英文字母組成，長(zhǎng)度不超過(guò)63個(gè)字母 。[問(wèn)題輸出] ，該文件中僅包含一個(gè)整數(shù)，該整數(shù)為單詞列表對(duì)應(yīng)的單詞查找樹(shù)的結(jié)點(diǎn)數(shù)。對(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ù)中去。可見(jiàn)，將一個(gè)單詞加入單詞樹(shù)的時(shí)候，須加入的結(jié)點(diǎn)數(shù)等于該單詞樹(shù)中已有單詞的差的最小值。于是，得出建樹(shù)的等效算法：① 讀入文件；② 對(duì)單詞列表進(jìn)行字典順序排序；③ 依次計(jì)算每個(gè)單詞對(duì)前一單詞的差，并把差累加起來(lái)。就給定的樣例，按照這個(gè)算法求結(jié)點(diǎn)數(shù)的過(guò)程如下表：表1原單詞列表排序后的列表差值總計(jì)輸出AA11213ANAN1ASPAS1ASASC1ASCASCII2ASCIIASP1BASBAS3BASICBASIC2[數(shù)據(jù)結(jié)構(gòu)] 先確定32K（32*1024=32768字節(jié)）的文件最多有多少單詞和字母。因?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。定義一個(gè)數(shù)組：a：array[1..32767] of char；把所有單詞連續(xù)存放起來(lái)，文件中每個(gè)單詞后的換行符轉(zhuǎn)換成數(shù)組中的一個(gè)“空格”字符。另外為了排序，再設(shè)一個(gè)數(shù)組index:array[1.. 6700] of integer；存放每個(gè)單詞在a中的起始位置。[參考程序]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]=a[j]) And (Ord(a[i])32) And (Ord(a[j])32)) Do Begin Inc(i)；Inc(j)；End； If (a[i]a[j]) Then cmp := False Else cmp := True；End；Begin {main} Assign(Input,39。)； Reset(Input)； Assign(Output,39。)；Rewrite(Output)； Fillchar(a, sizeof(a), 0)； n := 0；{單詞個(gè)數(shù)} k := 0；{下標(biāo)} While (Not Eof) Do {讀入文件中的單詞并且存儲(chǔ)到數(shù)組中} Begin Readln(s)；