樹的枚舉與計數(shù)

1、樹的枚舉與計數(shù)一. 引子4個結(jié)點的樹（有向樹） 樹，在計算機算法中是非常重要的非線形結(jié)構(gòu)。即使撇開樹的其他廣泛應(yīng)用不說，單單對樹本身的形態(tài)進行思考與研究，也是一個十分有趣，且具有挑戰(zhàn)性的過程。例如，我們想要知道，有著4個不可區(qū)別的結(jié)點的樹有幾棵？4個結(jié)點的無根樹（自由樹） 那么有n個結(jié)點的呢？如果再給這樣的樹加上深度的限制，是不是也可以解決？這些樹的形態(tài)又是怎樣的？它們之間有著什么樣的聯(lián)系？推廣到無根樹，問題會有怎樣的發(fā)展？ 下面，我們就集中力量來逐一解答這一系列的問題。在這個探索與討論的過程中，隨著有關(guān)樹的枚舉與計數(shù)的算法的得出，各種不同形態(tài)的樹將會以一種優(yōu)美的“序”為基礎(chǔ)被一一展示出來。二

2、. 一些概念在深入的討論之前，我們有必要首先將有關(guān)的基本概念明確一下。1. 樹的定義“一般地說，樹結(jié)構(gòu)是指結(jié)點之間的分枝關(guān)系，很象是在自然界的樹那樣?！庇嬎銠C程序設(shè)計技巧我們對一個樹的正式定義是：一個或多個結(jié)點的有限集合T，使：a) 有一個特別標出的稱為該樹的根root的結(jié)點，以及b) 剩下的結(jié)點（除根外）被分成m0個不相交的集合T1，Tm，而且這些集合的每一個又都是樹，樹T1，Tm被稱為這個根的子樹。甲乙 眾所周知，對于樹來說，遞歸的定義顯得最為恰當，因為遞歸是樹結(jié)構(gòu)的一個固有特征（在后面的算法設(shè)計中，也尤其重視了樹的遞歸特征）。 注意到，如果在定義的（b）中，子樹T1，Tm的相對次序是重要

3、的，那么這棵樹被稱為“有序樹”。如果當兩棵樹的差別僅僅在于子樹的相對次序時，我們一般不認為它們是不同的（即認為它們是同構(gòu)的，如上圖中的甲和乙，它們通過若干次子樹交換可以變作和對方完全相同的樹），我們稱它們?yōu)椤坝邢驑洹?，因為此時我們考慮的只是這些結(jié)點的相對方向，而不是次序。在下文中的計數(shù)和枚舉算法都是針對有向樹而言的。 關(guān)于樹的深度或者說是層數(shù)，在介紹數(shù)據(jù)結(jié)構(gòu)的文獻中有兩種不同的定義，一種認為根結(jié)點在第1層，另一種認為在第0層。在本文下面的論述中，凡涉及樹的深度的，都依據(jù)前一種概念。2. 無根樹 同時作為本文重點討論對象的還有無根樹（自由樹）。 “連通的無圈圖稱為自由樹。如果選定自由樹中的某個頂

4、點作樹根，以樹根為起點對每條邊定向，就能把一棵自由樹變成一棵通常的樹?！?數(shù)據(jù)結(jié)構(gòu)與算法 無根樹是不含回路的圖且恰有n-1條邊。 顧名思義，無根樹就是無父子關(guān)系而只有鄰接關(guān)系的樹。 容易發(fā)現(xiàn)，對某棵無根樹，指定其一個結(jié)點為根后，我們將得到一棵“有根樹”，而在將不同的有根樹轉(zhuǎn)化為無根樹時，又經(jīng)常得到相同的無根樹，這也是同構(gòu)現(xiàn)象。那么如何判定無根樹的同構(gòu)呢？甲 乙 甲*（乙*） 對于兩棵無根樹甲和乙，任取無根樹甲的某個結(jié)點作為根結(jié)點，形成一棵有根樹甲*，若存在以無根樹乙的某結(jié)點為根的有根樹乙*與甲*同構(gòu)，則稱甲乙兩樹同構(gòu)（如下圖）。 到此為止，我們已經(jīng)給出了樹和自由樹的一些初步概念?？梢灶A(yù)見，要對

5、不同形態(tài)的樹（以及無根樹）進行高效的計數(shù)乃至枚舉恐怕并非易如反掌。因為無論是有根樹還是無根樹，都存在極其普遍的同構(gòu)現(xiàn)象。而且從上面的討論來看，出現(xiàn)同構(gòu)現(xiàn)象的原因是結(jié)點（子樹）間缺乏“序”的關(guān)系。 三. 樹的計數(shù)算法1. 有向樹的計數(shù) 讓我們進入到頭一個問題有向樹的計數(shù)。為了增加解答的通用性，我們將直接確定具有n個結(jié)點，深度為d 的有向樹的個數(shù)。假設(shè)這樣的有向樹共有ad,n種。那么，具有n 個結(jié)點的有向樹的個數(shù)就等于： 正如上文提到的，由于一棵有向樹的子樹是無序的，同構(gòu)現(xiàn)象的大量滋生為計數(shù)工作制造了巨大的障礙。（當然，我們要考慮的有向樹的計數(shù)或枚舉算法決不是通過搜索所有有序樹，通過一次次的判斷和

