【正文】 單詞列表對應(yīng)的單詞查找樹的結(jié)點數(shù)。注意，對一個確定的單詞列表，請統(tǒng)計對應(yīng)的單詞查找樹的結(jié)點數(shù)（包含根結(jié)點）。程序框架如下：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)隊} While ( headtail) do Begin {隊列非空} p:=q[head]；head:=head+1； {取出隊首結(jié)點} Write(p^.data,‘ ‘)； {訪問某結(jié)點} For i:=1 To m Do {該結(jié)點的所有子結(jié)點按順序進(jìn)隊} If p^.child[i]Nil Then Begin q[tail]:=p^.child[I]；tail:=tail+1； End； End；End；例1：單詞查找樹[問題描述] 在進(jìn)行文法分析的時候，通常需要檢測一個單詞是否在我們的單詞列表里。層次遍歷應(yīng)用也較多，實際上就是我們所說的“廣度優(yōu)先搜索”。圖1后序遍歷的結(jié)果為：{5，6，2，3，8，9，7，4，1}；3．層次遍歷：按層次從小到大逐個訪問，同一層次按照從左到右的次序?？朔松鲜龅?種存儲方法的缺點，假設(shè)樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(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．孩子兄弟表示法：有些程序中需要對兄弟結(jié)點進(jìn)行處理，這種情況下，可以使用另外一種雙鏈表結(jié)構(gòu)，每個結(jié)點包括一個數(shù)據(jù)域和二個指針域，一個指針指向該結(jié)點的第一個孩子結(jié)點，一個指針指向該結(jié)點的下一個兄弟結(jié)點。假設(shè)樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10； {樹的度}Type tree=^node； node=Record data:Char； {數(shù)據(jù)域} child:Array[1..m] Of tree {指針域，指向若干孩子結(jié)點} End；Var t:tree；注：空間上的浪費其實可以用“虛開實用”的方法完美地解決，在FreePascal等環(huán)境下可以用Getmem、Freemem等過程達(dá)到這個目的，這樣建立一棵普通樹的時間復(fù)雜度也是很不錯的。數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10； {樹的結(jié)點數(shù)}Type node=Record data:Integer； {數(shù)據(jù)域} parent:Integer； {指針域} End；Var tree:Array[1..m] Of node；這種方法充分利用了樹中除根結(jié)點外每個結(jié)點都有唯一的父結(jié)點這個性質(zhì)，很容易找到樹根（可以規(guī)定根結(jié)點的父結(jié)點為0），但找孩子時卻需要遍歷整個線性表。三、樹的表示方法和存儲結(jié)構(gòu)樹的表示方法有多種，如圖1采用的就是一種形象的樹形表示法；另外還有一種常用的表示方法“括號表示法”，它的表示方法歸納如下：先將整棵樹的根結(jié)點放入一對圓括號中，然后把它的子樹由左至右放入括號中，同層子樹用圓括號括在一起（同層子樹之間用逗號隔開），而對子樹也采用同樣的方法處理，直到所有的子樹都只有一個根結(jié)點為止。從根結(jié)點出發(fā)，到樹中的其余結(jié)點一定存在著一條路徑。因為任何無序樹都可以當(dāng)作具有任一次序的有序樹來處理，所以下面如果不特別指明，均認(rèn)為樹是有序的。4．若樹中各結(jié)點的子樹是按照一定的次序從左向右安排的，它們之間的次序不能互換，這樣的樹稱之為有序樹，否則稱之為無序樹。如結(jié)點9都是結(jié)點4的子孫。如結(jié)點1是結(jié)點4的父結(jié)點，結(jié)點 4都是結(jié)點1的子結(jié)點，它們又是兄弟結(jié)點，同時結(jié)點2又是結(jié)點6的父結(jié)點。度不為0的結(jié)點稱為分支結(jié)點（如結(jié)點7）。第一節(jié) 樹一、樹的定義一棵樹（tree）是由n（n0）個元素組成的有限集合，其中：1．每個元素稱為結(jié)點(node)；2．有一個特定的結(jié)點，稱為根結(jié)點或樹根（root）；3．除根結(jié)點外，其余結(jié)點被分成m（m=0）個互不相交的有限集合T0,T1,T2,……Tm1，而每一個子集Ti又都是一棵樹（稱為原樹的子樹subtree）。樹型結(jié)構(gòu)在現(xiàn)實世界中廣泛存在，如把一個家族看作為一棵樹，樹中的結(jié)點為家族成員的姓名及相關(guān)信息，樹中的關(guān)系為父子關(guān)系，即父親是兒子的前驅(qū)，兒子是父親的后繼；把一個國家或一個地區(qū)的各級行政區(qū)劃分看作為一棵樹，樹中的結(jié)點為行政區(qū)的名稱及相關(guān)信息，樹中的關(guān)系為上下級關(guān)系，如一個城市包含有若干個區(qū)，每個區(qū)又包含有若干個街道，每個街道又包含有若干個居委會；把一本書的結(jié)構(gòu)看作是一棵樹，樹中的結(jié)點為書、章、節(jié)的名稱及相關(guān)信息，樹中的關(guān)系為包含關(guān)系。樹在計算機(jī)領(lǐng)域中也有廣泛應(yīng)用，如在編譯系統(tǒng)中，用樹表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)是數(shù)據(jù)庫層次模型的基礎(chǔ)，也是各種索引和目錄的主要組織形式。圖1圖1就是一棵典型的樹結(jié)構(gòu)。根結(jié)點以外的分支結(jié)點又稱為內(nèi)部結(jié)點（如結(jié)點7）。稱從根結(jié)點到某個子結(jié)點所經(jīng)過的所有結(jié)點為這個子結(jié)點的祖先。3．定義一棵樹的根結(jié)點的層次（level）為1，其它結(jié)點的層次等于它的父結(jié)點的層次數(shù)加1。所以，樹雖然是非線性結(jié)構(gòu)，但也是有序結(jié)構(gòu)。圖2，如果從一個結(jié)點出發(fā)，按層次自上而下沿著一個個樹枝能到達(dá)另一結(jié)點，稱它們之間存在著一條路徑。注意，不同子樹上的結(jié)點之間不存在路徑。用括號表示法表示圖1的步驟如下：=（T）=（1（T1，T2 ，T3 ）） {A是根結(jié)點，有3棵子樹，用逗號隔開}=（1（2（T11，T12），3，4（T31））） {分別對3棵子樹做同樣的操作}=（1（2（5，6），3，4（7（T311，T312））））=（1（2（5，6），3，4（7（8，9））））實際上，以上方法是按照樹的層次逐步展開，直到所有結(jié)點都已列出。2．孩子表示法：利用單鏈表，每個結(jié)點包括一個數(shù)據(jù)域和若干個指針域，每個指針都指向一個孩子結(jié)點。有興趣的同學(xué)可以參考有關(guān)書籍與程序。克服了上述第2種存儲方法的缺點，假設(shè)樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(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é)點的信息，這種操作叫做“樹的遍歷”。圖1層次遍歷的結(jié)果為：{1，2，3，4，5，6，7，8，9}；4．葉結(jié)點遍歷：有時我們把所有的數(shù)據(jù)信息都存放在葉結(jié)點中，而其余結(jié)點都是用來表示數(shù)據(jù)之間的某種分支或?qū)哟侮P(guān)系，這種情況就用這種方法。思想如下：若某個結(jié)點被訪問，則該結(jié)點的子結(jié)點應(yīng)被記錄下來，等待被訪問。為了提高查找和定位的速度，通常都畫出與單詞列表所對應(yīng)的單詞查找樹，其特點如下：1．根結(jié)點不包含字母，除根結(jié)點外每一個結(jié)點都僅包含一個大寫英文字母；2．從根結(jié)點到某一結(jié)點，路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列，稱為該結(jié)點對應(yīng)的單詞。[問題輸入] ，該文件為一個單詞列表，每一行僅包含一個單詞和一個換行/回車符。 [樣例輸入] AANASPASASCASCIIBASBASIC [樣例輸出] 13