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