6、排除同構(gòu)來實現(xiàn)的這樣做的效率將是十分低下的，因為這將是一個擁有指數(shù)級復(fù)雜度的算法，雖然不排除這種算法在小規(guī)模問題上的可行性，但僅僅通過局部的優(yōu)化是無法改變其本質(zhì)的。） 對于一棵有向樹，除去根結(jié)點，對其子樹進行排序。排序的規(guī)則簡單說來就是：深度大的子樹視為較大的子樹，深度相同時，擁有結(jié)點數(shù)較多的子樹視為較大的子樹。（注意，雖然在計數(shù)算法中，只須對根結(jié)點的子樹進行粗略的排序，但作為對這種排序規(guī)則的拓展，它應(yīng)當也是遞歸的，這一點詳見枚舉算法。） 考慮這棵有向樹的根結(jié)點的所有子樹的組成情況，對于任意一種組成方式，設(shè)深度為d1，結(jié)點數(shù)為n1的子樹有k1棵；深度為d2，結(jié)點數(shù)為n2的子樹有k2棵；深度為d

7、s，結(jié)點數(shù)為ns的子樹有ks棵，滿足：d1=d， 且根據(jù)上面的排序規(guī)則，對任意的1i<js，有didj，若di=dj，則必有ni>nj。由于形態(tài)不同的深度為di，結(jié)點數(shù)為ni的有向樹的總數(shù)是adi , ni，從中允許重復(fù)地選取ki棵，方案數(shù)無疑是： 所以，再由乘法原理，具有上述組成方式的有向樹的個數(shù)即為： 實現(xiàn)時可以使用一個遞歸的過程枚舉出所有符合上述排序規(guī)則的子樹組成方式，將每種組成方式得到的有根樹的個數(shù)全部相加，就求得ad,n。 添加過程定義為：procedure work (now : longint; last_d , last_n , rest_n : byte); la

8、st_d表示上一種類型的子樹的深度，last_n表示上一種類型子樹的結(jié)點數(shù)，rest_n表示“剩余未分配”的結(jié)點數(shù)。now為中間計算變量，具體說來，設(shè)當前已添加了t種類型的子樹，則 算法描述如下：procedure work (now : longint; last_d , last_n , rest_n : byte);var ni , di , ki , km : byte； beginif rest_n=0 then 本次添加結(jié)束，將now的值累加至sum else begin 首先嘗試添加與上一子樹同樣深度的子樹 for ni:= min (last_n-1, rest_n) down

9、to last_d do 當前子樹的結(jié)點數(shù)既要小于上一子樹, 也不能大于剩余結(jié)點數(shù), 同時,作為一棵深度為last_d的樹,至少要有l(wèi)ast_d個結(jié)點 begin km:=rest_n div ni; 最多能添加km棵這種類型的子樹 for ki:=1 to km do work(now* , last_d, ni, rest_n-ni*ki); end; 嘗試添加比上一子樹深度小的子樹 for di:=last_d-1 downto 1 do for ni:=rest_n downto di do begin km:=rest_n div ni; for ki:=1 to km do wor

10、k(now* , di, ni, rest_n-ni*ki ); end; end; end; procedure main (n , d : byte); 計算結(jié)點數(shù)為n，深度為d的不同有向樹的個數(shù)var ni, ki, km : byte;begin 為保證深度為d，第一棵子樹深度必為d-1 將sum 賦零 for ni:= n-1 downto d do begin km:=(n-1) div ni; 最多能添加km棵這種類型的子樹 for ki: = 1 to km do work( , d, ni, n-1-ni*ki); end; 將sum 賦給ad,nend;源程序見T_C.Pa

11、s (Tree Count)2. 有向樹的計數(shù)的改進算法 可以明確地說，上面的計數(shù)算法時間效率的瓶頸就在于對有向樹的每棵子樹情況的枚舉（即遞歸過程），事實上其中有不少是重復(fù)計算。所以，要提高時間效率，應(yīng)當盡力避免類似的窮舉過程。可以采取空間換時間的策略。 定義bd,n為一種特殊的有向樹的總數(shù)。這類有向樹具有如下性質(zhì)：它的結(jié)點數(shù)為n，它的每棵子樹的深度均為d。建立這個遞推變量的主要用途是 再定義ed,n為結(jié)點數(shù)為n，深度不大于d的有向樹的總數(shù)。易得： ， 它的作用在于減少累加運算。 再來看有向樹計數(shù)。 為了構(gòu)成一棵結(jié)點數(shù)為n，深度為d的有向樹，首先它必須擁有至少一棵深度為d-1的子樹。接下來，再

