安陽一中oi7月23日第五章樹

1、 在層次最大的兩層上出現(xiàn)；對任一結(jié)點，若其由分支下的子孫的最大層次為 m，則在其左分支下的子孫的最大層次必為 m 或 m+1。下圖 C、D 不是完全二叉樹，Q 請大家思考為什么？【性質(zhì) 3】對任何一棵二叉樹，如果其葉結(jié)點數(shù)為 n0，度為 2 的結(jié)點數(shù)為 n2，則一定滿足：n0=n2+1。證明：假設(shè)這棵樹的總結(jié)點樹為 n，度為 1 的結(jié)點樹為 n1。因為二叉樹中的所有結(jié)點的度都為 0、1、2，所以：n= n0+ n1+ n2再看二叉樹的分支數(shù)。除了根結(jié)點，其余每個結(jié)點都有且僅有一個分支進(jìn)入，設(shè) B為分支總數(shù)（入度），則 B=n-1。而度為 1 的結(jié)點有 1 個分支射出，度為 2 的結(jié)點有 2 個

2、分支射出，度為 0 的結(jié)點沒有分支射出，所以分支總數(shù)（出度）又等于：n1+2*n2,當(dāng)然，入度=出度，即：n-1= n1+2*n2,所以得出：n= n1+2*n2+1由可以得出：n0=n2+1。n【性質(zhì) 4】具有 n 個結(jié)點的完全二叉樹的深度為 trunc(LOG2 )+1證明：假設(shè)深度為 k，則根據(jù)完全二叉樹的定義，前面 k-1 層一定是滿的，所以 n2k1 -1。但 n 又要滿足 n=2k -1。所以，2k 1 1n=2k -1。變換一下為 2k 1 =n2k 1。以nn2 為底取對數(shù)得到：k-1=LOG2 0 Then Begingil := 1；gli := 1 End；If r En

3、d；For k :=0 Then Begingir := 1；gri := 1 End；1To n Do用Floyed法求任意兩結(jié)點之間的最短路徑長For i :=1 To n DoIf i k ThenFor j := 1 To n DoIf (i j) And (k j) And (gik + gkj gij)Then gij := gik + gkj； min := Maxlong；For i := 1 To n Do窮舉醫(yī)院建在N個結(jié)點，找出最短距離Begintotal := 0；For j := 1 To n DoInc(total, gij * aj)；If total mhen

4、min := total；End；Wrin(min)；Close(Input)；Close(Output)；End.【后記】在各種競賽中經(jīng)常遇到這樣：N-1 條公路連接著 N 個城市，從每個城市出發(fā)都可以通過公路到達(dá)其它任意的城市。每個城市里面都有一定數(shù)量的居民，但是數(shù)量并不一定相等，每條公路的長度也不一定相等。X 公司（或者是）決定在某一個城市建立一個醫(yī)院/酒廠/游樂場，問：將它建在哪里，可以使得所有的居民移動到那里的總耗費最??？這種題目都是本題的“變型”，一般稱為“樹的中心點問題”。除了簡單的窮舉法外，還有更好的時間復(fù)雜度為 O(n)的算法，講在后面的章節(jié)中繼續(xù)。235 輸出：（5-4）2

5、4（4+8）（5-3）24輸入： 輸出：！6算術(shù)表達(dá)式由鍵盤輸入一個算術(shù)表達(dá)式，該表達(dá)式由 09，加（+）、減（-）、乘（*）、求商（）運算符及括號組成。例如：6+8*(5-5*(26-1)2+7)是一個合法表達(dá)式。請編一個程序，對輸入的表達(dá)式，如不合法，輸出“ERROR”，如合法，則計算其值。輸入樣例 1 6+83輸出樣例 18輸入樣例 2 6+8+3輸出樣例 2ERROR7求不連續(xù)重復(fù)字符序列所謂不連續(xù)重復(fù)字符序列是指由大寫字母中前 L 個字母組成的字符序列中無連續(xù)重復(fù)的子串。例如：以下為有連續(xù)重復(fù)字串的字符序列：AA ABCDACABCABC ABCDABCD又如：以下為沒有連續(xù)重復(fù)子串的字符序列：A ABABCAB CBABCBA輸入和輸出：請編寫程序，讀入整數(shù) N 和 L，其中 0N80，1L26，輸出第 N 個由前 L 個字母組成的不連續(xù)重復(fù)字符序列,以及這個序列的長度。顯然，第 1 個不連續(xù)重復(fù)字符序列為 A。假定由給出