【文章內(nèi)容簡(jiǎn)介】 =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。39。)； Reset(Input)； Assign(Output,39。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)； n := n+1； index[n] := k+1；{第n個(gè)單詞的首字母起點(diǎn)下標(biāo)} For i:=1 To Length(s) Do {存入一個(gè)單詞} a[k+i] := s[i]； k := k+i+1； {為下個(gè)單詞的下標(biāo)設(shè)定好初值,i即為當(dāng)前單詞的長(zhǎng)度} End； For i:=1 To n Do {n個(gè)單詞的字典排序} For j:=i+1 To n Do If cmp(index[i], index[j]) Then Begin t := index[i]；index[i] := index[j]；index[j] := t；End； tot := 0； {計(jì)數(shù)器} pre := 39。39。； {前一個(gè)單詞} For i:=1 To n Do {統(tǒng)計(jì)} Begin now := 39。39。； j := index[i]； {第i個(gè)單詞的首字母在a數(shù)組中的下標(biāo)為j} While (Ord(a[j])0) Do {換行符換成了空格} Begin now := now + a[j]；j := j+1；End； {當(dāng)前處理的單詞存入now中} j := 1； While ((pre[j]=now[j]) And (j=length(pre))) Do Inc(j)；{求兩個(gè)單詞的差} tot := tot+(Length(now)j+1)； {累加} pre := now；{把當(dāng)前單詞作為下次比較的前一個(gè)單詞} End； Writeln(tot+1)； Close(Input)；Close(Output)；End.第二節(jié) 二叉樹(shù)一、二叉樹(shù)的概念二叉樹(shù)（binary tree,簡(jiǎn)寫(xiě)成BT）是一種特殊的樹(shù)型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)，即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)，而且二叉樹(shù)的子樹(shù)有左子樹(shù)、右子樹(shù)之分，孩子有左孩子、右孩子之分，其次序不能顛倒，所以二叉樹(shù)是一棵有序樹(shù)。它有如下5種基本形態(tài)：圖4第一節(jié)講述的樹(shù)的一些術(shù)語(yǔ)、概念也基本適用于二叉樹(shù)，但二叉樹(shù)與樹(shù)也有很多不同，如：二叉樹(shù)的每個(gè)結(jié)點(diǎn)至多只能有兩個(gè)結(jié)點(diǎn)，二叉樹(shù)一定是有序的，二叉樹(shù)可以為空（但樹(shù)不能為空，至少要有1個(gè)結(jié)點(diǎn)）。二、二叉樹(shù)的性質(zhì)：性質(zhì)1：在二叉樹(shù)的第i層上至多有2i1個(gè)結(jié)點(diǎn)（i=1）。性質(zhì)2：深度為k的二叉樹(shù)至多有2k –1個(gè)結(jié)點(diǎn)（k=1）。特別地，一棵深度為k且有2k –1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。圖5是深度為4的滿(mǎn)二叉樹(shù)，這種樹(shù)的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都達(dá)到了最大值。圖5可以對(duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，自上而下，從左到右，由此引出完全二叉樹(shù)的定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為完全二叉樹(shù)。 如圖6就是一個(gè)深度為4，結(jié)點(diǎn)數(shù)為12的完全二叉樹(shù)。圖6完全二叉樹(shù)具有如下特征：葉結(jié)點(diǎn)只可能出現(xiàn)在最下面兩層上；對(duì)任一結(jié)點(diǎn)，若其右子樹(shù)深度為m，則其左子樹(shù)的深度必為m或m+1。圖7和圖8所示的兩棵二叉樹(shù)就不是完全二叉樹(shù)，請(qǐng)讀者思考為什么？ 圖7 圖8性質(zhì)3：對(duì)任何一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則一定滿(mǎn)足：n0=n2+1。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為trunc(LOG2n)+1 （trunc為取整函數(shù)）性質(zhì)5：一棵n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，對(duì)于任一編號(hào)為i結(jié)點(diǎn)，有：1．如果i=1,則結(jié)點(diǎn)i為根，無(wú)父結(jié)點(diǎn)；如果i1,則其父結(jié)點(diǎn)編號(hào)為trunc(i/2)。2．如果2*in，則結(jié)點(diǎn)i為葉結(jié)點(diǎn)；否則左孩子編號(hào)為2*i。3．如果2*i+1n，則結(jié)點(diǎn)i無(wú)右孩子；否則右孩子編號(hào)為2*i+1。三、 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)與普通樹(shù)的存儲(chǔ)結(jié)構(gòu)基本相同，有鏈?zhǔn)胶晚樞虼鎯?chǔ)兩種方法。1．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):單鏈表結(jié)構(gòu)或雙鏈表結(jié)構(gòu)，基本數(shù)據(jù)結(jié)構(gòu)定義如下：Type tree=^node； {單鏈表結(jié)構(gòu)} node=Record data:Char； {數(shù)據(jù)域} lchild,rchild:tree {指針域：分別指向左、右孩子} End；Var bt:tree；Type tree=^node； {雙鏈表結(jié)構(gòu)} node=Record data:Char； {數(shù)據(jù)域} lchild,rchild,father:tree {指針域：分別指向左、右孩子及父結(jié)點(diǎn)} End；Var bt:tree；如圖9左邊所示的一棵二叉樹(shù)用單鏈表就可以表示成右邊的形式。 bt圖92．順序存儲(chǔ)結(jié)構(gòu):即幾個(gè)數(shù)組加一個(gè)指針變量，一般用在滿(mǎn)二叉樹(shù)和完全二叉樹(shù)中，將每個(gè)結(jié)點(diǎn)編號(hào)后作為數(shù)組的下標(biāo)變量值，基本數(shù)據(jù)結(jié)構(gòu)定義如下：Const n=10； {最多10個(gè)結(jié)點(diǎn)}Var data:Array[1..n] Of Char； {n個(gè)結(jié)點(diǎn)的數(shù)據(jù)域} lchild:Array[1..n] Of Integer； {n個(gè)結(jié)點(diǎn)的左孩子} rchild:Array[1..n] Of Integer； { n個(gè)結(jié)點(diǎn)的右孩子} bt:Integer； {根結(jié)點(diǎn)指針}這種結(jié)構(gòu)可以很方便地從根結(jié)點(diǎn)往下遍歷，但是如果想從某個(gè)分支結(jié)點(diǎn)或葉結(jié)點(diǎn)遍歷整棵樹(shù)，則還需設(shè)置一個(gè)父結(jié)點(diǎn)數(shù)組，操作也教麻煩。其實(shí)如果樹(shù)的結(jié)點(diǎn)較少，也可采用鄰接矩陣的方法，這樣操作起來(lái)也很方便。二叉樹(shù)在處理表達(dá)式時(shí)經(jīng)常用到，一般用葉結(jié)點(diǎn)表示運(yùn)算數(shù)，分支結(jié)點(diǎn)表示運(yùn)算符。這樣的二叉樹(shù)稱(chēng)為表達(dá)式樹(shù)，如表達(dá)式（a+b/c）*(de)就可以表示成圖10。 bt 圖10例2：醫(yī)院設(shè)置 [問(wèn)題描述] 設(shè)有一棵二叉樹(shù)（如圖11），其中圈中的數(shù)字表示結(jié)點(diǎn)中居民的人口，圈邊上數(shù)字表示結(jié)點(diǎn)編號(hào)?，F(xiàn)在要求在某個(gè)結(jié)點(diǎn)上建立一個(gè)醫(yī)院，使所有居民所走的路程之和為最小，同時(shí)約定，相鄰接點(diǎn)之間的距離為1。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和=4*2+13+20+40=81……[輸入格式] ，其中第一行一個(gè)整數(shù)n，表示樹(shù)的結(jié)點(diǎn)數(shù)（n=100）。接下來(lái)的n行每行描述了一個(gè)結(jié)點(diǎn)的狀況，包含三個(gè)整數(shù)，整數(shù)之間用空格（一個(gè)或多個(gè)）分隔，其中：第一個(gè)數(shù)為居民人口數(shù)；第二個(gè)數(shù)為左鏈接，為0表示無(wú)鏈接；第三個(gè)數(shù)為右鏈接。[輸出格式] ，該文件只有一個(gè)整數(shù)，表示最小距離和。 [樣例輸入]513 2 34 0 012 4 520 0 040 0 0[樣例輸出]81[問(wèn)題分析] 這是一道簡(jiǎn)單的二叉樹(shù)應(yīng)用問(wèn)題，問(wèn)題中的結(jié)點(diǎn)數(shù)并不多，數(shù)據(jù)規(guī)模也不大，采用鄰