12、給它添加若干深度小于d-1的子樹，使它的子樹的總結(jié)點數(shù)達到n-1。于是，有： 我們可以很快發(fā)現(xiàn)，a和b之間交替互推的。因為： 作為bd,n描述的有向樹，它的每一棵子樹的深度均為d，對于任意一種組成方式，設(shè)結(jié)點數(shù)為n1的子樹有j1棵；結(jié)點數(shù)為n2的子樹有j2棵；結(jié)點數(shù)為ns的子樹有js棵，即得到上式。那么現(xiàn)在只有b的計算需要用到類似work并且相對簡單的遞歸過程。 具體的算法描述此處從略，參見源程序T_C2.Pas 。改進后的算法的時間效率得到了大幅度提高，從下表可略見一斑。（測試環(huán)境：PIII 500MHz，192Mb RAM，Borland Pascal 7.0，用時單位：s）N有向樹個數(shù)用

13、時N有向樹個數(shù)用時算法1算法2算法1算法2 1946886760.220.00271608373432911.260.0020128262280.330.00284500706626918.020.0521352218320.600.002912618655430828.520.0522970551811.040.003035442684759744.950.05232682828551.650.0031997171512998-0.05247437249842.690.00322809934352700-0.052520671746454.400.00337929819784355-0.05

14、2657596365107.090.003422409533673568-0.05 由于用Extended類型計算，沒有使用高精度，所以當N>34時，用算法2編寫的程序出現(xiàn)浮點數(shù)計算錯誤，而它的時間效率顯得可圈可點；算法1在N>30時即不能有效地工作。3. 無根樹的計數(shù) 對無根樹問題的一個很自然的也是應(yīng)當?shù)南敕ㄊ前阉推胀ǖ臉渎?lián)系在一起。尤其當有向樹的計數(shù)問題已經(jīng)被解決的時候。無根樹和有向樹的差別其實僅僅在于根的存在與否。在前面也已經(jīng)提到，有可能來指定無根樹的任何一個結(jié)點X并以唯一的方式對根賦予方向，使它成為一個以X為根的有向樹。 那么首先要在指定哪個結(jié)點為根上作出決定。為了要讓轉(zhuǎn)

15、變后的無根樹體現(xiàn)相對整齊或者說是和諧的狀態(tài)，更重要的是要讓它們變得易于彼此區(qū)別，并且盡力地在無根樹和它們的代表有向樹（下面簡稱為它們的特征樹）之間建立一種一一對應(yīng)的關(guān)系，我們提出如下的對“中心”的定義。 任何一棵無根樹必定至少存在一個中心點，以該結(jié)點為根的有根樹的所有子樹中，深度最大的兩棵子樹（可以為空樹）的深度差為0或1。這點是容易證明的，首先任取一點為根，若它的深度最大的兩棵子樹的深度差不大于1，則它就是一個中心；否則取其深度最大的子樹的根結(jié)點為新的根，重復(fù)上述過程，必然可以得到一個中心。 另一方面，任何一棵無根樹至多存在兩個中心點。為了證明這一點，我們先來證明，同一棵無根樹的兩個中心必然

16、相鄰：假設(shè)已知兩個中心A與B，那么它們之間有唯一的通路（如圖）。假定通路長為L（即包含L條邊，L1），而A和B在各自的一側(cè)的子樹（即AB通路（長為L）子樹最大深度dA子樹最大深度dB虛線框內(nèi)）的最大深度分別dA 和dB。不妨設(shè)dA dB，既然B為中心，根據(jù)中心的定義，有：（dA+L）- dB1，即（dA-dB）+L1，所以L1，即L=1。由此，一棵無根樹的“任何”兩個中心必相鄰；那么若一棵無根樹有2個以上中心，中心之間必然構(gòu)成回路，這與樹的定義不符。所以一棵無根樹最多有兩個中心。 進一步地，若深度最大的兩子樹的深度差為0，則稱該無根樹為單中心無根樹，以中心結(jié)點為根的有根樹為該無根樹的特征樹，如

17、圖（黑色表示中心）：單中心的無根樹顯然單中心樹的中心是唯一的； 若深度最大的兩子樹的深度差為1，則深度最大的子樹去掉后，整棵樹的深度與去掉的子樹相同，該無根樹可以看作是由兩棵深度相同的有根樹通過根結(jié)點相連而構(gòu)成的，這樣的無根樹稱為雙中心無根樹，如圖：雙中心的無根樹框中深度最大的子樹（深度為3）去掉后剩余部分深度也為3，構(gòu)成該無根樹的二棵深度相同的特征樹（子樹的根即為中心）。 下面討論一下特征樹與無根樹的對應(yīng)。對于兩棵無根樹而言，只要比較它們的特征樹即可得知它們是否同構(gòu)，因為以一棵無根樹非中心結(jié)點為根構(gòu)成的有根樹的深度最大的兩棵子樹（可以為空）的深度之差大于等于2，顯然與以中心點為根的特征樹是不

18、同構(gòu)的，作為結(jié)論，兩棵無根樹同構(gòu)當且僅當它們的特征樹存在同構(gòu)關(guān)系，兩棵單中心無根樹同構(gòu)當且僅當它們的特征樹同構(gòu)，兩棵雙中心無根樹同構(gòu)當且僅當它們各自的兩棵特征樹具有一一對應(yīng)的同構(gòu)關(guān)系，即特征樹甲1同構(gòu)于特征樹乙1，且特征樹甲2同構(gòu)于特征樹乙2，或甲2同構(gòu)于乙1，甲1同構(gòu)于乙2。 根據(jù)無根樹的“中心”定義，每一棵單中心無根樹可以唯一地對應(yīng)一棵有根樹（通過指定中心為根），而每一棵雙中心無根樹可以對應(yīng)為兩棵同深度的有根樹根根相連而成（兩個中心分別作為它們的根）。 至此，通過人為定義“中心”，由中心連接若干子樹，從而使我們得以直接生成有根特征樹等效地代替無根樹，避免重復(fù)生成。 無根樹的計數(shù)，需要針對雙

