【正文】 單詞列表對(duì)應(yīng)的單詞查找樹(shù)的結(jié)點(diǎn)數(shù)。注意，對(duì)一個(gè)確定的單詞列表，請(qǐng)統(tǒng)計(jì)對(duì)應(yīng)的單詞查找樹(shù)的結(jié)點(diǎn)數(shù)（包含根結(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è)單詞是否在我們的單詞列表里。層次遍歷應(yīng)用也較多，實(shí)際上就是我們所說(shuō)的“廣度優(yōu)先搜索”。圖1后序遍歷的結(jié)果為：{5，6，2，3，8，9，7，4，1}；3．層次遍歷：按層次從小到大逐個(gè)訪問(wè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)。假設(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ò)的。數(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ù)的表示方法和存儲(chǔ)結(jié)構(gòu)樹(shù)的表示方法有多種，如圖1采用的就是一種形象的樹(shù)形表示法；另外還有一種常用的表示方法“括號(hào)表示法”，它的表示方法歸納如下：先將整棵樹(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)為止。從根結(jié)點(diǎn)出發(fā)，到樹(shù)中的其余結(jié)點(diǎn)一定存在著一條路徑。因?yàn)槿魏螣o(wú)序樹(shù)都可以當(dāng)作具有任一次序的有序樹(shù)來(lái)處理，所以下面如果不特別指明，均認(rèn)為樹(shù)是有序的。4．若樹(shù)中各結(jié)點(diǎn)的子樹(shù)是按照一定的次序從左向右安排的，它們之間的次序不能互換，這樣的樹(shù)稱(chēng)之為有序樹(shù)，否則稱(chēng)之為無(wú)序樹(shù)。如結(jié)點(diǎn)9都是結(jié)點(diǎn)4的子孫。如結(jié)點(diǎn)1是結(jié)點(diǎn)4的父結(jié)點(diǎn)，結(jié)點(diǎn) 4都是結(jié)點(diǎn)1的子結(jié)點(diǎn)，它們又是兄弟結(jié)點(diǎn)，同時(shí)結(jié)點(diǎn)2又是結(jié)點(diǎn)6的父結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)（如結(jié)點(diǎn)7）。第一節(jié) 樹(shù)一、樹(shù)的定義一棵樹(shù)（tree）是由n（n0）個(gè)元素組成的有限集合，其中：1．每個(gè)元素稱(chēng)為結(jié)點(diǎn)(node)；2．有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)或樹(shù)根（root）；3．除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成m（m=0）個(gè)互不相交的有限集合T0,T1,T2,……Tm1，而每一個(gè)子集Ti又都是一棵樹(shù)（稱(chēng)為原樹(shù)的子樹(shù)subtree）。樹(shù)型結(jié)構(gòu)在現(xiàn)實(shí)世界中廣泛存在，如把一個(gè)家族看作為一棵樹(shù)，樹(shù)中的結(jié)點(diǎn)為家族成員的姓名及相關(guān)信息，樹(shù)中的關(guān)系為父子關(guān)系，即父親是兒子的前驅(qū)，兒子是父親的后繼；把一個(gè)國(guó)家或一個(gè)地區(qū)的各級(jí)行政區(qū)劃分看作為一棵樹(shù)，樹(shù)中的結(jié)點(diǎn)為行政區(qū)的名稱(chēng)及相關(guān)信息，樹(shù)中的關(guān)系為上下級(jí)關(guān)系，如一個(gè)城市包含有若干個(gè)區(qū)，每個(gè)區(qū)又包含有若干個(gè)街道，每個(gè)街道又包含有若干個(gè)居委會(huì)；把一本書(shū)的結(jié)構(gòu)看作是一棵樹(shù)，樹(shù)中的結(jié)點(diǎn)為書(shū)、章、節(jié)的名稱(chēng)及相關(guān)信息，樹(shù)中的關(guān)系為包含關(guān)系。樹(shù)在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用，如在編譯系統(tǒng)中，用樹(shù)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)型結(jié)構(gòu)是數(shù)據(jù)庫(kù)層次模型的基礎(chǔ)，也是各種索引和目錄的主要組織形式。圖1圖1就是一棵典型的樹(shù)結(jié)構(gòu)。根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)又稱(chēng)為內(nèi)部結(jié)點(diǎn)（如結(jié)點(diǎn)7）。稱(chēng)從根結(jié)點(diǎn)到某個(gè)子結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)為這個(gè)子結(jié)點(diǎn)的祖先。3．定義一棵樹(shù)的根結(jié)點(diǎn)的層次（level）為1，其它結(jié)點(diǎn)的層次等于它的父結(jié)點(diǎn)的層次數(shù)加1。所以，樹(shù)雖然是非線性結(jié)構(gòu)，但也是有序結(jié)構(gòu)。圖2，如果從一個(gè)結(jié)點(diǎn)出發(fā)，按層次自上而下沿著一個(gè)個(gè)樹(shù)枝能到達(dá)另一結(jié)點(diǎn)，稱(chēng)它們之間存在著一條路徑。注意，不同子樹(shù)上的結(jié)點(diǎn)之間不存在路徑。用括號(hào)表示法表示圖1的步驟如下：=（T）=（1（T1，T2 ，T3 ）） {A是根結(jié)點(diǎn)，有3棵子樹(shù)，用逗號(hào)隔開(kāi)}=（1（2（T11，T12），3，4（T31））） {分別對(duì)3棵子樹(shù)做同樣的操作}=（1（2（5，6），3，4（7（T311，T312））））=（1（2（5，6），3，4（7（8，9））））實(shí)際上，以上方法是按照樹(shù)的層次逐步展開(kāi)，直到所有結(jié)點(diǎn)都已列出。2．孩子表示法：利用單鏈表，每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和若干個(gè)指針域，每個(gè)指針都指向一個(gè)孩子結(jié)點(diǎn)。有興趣的同學(xué)可以參考有關(guān)書(shū)籍與程序?？朔松鲜龅?種存儲(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層次遍歷的結(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)系，這種情況就用這種方法。思想如下：若某個(gè)結(jié)點(diǎn)被訪問(wèn)，則該結(jié)點(diǎn)的子結(jié)點(diǎn)應(yīng)被記錄下來(lái)，等待被訪問(wèn)。為了提高查找和定位的速度，通常都畫(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)成的字母序列，稱(chēng)為該結(jié)點(diǎn)對(duì)應(yīng)的單詞。[問(wèn)題輸入] ，該文件為一個(gè)單詞列表，每一行僅包含一個(gè)單詞和一個(gè)換行/回車(chē)符。 [樣例輸入] AANASPASASCASCIIBASBASIC [樣例輸出] 13