【正文】 n := n+1； index[n] := k+1；{第n個單詞的首字母起點下標} For i:=1 To Length(s) Do {存入一個單詞} a[k+i] := s[i]； k := k+i+1； {為下個單詞的下標設(shè)定好初值,i即為當前單詞的長度} End； For i:=1 To n Do {n個單詞的字典排序} 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； {計數(shù)器} pre := 39。； {前一個單詞} For i:=1 To n Do {統(tǒng)計} Begin now := 39。； j := index[i]； {第i個單詞的首字母在a數(shù)組中的下標為j} While (Ord(a[j])0) Do {換行符換成了空格} Begin now := now + a[j]；j := j+1；End； {當前處理的單詞存入now中} j := 1； While ((pre[j]=now[j]) And (j=length(pre))) Do Inc(j)；{求兩個單詞的差} tot := tot+(Length(now)j+1)； {累加} pre := now；{把當前單詞作為下次比較的前一個單詞} End； Writeln(tot+1)； Close(Input)；Close(Output)；End.第二節(jié) 二叉樹一、二叉樹的概念二叉樹（binary tree,簡寫成BT）是一種特殊的樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有二棵子樹，即二叉樹中不存在度大于2的結(jié)點，而且二叉樹的子樹有左子樹、右子樹之分，孩子有左孩子、右孩子之分，其次序不能顛倒，所以二叉樹是一棵有序樹。二、二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i1個結(jié)點（i=1）。特別地，一棵深度為k且有2k –1個結(jié)點的二叉樹稱為滿二叉樹。圖5可以對滿二叉樹的結(jié)點進行連續(xù)編號，約定編號從根結(jié)點起，自上而下，從左到右，由此引出完全二叉樹的定義：深度為k，有n個結(jié)點的二叉樹當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應時，稱為完全二叉樹。圖6完全二叉樹具有如下特征：葉結(jié)點只可能出現(xiàn)在最下面兩層上；對任一結(jié)點，若其右子樹深度為m，則其左子樹的深度必為m或m+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為trunc(LOG2n)+1 （trunc為取整函數(shù)）性質(zhì)5：一棵n個結(jié)點的完全二叉樹，對于任一編號為i結(jié)點，有：1．如果i=1,則結(jié)點i為根，無父結(jié)點；如果i1,則其父結(jié)點編號為trunc(i/2)。3．如果2*i+1n，則結(jié)點i無右孩子；否則右孩子編號為2*i+1。1．鏈式存儲結(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é)點} End；Var bt:tree；如圖9左邊所示的一棵二叉樹用單鏈表就可以表示成右邊的形式。其實如果樹的結(jié)點較少，也可采用鄰接矩陣的方法，這樣操作起來也很方便。這樣的二叉樹稱為表達式樹，如表達式（a+b/c）*(de)就可以表示成圖10?，F(xiàn)在要求在某個結(jié)點上建立一個醫(yī)院，使所有居民所走的路程之和為最小，同時約定，相鄰接點之間的距離為1。接下來的n行每行描述了一個結(jié)點的狀況，包含三個整數(shù)，整數(shù)之間用空格（一個或多個）分隔，其中：第一個數(shù)為居民人口數(shù)；第二個數(shù)為左鏈接，為0表示無鏈接；第三個數(shù)為右鏈接。 [樣例輸入]513 2 34 0 012 4 520 0 040 0 0[樣例輸出]81[問題分析] 這是一道簡單的二叉樹應用問題，問題中的結(jié)點數(shù)并不多，數(shù)據(jù)規(guī)模也不大，采用鄰接矩陣存儲，用Floyed法求出任意兩結(jié)點之間的最短路徑長，然后窮舉醫(yī)院可能建立的n個結(jié)點位置，找出一個最小距離的位置即可。[參考程序]Program p2(Input, Output)；Var a : Array [1..100] Of Longint； g : Array [1..100, 1..100] Of Longint； n, i, j, k, l, r, min, total : Longint；Begin Assign(Input, 39。)； Reset(Input)；Assign(Output, 39。)； Rewrite(Output)； Readln(n)； For i := 1 To n Do 圖11 For j := 1 To n Do g[i][j] := 1000000； For i := 1 To n Do {讀入、初始化} Begin g[i][i] := 0； Readln(a[i], l, r)； If l 0 Then Begin g[i][l] := 1；g[l][i] := 1 End； If r 0 Then Begin g[i][r] := 1；g[r][i] := 1 End； End； For k := 1 To n Do {用Floyed法求任意兩結(jié)點之間的最短路徑長} For i := 1 To n Do If i k Then For j := 1 To n Do If (i j) And (k j) And (g[i][k] + g[k][j] g[i][j]) Then g[i][j] := g[i][k] + g[k][j]； min := Maxlongint； For i := 1 To n Do {窮舉醫(yī)院建在N個結(jié)點，找出最短距離} Begin total := 0； For j := 1 To n Do Inc(total, g[i][j] * a[j])； If total min Then min := total； End； Writeln(min)；Close(Input)；Close(Output)；End.[后記] 在各種競賽中經(jīng)常遇到這樣的問題：N1條公路連接著N個城市，從每個城市出發(fā)都可以通過公路到達其它任意的城市。X公司（或者是政府）決定在某一個城市建立一個醫(yī)院/酒廠/游樂場……，問：將它建在哪里，可以使得所有的居民移動到那里的總耗費最??？這種題目都是本題的“變型”，一般稱為“樹的中心點問題”。四、普通樹轉(zhuǎn)換成二叉樹由于二叉樹是有序的，而且操作和應用更廣泛，所以在實際使用時，我們經(jīng)常把普通樹轉(zhuǎn)換成二叉樹進行操作。第一節(jié)中的圖1所示的普通樹轉(zhuǎn)換成二叉樹的過程如圖12所示：圖12同樣我們