19、中心及單中心兩種情況分別討論。a) 雙中心 比較簡單：任選兩棵深度相同，結(jié)點數(shù)之和為n的有根樹，以根根相連的方法構(gòu)成雙中心的n結(jié)點無根樹。無須調(diào)用遞歸過程。計算表達式如下： 當n 為奇數(shù)時， 當n 為偶數(shù)時， 在上式中有一點需注意的就是：當n為偶數(shù)時，這棵雙中心無根樹可能由兩棵結(jié)點數(shù)，深度均相等的有根樹相連而成，則此時應(yīng)避免直接用乘法原理計算ad, n div 2*ad, n div 2，而應(yīng)采用可重復(fù)組合公式進行計算。b) 單中心 計算單中心無根樹時，可以用篩法。因為單中心無根樹必須滿足至少有兩棵子樹具有最大深度，所以凡是只有一棵子樹深度最大的即不符合條件，需要篩去。設(shè)單中心無根樹的特征樹深

20、度為d，則符合條件的無根樹總數(shù)為（其中a和e的定義同有根樹計數(shù)算法）： 那么n個結(jié)點的無根樹總數(shù)就是： 最后, sum1+sum2即為無根樹的總數(shù)。 作為評估上述算法時間復(fù)雜度的參考，下面給出按上述算法編寫的程序的運行情況表。源程序見NRT_C.Pas (None Root Tree Count) （程序用時極少，故不列入表內(nèi)）N無根樹個數(shù)N無根樹個數(shù)11 235231482807412 551243929989713 13012510463689014 3159262797934501577412775106545916193202820234430321748629295469566584

21、18123867301483087180219317955314033082902920823065321099724102212121445053330062886247922562375634823779631721四. 枚舉算法 上面僅僅是描述了時間復(fù)雜度較小的計數(shù)算法。是否存在時間復(fù)雜度較小的枚舉算法呢？答案是肯定的。同樣地，我們首先討論一下給定深度和結(jié)點數(shù)的有向樹枚舉算法。1. 有向樹的枚舉 在計數(shù)算法的討論中，為了避免重復(fù)計數(shù)，我們初步地定義了子樹的大小順序，在計數(shù)算法中，這種大小的定義僅僅用來區(qū)別了深度或結(jié)點數(shù)不同的子樹。 現(xiàn)在，我們需要枚舉出所有具有相同深度和結(jié)點數(shù)的有向樹的具

22、體結(jié)構(gòu)，顯然，我們需要知道具有相同深度和結(jié)點數(shù)，但結(jié)構(gòu)不同的兩棵樹的大小關(guān)系。于是，可以把上面的定義推廣到任意兩棵有向樹的大小關(guān)系的定義。 假設(shè)，當前要比較樹A與樹B的大?。銩與樹B的子樹都是按照前述的大小關(guān)系遞歸地從大到小排序的）。 它的比較過程是這樣的（注意，空樹被認為是深度及結(jié)點數(shù)均為0的樹）：若A的深度大于B，則A>B；若A的深度小于B，則A<B；若A與B深度相等，視A與B的結(jié)點數(shù)：若A的結(jié)點數(shù)大于B，則A>B；若A的結(jié)點數(shù)小于B，則A<B；若A與B的結(jié)點數(shù)相等，依次討論A與B的子樹：擁有較大子樹的樹較大。若當前討論的子樹相等，則討論A與B的下一棵子樹。 我們

23、注意到，上面的比較過程同樣是遞歸的。 這樣一來，我們實現(xiàn)了對任意有向樹的大小關(guān)系的定義。回到枚舉有向樹的問題上來：對于深度為d，結(jié)點數(shù)為n 的所有形態(tài)的有向樹，根據(jù)上面的比較規(guī)則，可以把它們從大到小排成一個序列。舉d=3，n=6為例，這個序列是： 進一步地，對于任意的n和d ，在相應(yīng)序列中的第一棵樹和最后一棵樹的形態(tài)是容易確定的，如下： 現(xiàn)在問題就轉(zhuǎn)化為，根據(jù)上述的大小定義，能否找到一種變換的規(guī)則，使根據(jù)這種規(guī)則，可以從最小的一棵樹開始，連續(xù)地、不遺漏不重復(fù)地生成接下來的所有不同形態(tài)的樹。應(yīng)當說，這是一個十分復(fù)雜的變換過程。 首先，從樹的序列中的一個形態(tài)變換到另一個形態(tài)，必然是一個變小的過程，

