江蘇常州高級中學(xué)李源

1、江蘇省常州高級中學(xué) 李源,樹的枚舉,樹，在計算機算法中是非常重要的非線形結(jié)構(gòu)。即使撇開樹的其他廣泛應(yīng)用不說，單單對樹本身的形態(tài)進行思考與研究，也是一個十分有趣，且具有挑戰(zhàn)性的過程。,引子,常規(guī)的搜索加判重的做法：,枚舉算法,下面我們就來看一種不重復(fù)地生成所有確定結(jié)點數(shù)和深度的有向樹的構(gòu)造性算法。,不重復(fù)性：樹的大小定義,不遺漏性：樹的變換算法,樹的大小定義,我們對樹的“大小”作一個規(guī)定，使不同樹結(jié)構(gòu)之間的關(guān)系有序化。假設(shè)當(dāng)前要比較

2、樹A與樹B的大小（樹A與樹B的子樹也都要按照下述的大小關(guān)系遞歸地從大到小排序）。 比較過程為：,若A的深度大于B，則A>B；若A的深度小于B，則AB；若A的結(jié)點數(shù)小于B，則A<B； 若A與B的結(jié)點數(shù)相等，依次討論A與B的子樹： 擁有較大子樹的樹較大。若當(dāng)前討論的子樹相等，則討論A與B的下一棵子樹。,現(xiàn)在回到枚舉有向樹的問題上來：對于深度為d，結(jié)點數(shù)為n 的所有形態(tài)的有向樹

3、，根據(jù)上面的比較規(guī)則，可以把它們從大到小排成一個序列。舉d=3，n=6為例，這個序列是：,,,,,,進一步地，對于任意的n和d ，在相應(yīng)序列中的第一棵樹和最后一棵樹的形態(tài)是容易確定的，如下：,現(xiàn)在問題就轉(zhuǎn)化為，根據(jù)上述的大小定義，能否找到一種變換的規(guī)則，使根據(jù)這種規(guī)則，可以從最小的一棵樹開始，連續(xù)地、不遺漏不重復(fù)地生成接下來的所有不同形態(tài)的樹？,首先，從樹的序列中的一個形態(tài)變換到另一個形態(tài)，是一個變小的過程。在這個變換過程中，至少有一

4、棵子樹被變小了，變小的過程是通過奪走它的一個子結(jié)點實現(xiàn)的（我們用一個虛線框來表示被變小的子樹）。,變換過程,它們會適當(dāng)?shù)刈兇?，然而由于它們在有向樹大小比較的過程中的地位比先前被變小的那棵子樹要低，于是，總的說來，整個有向樹就被變小了。,,,結(jié)點被奪去；,排在它后面的某些子樹將會得到這個被奪走的結(jié)點，或被重新組合。,,過程I 尋找被刪去結(jié)點,過程II 將被刪的結(jié)點重組到后面的子樹中,過程I 尋找被刪去結(jié)點,在選擇被刪去的結(jié)點時，其所

5、在子樹的變小對于整棵樹的影響必須盡量小。使它經(jīng)過變換后恰好可以成為序列中緊鄰它的一棵樹而不是跳躍性的變換。所以：,首先，這個被奪取的結(jié)點必然為葉結(jié)點。,第二，對于并列的若干子樹，應(yīng)當(dāng)從后向前查找。,過程I 算法,從根出發(fā)，在子結(jié)點中從后向前找到第一個非葉結(jié)點的結(jié)點，繼續(xù)搜索直到到達一個子結(jié)點均為葉子的結(jié)點為止。,是否可認為該結(jié)點的最后一個子結(jié)點為待刪除結(jié)點呢？事實上仍需進一步處理： 假如，找到的待刪除結(jié)點A為其父親B唯一的子結(jié)

6、點，也就意味著如果將A從它的父結(jié)點B刪除，那么以B為根的那棵子樹的深度將會減少1……,在對樹的大小定義中，深度比結(jié)點數(shù)更優(yōu)先。所以，在選擇待刪除結(jié)點時，應(yīng)該盡量選擇刪除后不影響子樹深度的結(jié)點優(yōu)先處理。因此，在找到A結(jié)點后，必須沿其父親結(jié)點進行回溯，直到當(dāng)前結(jié)點以下的子樹的深度不因刪除A而改變?yōu)橹梗ㄔ谏蠄D中直到D結(jié)點），在回溯的過程中，如果經(jīng)過某一結(jié)點，它還有另一個子結(jié)點（比如上圖中的C，它還有另一個子結(jié)點E），那么就舍棄原來找到的結(jié)點

7、A，把E定為待刪除的結(jié)點。,過程I 算法,如果將A從B斷開，則以B、C為根的子樹的深度都會受到影響。,C有子結(jié)點E，E→Target,回溯,找到A，A→Target,,過程II 將被刪的結(jié)點重組到后面的子樹中,在找到該結(jié)點并刪除之后，又需要進行一系列的處理以形成一棵新的樹。在建立新樹的時候要強調(diào)的一點就是，“要使整棵樹變小，但變小的幅度必須達到最小”。刪除一個結(jié)點之后，會出現(xiàn)兩種情況：,當(dāng)前子樹深度不變，結(jié)點數(shù)變??；或者子樹深度

8、變小。,下面就對這兩種情況分別進行討論。,過程II 算法 刪除結(jié)點后子樹深度不變,接下來，對排列在被改動的這棵子樹以后的其它子樹進行重新組合，使它們在滿足不大于當(dāng)前這棵子樹的情況下變得最大（同時將被刪除的那個結(jié)點加入）。,刪除結(jié)點，使子樹變小,,,將后面的子樹重組（最大化）,變換完成,過程II 算法 刪除結(jié)點后子樹深度變小,對于刪除結(jié)點后子樹深度改變的，則要進行如下的處理（舉例來說）：,F：要從父親處刪除的結(jié)點。C E： 深度

9、將會變小。要進一步處理。,將F刪去，處理E極其兄弟（此處為空），連同刪去的F，以C為根進行重組。,處理C極其兄弟（D），連同C以下的所有子樹，以C的父親B為根進行重組。得到新的樹。,完整的有根樹枚舉算法大致可以如下構(gòu)成：1 讀入d,n2 找第一棵樹（最大的）3 while 未全部生成 do {這步判斷可以用計數(shù)算法得到的總數(shù)來判斷,也可以先求得最小的一棵樹用來判斷}4 找到待刪除的結(jié)點tar

10、get;5 刪除target;6 對樹進行變換; {包括上面的兩種情況: 子樹深度改變, 以及深度未改變}7 end of while,小結(jié),雖然上面變換過程看似十分復(fù)雜，實質(zhì)上它是以一種簡潔和嚴謹?shù)囊?guī)律為基礎(chǔ)的。在仔細的研究中，大家可以體會到變換過程的和諧：它和自然數(shù)的遞減與退位還頗有相似之處。 比如說：為了使2000成為比它小，但又與它相差最少的自然數(shù)：,2000,,,1

11、999,,1000,類似地, 再看一個有向樹變換的例子:,刪除結(jié)點，使子樹變小,,,將后面的子樹重組（最大化）,變換完成,我們先從后向前找到一個待刪除結(jié)點，刪除它之后，然后對其它子樹進行了一定的變換（類似于上面把0變成為9的過程），確保了整棵樹變小的程度最小，從而得到了序列中的下一棵有向樹。,以上介紹的算法可以實現(xiàn)給定深度d，結(jié)點數(shù)n，按照從大到小的順序變換生成所有形態(tài)的有向樹。算法中涉及的樹的復(fù)制，以及遍歷等，復(fù)雜度均為O（n），并且