24、換句話說，在這個變換過程中，至少有一棵子樹被變小了（注意到，這里以及下文所提到的“大”與“小”的概念都是基于上文中定義的大小規(guī)則），變小的過程是通過奪走它的一個子結(jié)點實現(xiàn)的（在d=3，n=6的例子里，我們用一個虛線框來表示被變小的子樹）。 當然，隨后排在它后面的某些子樹將會得到這個被奪走的結(jié)點，或者被重新組合，它們會適當?shù)刈兇?，然而由于它們在有向樹大小比較的過程中的地位比先前被變小的那棵子樹要低，于是，總的說來，整個有向樹就被變小了。 在選擇被變小的子樹時值得注意的是，該子樹的變小對于整棵樹的影響必須盡量小，也就是說，變換的目的是要使整棵樹變小，但變小的幅度必須達到最微，以使它經(jīng)過變換后恰好可

25、以成為序列中緊鄰它的一棵樹而不是跳躍性的變換，這樣才能保證生成的不遺漏性。 所以，尋找變換規(guī)則要解決的第一個問題就是如何找到這棵當前需要被變小的子樹。為了方便起見，我們不妨就討論如何找到那個需要被奪走的結(jié)點（也就是說，在下一步變換中，這個結(jié)點將首先從它的父親那里被刪除，從而使它原先所在的那棵子樹變?。?，當然，這個被奪取的結(jié)點必然為葉結(jié)點?？偸茄刂斍敖Y(jié)點的最后一條邊深入下去與根結(jié)點直接相連的葉結(jié)點是不可能被刪除的。 有一點是顯然的，就是對于并列的若干子樹，應(yīng)當從后向前查找。因為排列越靠后的子樹，在大小比較時的地位越低，它們被變小，對整棵樹的影響就比較小。那么是不是只要從根開始，不斷地沿著當前結(jié)

26、點的最后一條邊深入下去找到的葉結(jié)點就是我們要找的結(jié)點呢？這樣做的一個明顯的反例就是：與根結(jié)點直接相連的葉結(jié)點是不可能從根結(jié)點刪除的。下一形態(tài)應(yīng)當刪除的葉子按上面方法找到的葉子 進一步的實驗證明，即使排除與根結(jié)點直接相連的葉結(jié)點之后，這種尋找方式依然是行不通的。雖然對于上面d=3，n=6的例子它似乎是每次都十分成功地找到了要被刪除的結(jié)點，但對于規(guī)模稍大一些的實例它又一次失去了說服力。讓我們來看下面這個例子，它們是d=4，n=8時的樹的序列中的相鄰的兩個樹形態(tài)。 這個例子給了我們一些很有價值的啟示。正確的算法是這樣的： 從根出發(fā)，在子結(jié)點中從后向前找到第一個非葉結(jié)點的結(jié)點，繼續(xù)搜索直到到達一個子結(jié)

27、點均為葉子的結(jié)點為止。是否可認為該結(jié)點的最后一個子結(jié)點為待刪除結(jié)點呢？事實上仍需進一步處理：假如，找到的待刪除結(jié)點A為其父親B唯一的子結(jié)點，也就意味著如果將A從它的父結(jié)點B刪除，那么以B為根的那棵子樹的深度將會減少1，同時，該子樹的上一級子樹甚至以上若干級子樹的深度也可能要降低如果B又是它父親的獨子的話（如下圖）如果將A從B斷開，則以B、C為根的子樹的深度都會受到影響。C有子結(jié)點E，ETarget回溯找到A，ATarget 在對樹的大小定義中，深度比結(jié)點數(shù)更優(yōu)先。所以，在選擇待刪除結(jié)點時，應(yīng)該盡量選擇刪除后不影響子樹深度的結(jié)點優(yōu)先處理。因此，在找到A結(jié)點后，必須沿其父親結(jié)點進行回溯，直到當前結(jié)

28、點以下的子樹的深度不因刪除A而改變?yōu)橹梗ㄔ谏蠄D中直到D結(jié)點），在回溯的過程中，如果經(jīng)過某一結(jié)點，它還有另一個子結(jié)點（比如上圖中的C，它還有另一個子結(jié)點E），那么就舍棄原來找到的結(jié)點A，把E定為待刪除的結(jié)點。 至此，我們找到了搜尋待刪除結(jié)點的算法。前一部分算法的給出 作為前一部分論述的小結(jié)，我們將“搜尋待刪除結(jié)點”算法描述具體地給出來。 在此之前，先將數(shù)據(jù)結(jié)構(gòu)解釋一下。因為涉及的樹的操作比較復(fù)雜，所以使用下面的存儲結(jié)構(gòu)：type link=nodetype; arr=array1.max of link; nodetype=record father:link; 指向父結(jié)點 son_num:by

29、te; 子結(jié)點個數(shù) dep,num:byte; 以當前結(jié)點為根的子樹的深度和包含的結(jié)點數(shù) son:arr; 兒子列表 end;輸出時調(diào)用change（root）將樹轉(zhuǎn)化為廣義表。用temp（字符串）存放廣義表。procedure change(pn:link);var i:byte;begin temp:=temp+'P' if pn.son_num<>0 then 非葉結(jié)點 begin temp:=temp+'(' for i:=1 to pn.son_num do 對每個子結(jié)點 change(pn.soni); temp:=temp+')

30、' end;end; 接下來的一個必不可少的過程是找深度為d，結(jié)點數(shù)為n的最大的一棵樹（作為整個生成算法的起點）。下面的算法就是用來生成這樣的一棵樹。pn將指向它的根。procedure make_biggest(pn:link; n,d:byte);var i:byte; qn:link;begin delete_except(pn); 刪除pn 的所有子樹（釋放它們占據(jù)的空間）， 初始化pn指向的存儲單元，下同 pn.dep:=d; pn.num:=n; if d<>1 then begin 建立“主鏈”，可參見上文有關(guān)最大樹的圖 for i:=d-1 downto 1

31、 do begin new(qn); pn.son_num:=1; pn.son1:=qn; with qn do begin 初始化qn指向的存儲單元 dep:=i; num:=n-(d-i); end; pn:=qn; end; pn.son_num:=0; pn.num:=1; 將剩余結(jié)點全部連接到最后一層，完成樹的構(gòu)造 pn:=pn.father; pn.son_num:=n-d+1; for i:=2 to n-d+1 do begin new(qn); pn.soni:=qn; with qn do begin 初始化qn指向的存儲單元 dep:=1; num:=1; end; e

32、nd; end;end; 下面是對于當前要變換的樹，找到其待刪除結(jié)點target的算法：procedure search; search for the next node to be changedvar i:byte; s,f:link; depthchange:boolean;begin s:=root; 從根開始 i:=1; while i<>0 do begin i:=s.son_num; while (i>0) and (s.soni.son_num=0) do dec(i); 從后向前找到第一個非葉子的子結(jié)點 if i<>0 then s:=s.so

33、ni; 若存在，則深入一層 end; target:=s.sons.son_num; 找到一個待刪除結(jié)點 depthchange:=true; s:=target; f:=target.father; while depthchange and (f<>root) do 向上回溯直至深度不再改變 begin if s<>f.son1 then depthchange:=false; if depthchange and (f.son_num>1) then 若出現(xiàn)另一個子結(jié)點 begin target:=f.sonf.son_num; exit; end; 則優(yōu)先

34、刪除該子結(jié)點 s:=f; f:=f.father; end;end;找到待刪除結(jié)點之后的處理過程 在找到該結(jié)點并刪除之后，又需要進行一系列的處理以形成一棵新的樹。在建立新樹的時候要強調(diào)的一點就是，“要使整棵樹變小，但變小的幅度必須達到最小”。 刪除一個結(jié)點之后，會出現(xiàn)兩種情況：子樹深度不變，結(jié)點數(shù)變?。换蛘呱疃茸冃?。 對于深度不變的情況，由于當前子樹的結(jié)點數(shù)變小，所以首先要在現(xiàn)在的深度和結(jié)點數(shù)情況下將其最大化。具體變換如下（其中f表示被刪除結(jié)點的父結(jié)點，假設(shè)target已被刪除）：make_biggest(f,f.num,f.dep); 首先使以f為根的子樹變?yōu)樽畲骯dd:=1; 表示現(xiàn)有一個

35、多余的結(jié)點有待調(diào)整時添加repeat s:=f; f:=f.father; 上一層結(jié)點f 找到當前子樹是其父結(jié)點的第i棵子樹 fit(f, f.soni, i, add); 將f的第i棵之后的所有子樹都變得盡量大，但根據(jù)子樹排序的要求，它們不得大于子樹i add:=0; until f=root;下面再就fit過程給出具體算法：procedure fit(pn:link; 子樹需要重新組合的父結(jié)點 pm:link; 作為樣本的子樹的根，也就是它之后的子樹均不能大于它 sta:byte; 這棵樣本子樹是它的父結(jié)點的第sta棵子樹 add:byte 是否有額外的結(jié)點要在重組時添加上去（例如有一個結(jié)

36、點被預(yù)先刪除，則add=1） );var i, now_n, now_d:byte; qn:link;begin 先將排在子樹sta之后的子樹全部刪除，因為它們將被重組，同時計算出被刪除的子樹的總結(jié)點數(shù)賦予rest_n，并對它們的父結(jié)點pn的有關(guān)信息進行相應(yīng)變動 inc(rest_n , add); sta_n:=pm.num; 樣本子樹的結(jié)點數(shù) tree_n:=rest_n div sta_n; 最多可復(fù)制多少棵同樣的子樹 復(fù)制子樹 for i:=1 to tree_n do begin 先建立子樹的根 inc(pn.son_num); dec(rest_n); new(qn); pn.so

37、npn.son_num:=qn; 初始化qn createtree(qn, pm); 對照以pm為根的子樹,以qn為根復(fù)制子樹 end; if (rest_n mod sta_n)<>0 then 還有剩余結(jié)點,但不足以復(fù)制樣本子樹 begin now_n:=rest_n mod sta_n; 計算剩余結(jié)點 now_d:=pm.dep; if now_n<now_d then now_d:=now_n; 計算剩余結(jié)點可以建立的子樹的最大深度 建立子樹的根 inc(pn.son_num); new(qn); pn.sonpn.son_num:=qn; 初始化qn make_bi

38、ggest(qn,now_n,now_d); 建立以qn為根的子樹(最大) end; caculate(pn); 最后,重新計算以pn為根的子樹中所有結(jié)點的dep和num值end; 對于刪除結(jié)點后子樹深度改變的，則要進行如下的處理（假設(shè)s為刪除結(jié)點target后，向上回溯遇到的第一個子樹深度不受影響的結(jié)點）： f:=s.father; 找到s為f的第i個子結(jié)點 將f的第i個子樹后的所有子樹刪除，改變f的相應(yīng)值，并將第i個子樹后的所有子樹的總結(jié)點數(shù)計算出來，賦給n1 make_biggest(s, n1+s.num ,s.dep); 將所有被刪除的結(jié)點添加到子樹i，并使之在保持原深度的基礎(chǔ)上成為

39、最大的子樹 f:=s; repeat s:=f; f:=f.father; 上一層結(jié)點f 找到當前子樹是其父結(jié)點的第i棵子樹 fit(f,f.soni,i,0); 將f的第i棵之后的所有子樹都變得盡量大，但根據(jù)子樹排序的要求，它們不得大于子樹i until f=root; 總的有根樹枚舉算法大致可以如下構(gòu)成：讀入d,nmake_biggest(root, n, d); 找第一棵樹while 未全部生成 do 這步判斷可以用計數(shù)算法得到的總數(shù)來判斷,也可以先求得最小的一棵樹用來判斷 begin search; 刪除target; 對樹進行變換(包括上面的兩種情況: 子樹深度改變, 以及深度未改變

40、); end;刪除結(jié)點，使子樹變小將后面的子樹重組（最大化）變換完成 雖然上面變換過程看似十分復(fù)雜，實質(zhì)上它是以一種簡潔和嚴謹?shù)囊?guī)律為基礎(chǔ)的。在仔細的研究中，大家可以體會到變換過程的和諧：它和自然數(shù)的遞減與退位還頗有相似之處。比如說：為了使2000成為比它小，但又與它相差最少的自然數(shù)，我們從低位到高位找到它的第一個非0位（也就是可以減小的位）千位2，將它減小1，同時，比它低的各位都須變?yōu)樽畲螅?），于是得到1999。再看一個有向樹變換的例子（如下圖）： 我們先從后向前找到一個待刪除結(jié)點，刪除它之后，然后對其它子樹進行了一定的變換（類似于上面把0變成為9的過程），確保了整棵樹變小的程度最小，從而

41、得到了序列中的下一棵有向樹。 以上介紹的算法可以實現(xiàn)給定深度d，結(jié)點數(shù)n，按照從大到小的順序變換生成所有形態(tài)的有向樹。算法中涉及的樹的復(fù)制，以及遍歷等，復(fù)雜度均為O（n），并且在樹的生成過程中完全沒有重復(fù)生成，所以整個算法的耗時主要還與不同形態(tài)樹的總數(shù)有關(guān)。 源程序見T_E.Pas (Tree Enumerate)2. 無根樹的枚舉 解決了有根樹的枚舉問題，通過中心的定義，可以比較容易地把無根樹的枚舉問題與之聯(lián)系起來解決。a) 雙中心 找兩棵深度相等，結(jié)點數(shù)之和為n的有根樹根根相連即可。假設(shè)這兩棵樹的深度為sub_d1, sub_d2, 結(jié)點數(shù)為sub_n1, sub_n2, 根結(jié)點為root

42、1和root2。下面簡稱這兩種類型的樹分別為樹A和樹B。算法如下：for sub_d1:=2 to n div 2 do begin for sub_n1:=sub_d1 to n div 2 do begin sub_n2:=n-sub_n1; sub_d2:=sub_d1; 找最大的樹A repeat if sub_n1=sub_n2 then createtree(root2, root1); 建立與樹A相等的樹B, 以保證A不大于B else 找最大的B; 將A與B 相連,得到一棵無根樹 while B的可能形態(tài)未全部生成 do begin 找下一棵B 其實這是有根數(shù)枚舉算法中的一步

43、將A與B 相連,得到一棵無根樹 end; 若A的所有可能形態(tài)都已生成,則退出循環(huán) 找下一棵A until false; end; end;b) 單中心 與計數(shù)算法略不同的是，我們?nèi)匀话褑沃行臒o根樹拆成兩棵有根樹，樹A為中心的一棵深度最大的子樹，余下的結(jié)點包括中心為樹B。樹A與樹B的關(guān)系除了樹A的深度比樹B小1之外，還要滿足樹A大于等于樹B的第一棵子樹（深度最大的子樹）。生成算法如下：for sub_d1:=1 to n div 2 do begin for sub_n1:=sub_d1 to n-(sub_d1+1) do begin if (sub_d1=1) and (sub_n1>

44、1) then break; 可能無法構(gòu)成樹 sub_n2:=n-sub_n1; sub_d2:=sub_d1+1; if sub_n2<sub_d2 then break; 可能無法構(gòu)成樹 找最大的A repeat fit(root2, root1, 0, sub_n2-1); 建立第一棵樹B，滿足樹B最大的子樹不大于樹A 將A與B相連得到一棵無根樹 while B的可能形態(tài)未全部生成 do begin 找下一棵B 其實這是有根數(shù)枚舉算法中的一步 將A與B 相連,得到一棵無根樹 end; 若A的所有可能形態(tài)都已生成,則退出循環(huán) 找下一棵A until false; end; end;

45、上述的無根樹枚舉算法實現(xiàn)了指定結(jié)點數(shù)的無根樹的不重復(fù)的直接生成。 值得一提的是，對于無根樹的枚舉，另一種當前普遍的做法是搜索加判重。這種搜索算法優(yōu)化后對于小規(guī)模問題的效果還是比較理想的。其主要優(yōu)化措施其實就是利用上文中所提到的排序思想對判重進行優(yōu)化（也可參見N-Block排序思想的應(yīng)用）。 我們可以用按照枚舉算法編寫的生成程序與這種搜索算法作一個比較（測試環(huán)境：PIII 500MHz，192Mb RAM，Borland Pascal 7.0，下文同，用時單位：s）：N11121314151617181920構(gòu)造用時0.050.050.110.160.491.213.198.5223.0862.

46、91搜索用時0.270.71 2.09 6.04 17.69 51.92152.20-源程序見NRT_E.Pas (None Root Tree Enumerate) 五. 拓展應(yīng)用與啟示1. NOI92 無根樹 “無根樹”，本身作為一道著名的信息學競賽題（NOI92），可以使用本文所討論的算法較為高效地解決。它的問題描述是這樣的： 無根樹與通常所說的樹（有根樹）很相似，它包括有結(jié)點和枝，但不含有根。無根樹結(jié)點間只有相鄰關(guān)系，而不存在父子結(jié)點關(guān)系。如圖1所示，是一棵有7個結(jié)點的無根樹；以圖1的A為根結(jié)點得到圖2所示的有根樹，以圖1的B為根結(jié)點得到圖3所示的有根樹，但從無根樹角度來看，圖1、圖2

47、、圖3是結(jié)構(gòu)相同的無根樹，同時無根樹的結(jié)構(gòu)與結(jié)點的名稱無關(guān)。 有根樹可以以字符串形式表示，其遞歸表示方法為：根結(jié)點（子樹1 子樹2 子樹3）。 如圖2、圖3的有根樹可以分別表示為A（B（CF（EGD）和B（ACF（EGD），需要注意的是，由于子樹的表示順序可以不同，所以一棵有根樹可以有多種表示方法，如圖3由字符串可表示為B（F（EGD）CA）或B（ACF（DEG）等。圖1ABCDEFG圖2ABCDFEG圖3ABCDEGF 表示無根樹時，可以以它的任一結(jié)點為根結(jié)點，將其看作有根樹從而可以利用有根樹的字符串表示形式來表示無根樹。 任務(wù)1： 由鍵盤輸入一個字符串表示的無根樹，無根樹的各結(jié)點的名稱用互

48、不相同的大寫英文字母表示。由用戶輸入一個結(jié)點的名稱，程序應(yīng)能夠輸出一種以該結(jié)點為根結(jié)點的字符串形式。 程序輸出無根樹的字符串形式時，各個結(jié)點的名稱無關(guān)緊要，所有結(jié)點都以P表示，以后的各種輸出也采用這種方式。 例如，用戶輸入無根樹的字符串形式：A（B（CD（EF） 指定的根結(jié)點為： D 程序應(yīng)能輸出： P（P（PP）PP） P（PP（PP）P） P（PPP（PP） 任務(wù)2： 輸入兩個串表示的無根樹，判斷其結(jié)構(gòu)是否一樣。注意與結(jié)點名稱無關(guān)，只考慮結(jié)構(gòu)。 任務(wù)3： 輸入無根樹的總枝數(shù)M（1M11），輸出所有技數(shù)為M互不相同的無根樹，并記錄總數(shù)。以字符串形式輸出： 例如，M=5時，共有6種不同結(jié)構(gòu)的無

49、根樹，如下所示： 注意：各種樹結(jié)構(gòu)的字符串表達形式不唯一。 解答 任務(wù)一，仍采用鏈式存儲結(jié)構(gòu)，先找到新的根結(jié)點，然后可以使用一個遞歸過程依據(jù)原樹建立一棵新的樹。源程序見Task1.Pas。 任務(wù)二，使用對子樹排序（排序的規(guī)則就象我們在上文中定義的一樣）的手段可以避免不斷交換子樹以得到所有可能表示的復(fù)雜過程，從而比較高效地進行同構(gòu)比較。先將兩棵有根樹分別進行子樹排序，如果所得的有根樹不同，那么我們對有根樹1進行換根換根的過程其實就是任務(wù)一。每次換根以后同樣要進行子樹排序，然后判斷有根樹1 的新生樹與（已排序的）有根樹2是否相同。重復(fù)上述過程直到出現(xiàn)兩樹相同（說明同構(gòu)）或有根樹1的所有結(jié)點均已被用作根一次（說明兩棵樹本質(zhì)不同）。源程序見Task2.Pas。任務(wù)三，對于一棵樹來說，總枝數(shù)為結(jié)點數(shù)減1。所以任務(wù)三就是一個給定結(jié)點數(shù)的無根樹枚舉