树的枚举与计数

1、树的枚举与计数一. 引子4个结点的树（有向树） 树，在计算机算法中是非常重要的非线形结构。即使撇开树的其他广泛应用不说，单单对树本身的形态进行思考与研究，也是一个十分有趣，且具有挑战性的过程。例如，我们想要知道，有着4个不可区别的结点的树有几棵？4个结点的无根树（自由树） 那么有n个结点的呢？如果再给这样的树加上深度的限制，是不是也可以解决？这些树的形态又是怎样的？它们之间有着什么样的联系？推广到无根树，问题会有怎样的发展？ 下面，我们就集中力量来逐一解答这一系列的问题。在这个探索与讨论的过程中，随着有关树的枚举与计数的算法的得出，各种不同形态的树将会以一种优美的“序”为基础被一一展示出来。二

2、. 一些概念在深入的讨论之前，我们有必要首先将有关的基本概念明确一下。1. 树的定义“一般地说，树结构是指结点之间的分枝关系，很象是在自然界的树那样。”计算机程序设计技巧我们对一个树的正式定义是：一个或多个结点的有限集合T，使：a) 有一个特别标出的称为该树的根root的结点，以及b) 剩下的结点（除根外）被分成m0个不相交的集合T1，Tm，而且这些集合的每一个又都是树，树T1，Tm被称为这个根的子树。甲乙 众所周知，对于树来说，递归的定义显得最为恰当，因为递归是树结构的一个固有特征（在后面的算法设计中，也尤其重视了树的递归特征）。 注意到，如果在定义的（b）中，子树T1，Tm的相对次序是重要

3、的，那么这棵树被称为“有序树”。如果当两棵树的差别仅仅在于子树的相对次序时，我们一般不认为它们是不同的（即认为它们是同构的，如上图中的甲和乙，它们通过若干次子树交换可以变作和对方完全相同的树），我们称它们为“有向树”，因为此时我们考虑的只是这些结点的相对方向，而不是次序。在下文中的计数和枚举算法都是针对有向树而言的。 关于树的深度或者说是层数，在介绍数据结构的文献中有两种不同的定义，一种认为根结点在第1层，另一种认为在第0层。在本文下面的论述中，凡涉及树的深度的，都依据前一种概念。2. 无根树 同时作为本文重点讨论对象的还有无根树（自由树）。 “连通的无圈图称为自由树。如果选定自由树中的某个顶

4、点作树根，以树根为起点对每条边定向，就能把一棵自由树变成一棵通常的树。” 数据结构与算法 无根树是不含回路的图且恰有n-1条边。 顾名思义，无根树就是无父子关系而只有邻接关系的树。 容易发现，对某棵无根树，指定其一个结点为根后，我们将得到一棵“有根树”，而在将不同的有根树转化为无根树时，又经常得到相同的无根树，这也是同构现象。那么如何判定无根树的同构呢？甲 乙 甲*（乙*） 对于两棵无根树甲和乙，任取无根树甲的某个结点作为根结点，形成一棵有根树甲*，若存在以无根树乙的某结点为根的有根树乙*与甲*同构，则称甲乙两树同构（如下图）。 到此为止，我们已经给出了树和自由树的一些初步概念。可以预见，要对

5、不同形态的树（以及无根树）进行高效的计数乃至枚举恐怕并非易如反掌。因为无论是有根树还是无根树，都存在极其普遍的同构现象。而且从上面的讨论来看，出现同构现象的原因是结点（子树）间缺乏“序”的关系。 三. 树的计数算法1. 有向树的计数 让我们进入到头一个问题有向树的计数。为了增加解答的通用性，我们将直接确定具有n个结点，深度为d 的有向树的个数。假设这样的有向树共有ad,n种。那么，具有n 个结点的有向树的个数就等于： 正如上文提到的，由于一棵有向树的子树是无序的，同构现象的大量滋生为计数工作制造了巨大的障碍。（当然，我们要考虑的有向树的计数或枚举算法决不是通过搜索所有有序树，通过一次次的判断和

6、排除同构来实现的这样做的效率将是十分低下的，因为这将是一个拥有指数级复杂度的算法，虽然不排除这种算法在小规模问题上的可行性，但仅仅通过局部的优化是无法改变其本质的。） 对于一棵有向树，除去根结点，对其子树进行排序。排序的规则简单说来就是：深度大的子树视为较大的子树，深度相同时，拥有结点数较多的子树视为较大的子树。（注意，虽然在计数算法中，只须对根结点的子树进行粗略的排序，但作为对这种排序规则的拓展，它应当也是递归的，这一点详见枚举算法。） 考虑这棵有向树的根结点的所有子树的组成情况，对于任意一种组成方式，设深度为d1，结点数为n1的子树有k1棵；深度为d2，结点数为n2的子树有k2棵；深度为d

7、s，结点数为ns的子树有ks棵，满足：d1=d， 且根据上面的排序规则，对任意的1i<js，有didj，若di=dj，则必有ni>nj。由于形态不同的深度为di，结点数为ni的有向树的总数是adi , ni，从中允许重复地选取ki棵，方案数无疑是： 所以，再由乘法原理，具有上述组成方式的有向树的个数即为： 实现时可以使用一个递归的过程枚举出所有符合上述排序规则的子树组成方式，将每种组成方式得到的有根树的个数全部相加，就求得ad,n。 添加过程定义为：procedure work (now : longint; last_d , last_n , rest_n : byte); la

8、st_d表示上一种类型的子树的深度，last_n表示上一种类型子树的结点数，rest_n表示“剩余未分配”的结点数。now为中间计算变量，具体说来，设当前已添加了t种类型的子树，则 算法描述如下：procedure work (now : longint; last_d , last_n , rest_n : byte);var ni , di , ki , km : byte； beginif rest_n=0 then 本次添加结束，将now的值累加至sum else begin 首先尝试添加与上一子树同样深度的子树 for ni:= min (last_n-1, rest_n) down

9、to last_d do 当前子树的结点数既要小于上一子树, 也不能大于剩余结点数, 同时,作为一棵深度为last_d的树,至少要有last_d个结点 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); 计算结点数为n，深度为d的不同有向树的个数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. 有向树的计数的改进算法 可以明确地说，上面的计数算法时间效率的瓶颈就在于对有向树的每棵子树情况的枚举（即递归过程），事实上其中有不少是重复计算。所以，要提高时间效率，应当尽力避免类似的穷举过程。可以采取空间换时间的策略。 定义bd,n为一种特殊的有向树的总数。这类有向树具有如下性质：它的结点数为n，它的每棵子树的深度均为d。建立这个递推变量的主要用途是 再定义ed,n为结点数为n，深度不大于d的有向树的总数。易得： ， 它的作用在于减少累加运算。 再来看有向树计数。 为了构成一棵结点数为n，深度为d的有向树，首先它必须拥有至少一棵深度为d-1的子树。接下来，再

12、给它添加若干深度小于d-1的子树，使它的子树的总结点数达到n-1。于是，有： 我们可以很快发现，a和b之间交替互推的。因为： 作为bd,n描述的有向树，它的每一棵子树的深度均为d，对于任意一种组成方式，设结点数为n1的子树有j1棵；结点数为n2的子树有j2棵；结点数为ns的子树有js棵，即得到上式。那么现在只有b的计算需要用到类似work并且相对简单的递归过程。 具体的算法描述此处从略，参见源程序T_C2.Pas 。改进后的算法的时间效率得到了大幅度提高，从下表可略见一斑。（测试环境：PIII 500MHz，192Mb RAM，Borland Pascal 7.0，用时单位：s）N有向树个数用

13、时N有向树个数用时算法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编写的程序出现浮点数计算错误，而它的时间效率显得可圈可点；算法1在N>30时即不能有效地工作。3. 无根树的计数 对无根树问题的一个很自然的也是应当的想法是把它和普通的树联系在一起。尤其当有向树的计数问题已经被解决的时候。无根树和有向树的差别其实仅仅在于根的存在与否。在前面也已经提到，有可能来指定无根树的任何一个结点X并以唯一的方式对根赋予方向，使它成为一个以X为根的有向树。 那么首先要在指定哪个结点为根上作出决定。为了要让转

15、变后的无根树体现相对整齐或者说是和谐的状态，更重要的是要让它们变得易于彼此区别，并且尽力地在无根树和它们的代表有向树（下面简称为它们的特征树）之间建立一种一一对应的关系，我们提出如下的对“中心”的定义。 任何一棵无根树必定至少存在一个中心点，以该结点为根的有根树的所有子树中，深度最大的两棵子树（可以为空树）的深度差为0或1。这点是容易证明的，首先任取一点为根，若它的深度最大的两棵子树的深度差不大于1，则它就是一个中心；否则取其深度最大的子树的根结点为新的根，重复上述过程，必然可以得到一个中心。 另一方面，任何一棵无根树至多存在两个中心点。为了证明这一点，我们先来证明，同一棵无根树的两个中心必然

16、相邻：假设已知两个中心A与B，那么它们之间有唯一的通路（如图）。假定通路长为L（即包含L条边，L1），而A和B在各自的一侧的子树（即AB通路（长为L）子树最大深度dA子树最大深度dB虚线框内）的最大深度分别dA 和dB。不妨设dA dB，既然B为中心，根据中心的定义，有：（dA+L）- dB1，即（dA-dB）+L1，所以L1，即L=1。由此，一棵无根树的“任何”两个中心必相邻；那么若一棵无根树有2个以上中心，中心之间必然构成回路，这与树的定义不符。所以一棵无根树最多有两个中心。 进一步地，若深度最大的两子树的深度差为0，则称该无根树为单中心无根树，以中心结点为根的有根树为该无根树的特征树，如

17、图（黑色表示中心）：单中心的无根树显然单中心树的中心是唯一的； 若深度最大的两子树的深度差为1，则深度最大的子树去掉后，整棵树的深度与去掉的子树相同，该无根树可以看作是由两棵深度相同的有根树通过根结点相连而构成的，这样的无根树称为双中心无根树，如图：双中心的无根树框中深度最大的子树（深度为3）去掉后剩余部分深度也为3，构成该无根树的二棵深度相同的特征树（子树的根即为中心）。 下面讨论一下特征树与无根树的对应。对于两棵无根树而言，只要比较它们的特征树即可得知它们是否同构，因为以一棵无根树非中心结点为根构成的有根树的深度最大的两棵子树（可以为空）的深度之差大于等于2，显然与以中心点为根的特征树是不

18、同构的，作为结论，两棵无根树同构当且仅当它们的特征树存在同构关系，两棵单中心无根树同构当且仅当它们的特征树同构，两棵双中心无根树同构当且仅当它们各自的两棵特征树具有一一对应的同构关系，即特征树甲1同构于特征树乙1，且特征树甲2同构于特征树乙2，或甲2同构于乙1，甲1同构于乙2。 根据无根树的“中心”定义，每一棵单中心无根树可以唯一地对应一棵有根树（通过指定中心为根），而每一棵双中心无根树可以对应为两棵同深度的有根树根根相连而成（两个中心分别作为它们的根）。 至此，通过人为定义“中心”，由中心连接若干子树，从而使我们得以直接生成有根特征树等效地代替无根树，避免重复生成。 无根树的计数，需要针对双

19、中心及单中心两种情况分别讨论。a) 双中心 比较简单：任选两棵深度相同，结点数之和为n的有根树，以根根相连的方法构成双中心的n结点无根树。无须调用递归过程。计算表达式如下： 当n 为奇数时， 当n 为偶数时， 在上式中有一点需注意的就是：当n为偶数时，这棵双中心无根树可能由两棵结点数，深度均相等的有根树相连而成，则此时应避免直接用乘法原理计算ad, n div 2*ad, n div 2，而应采用可重复组合公式进行计算。b) 单中心 计算单中心无根树时，可以用筛法。因为单中心无根树必须满足至少有两棵子树具有最大深度，所以凡是只有一棵子树深度最大的即不符合条件，需要筛去。设单中心无根树的特征树深

20、度为d，则符合条件的无根树总数为（其中a和e的定义同有根树计数算法）： 那么n个结点的无根树总数就是： 最后, sum1+sum2即为无根树的总数。 作为评估上述算法时间复杂度的参考，下面给出按上述算法编写的程序的运行情况表。源程序见NRT_C.Pas (None Root Tree Count) （程序用时极少，故不列入表内）N无根树个数N无根树个数11 235231482807412 551243929989713 13012510463689014 3159262797934501577412775106545916193202820234430321748629295469566584

21、18123867301483087180219317955314033082902920823065321099724102212121445053330062886247922562375634823779631721四. 枚举算法 上面仅仅是描述了时间复杂度较小的计数算法。是否存在时间复杂度较小的枚举算法呢？答案是肯定的。同样地，我们首先讨论一下给定深度和结点数的有向树枚举算法。1. 有向树的枚举 在计数算法的讨论中，为了避免重复计数，我们初步地定义了子树的大小顺序，在计数算法中，这种大小的定义仅仅用来区别了深度或结点数不同的子树。 现在，我们需要枚举出所有具有相同深度和结点数的有向树的具

22、体结构，显然，我们需要知道具有相同深度和结点数，但结构不同的两棵树的大小关系。于是，可以把上面的定义推广到任意两棵有向树的大小关系的定义。 假设，当前要比较树A与树B的大小（树A与树B的子树都是按照前述的大小关系递归地从大到小排序的）。 它的比较过程是这样的（注意，空树被认为是深度及结点数均为0的树）：若A的深度大于B，则A>B；若A的深度小于B，则A<B；若A与B深度相等，视A与B的结点数：若A的结点数大于B，则A>B；若A的结点数小于B，则A<B；若A与B的结点数相等，依次讨论A与B的子树：拥有较大子树的树较大。若当前讨论的子树相等，则讨论A与B的下一棵子树。 我们

23、注意到，上面的比较过程同样是递归的。 这样一来，我们实现了对任意有向树的大小关系的定义。回到枚举有向树的问题上来：对于深度为d，结点数为n 的所有形态的有向树，根据上面的比较规则，可以把它们从大到小排成一个序列。举d=3，n=6为例，这个序列是： 进一步地，对于任意的n和d ，在相应序列中的第一棵树和最后一棵树的形态是容易确定的，如下： 现在问题就转化为，根据上述的大小定义，能否找到一种变换的规则，使根据这种规则，可以从最小的一棵树开始，连续地、不遗漏不重复地生成接下来的所有不同形态的树。应当说，这是一个十分复杂的变换过程。 首先，从树的序列中的一个形态变换到另一个形态，必然是一个变小的过程，

24、换句话说，在这个变换过程中，至少有一棵子树被变小了（注意到，这里以及下文所提到的“大”与“小”的概念都是基于上文中定义的大小规则），变小的过程是通过夺走它的一个子结点实现的（在d=3，n=6的例子里，我们用一个虚线框来表示被变小的子树）。 当然，随后排在它后面的某些子树将会得到这个被夺走的结点，或者被重新组合，它们会适当地变大，然而由于它们在有向树大小比较的过程中的地位比先前被变小的那棵子树要低，于是，总的说来，整个有向树就被变小了。 在选择被变小的子树时值得注意的是，该子树的变小对于整棵树的影响必须尽量小，也就是说，变换的目的是要使整棵树变小，但变小的幅度必须达到最微，以使它经过变换后恰好可

25、以成为序列中紧邻它的一棵树而不是跳跃性的变换，这样才能保证生成的不遗漏性。 所以，寻找变换规则要解决的第一个问题就是如何找到这棵当前需要被变小的子树。为了方便起见，我们不妨就讨论如何找到那个需要被夺走的结点（也就是说，在下一步变换中，这个结点将首先从它的父亲那里被删除，从而使它原先所在的那棵子树变小），当然，这个被夺取的结点必然为叶结点。总是沿着当前结点的最后一条边深入下去与根结点直接相连的叶结点是不可能被删除的。 有一点是显然的，就是对于并列的若干子树，应当从后向前查找。因为排列越靠后的子树，在大小比较时的地位越低，它们被变小，对整棵树的影响就比较小。那么是不是只要从根开始，不断地沿着当前结

26、点的最后一条边深入下去找到的叶结点就是我们要找的结点呢？这样做的一个明显的反例就是：与根结点直接相连的叶结点是不可能从根结点删除的。下一形态应当删除的叶子按上面方法找到的叶子 进一步的实验证明，即使排除与根结点直接相连的叶结点之后，这种寻找方式依然是行不通的。虽然对于上面d=3，n=6的例子它似乎是每次都十分成功地找到了要被删除的结点，但对于规模稍大一些的实例它又一次失去了说服力。让我们来看下面这个例子，它们是d=4，n=8时的树的序列中的相邻的两个树形态。 这个例子给了我们一些很有价值的启示。正确的算法是这样的： 从根出发，在子结点中从后向前找到第一个非叶结点的结点，继续搜索直到到达一个子结

27、点均为叶子的结点为止。是否可认为该结点的最后一个子结点为待删除结点呢？事实上仍需进一步处理：假如，找到的待删除结点A为其父亲B唯一的子结点，也就意味着如果将A从它的父结点B删除，那么以B为根的那棵子树的深度将会减少1，同时，该子树的上一级子树甚至以上若干级子树的深度也可能要降低如果B又是它父亲的独子的话（如下图）如果将A从B断开，则以B、C为根的子树的深度都会受到影响。C有子结点E，ETarget回溯找到A，ATarget 在对树的大小定义中，深度比结点数更优先。所以，在选择待删除结点时，应该尽量选择删除后不影响子树深度的结点优先处理。因此，在找到A结点后，必须沿其父亲结点进行回溯，直到当前结

28、点以下的子树的深度不因删除A而改变为止（在上图中直到D结点），在回溯的过程中，如果经过某一结点，它还有另一个子结点（比如上图中的C，它还有另一个子结点E），那么就舍弃原来找到的结点A，把E定为待删除的结点。 至此，我们找到了搜寻待删除结点的算法。前一部分算法的给出 作为前一部分论述的小结，我们将“搜寻待删除结点”算法描述具体地给出来。 在此之前，先将数据结构解释一下。因为涉及的树的操作比较复杂，所以使用下面的存储结构：type link=nodetype; arr=array1.max of link; nodetype=record father:link; 指向父结点 son_num:by

29、te; 子结点个数 dep,num:byte; 以当前结点为根的子树的深度和包含的结点数 son:arr; 儿子列表 end;输出时调用change（root）将树转化为广义表。用temp（字符串）存放广义表。procedure change(pn:link);var i:byte;begin temp:=temp+'P' if pn.son_num<>0 then 非叶结点 begin temp:=temp+'(' for i:=1 to pn.son_num do 对每个子结点 change(pn.soni); temp:=temp+')

30、' end;end; 接下来的一个必不可少的过程是找深度为d，结点数为n的最大的一棵树（作为整个生成算法的起点）。下面的算法就是用来生成这样的一棵树。pn将指向它的根。procedure make_biggest(pn:link; n,d:byte);var i:byte; qn:link;begin delete_except(pn); 删除pn 的所有子树（释放它们占据的空间）， 初始化pn指向的存储单元，下同 pn.dep:=d; pn.num:=n; if d<>1 then begin 建立“主链”，可参见上文有关最大树的图 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; 将剩余结点全部连接到最后一层，完成树的构造 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; 下面是对于当前要变换的树，找到其待删除结点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); 从后向前找到第一个非叶子的子结点 if i<>0 then s:=s.so

33、ni; 若存在，则深入一层 end; target:=s.sons.son_num; 找到一个待删除结点 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 若出现另一个子结点 begin target:=f.sonf.son_num; exit; end; 则优先

34、删除该子结点 s:=f; f:=f.father; end;end;找到待删除结点之后的处理过程 在找到该结点并删除之后，又需要进行一系列的处理以形成一棵新的树。在建立新树的时候要强调的一点就是，“要使整棵树变小，但变小的幅度必须达到最小”。 删除一个结点之后，会出现两种情况：子树深度不变，结点数变小；或者深度变小。 对于深度不变的情况，由于当前子树的结点数变小，所以首先要在现在的深度和结点数情况下将其最大化。具体变换如下（其中f表示被删除结点的父结点，假设target已被删除）：make_biggest(f,f.num,f.dep); 首先使以f为根的子树变为最大add:=1; 表示现有一个

35、多余的结点有待调整时添加repeat s:=f; f:=f.father; 上一层结点f 找到当前子树是其父结点的第i棵子树 fit(f, f.soni, i, add); 将f的第i棵之后的所有子树都变得尽量大，但根据子树排序的要求，它们不得大于子树i add:=0; until f=root;下面再就fit过程给出具体算法：procedure fit(pn:link; 子树需要重新组合的父结点 pm:link; 作为样本的子树的根，也就是它之后的子树均不能大于它 sta:byte; 这棵样本子树是它的父结点的第sta棵子树 add:byte 是否有额外的结点要在重组时添加上去（例如有一个结

36、点被预先删除，则add=1） );var i, now_n, now_d:byte; qn:link;begin 先将排在子树sta之后的子树全部删除，因为它们将被重组，同时计算出被删除的子树的总结点数赋予rest_n，并对它们的父结点pn的有关信息进行相应变动 inc(rest_n , add); sta_n:=pm.num; 样本子树的结点数 tree_n:=rest_n div sta_n; 最多可复制多少棵同样的子树 复制子树 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为根复制子树 end; if (rest_n mod sta_n)<>0 then 还有剩余结点,但不足以复制样本子树 begin now_n:=rest_n mod sta_n; 计算剩余结点 now_d:=pm.dep; if now_n<now_d then now_d:=now_n; 计算剩余结点可以建立的子树的最大深度 建立子树的根 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为根的子树中所有结点的dep和num值end; 对于删除结点后子树深度改变的，则要进行如下的处理（假设s为删除结点target后，向上回溯遇到的第一个子树深度不受影响的结点）： f:=s.father; 找到s为f的第i个子结点 将f的第i个子树后的所有子树删除，改变f的相应值，并将第i个子树后的所有子树的总结点数计算出来，赋给n1 make_biggest(s, n1+s.num ,s.dep); 将所有被删除的结点添加到子树i，并使之在保持原深度的基础上成为

39、最大的子树 f:=s; repeat s:=f; f:=f.father; 上一层结点f 找到当前子树是其父结点的第i棵子树 fit(f,f.soni,i,0); 将f的第i棵之后的所有子树都变得尽量大，但根据子树排序的要求，它们不得大于子树i until f=root; 总的有根树枚举算法大致可以如下构成：读入d,nmake_biggest(root, n, d); 找第一棵树while 未全部生成 do 这步判断可以用计数算法得到的总数来判断,也可以先求得最小的一棵树用来判断 begin search; 删除target; 对树进行变换(包括上面的两种情况: 子树深度改变, 以及深度未改变

40、); end;删除结点，使子树变小将后面的子树重组（最大化）变换完成 虽然上面变换过程看似十分复杂，实质上它是以一种简洁和严谨的规律为基础的。在仔细的研究中，大家可以体会到变换过程的和谐：它和自然数的递减与退位还颇有相似之处。比如说：为了使2000成为比它小，但又与它相差最少的自然数，我们从低位到高位找到它的第一个非0位（也就是可以减小的位）千位2，将它减小1，同时，比它低的各位都须变为最大（9），于是得到1999。再看一个有向树变换的例子（如下图）： 我们先从后向前找到一个待删除结点，删除它之后，然后对其它子树进行了一定的变换（类似于上面把0变成为9的过程），确保了整棵树变小的程度最小，从而

41、得到了序列中的下一棵有向树。 以上介绍的算法可以实现给定深度d，结点数n，按照从大到小的顺序变换生成所有形态的有向树。算法中涉及的树的复制，以及遍历等，复杂度均为O（n），并且在树的生成过程中完全没有重复生成，所以整个算法的耗时主要还与不同形态树的总数有关。 源程序见T_E.Pas (Tree Enumerate)2. 无根树的枚举 解决了有根树的枚举问题，通过中心的定义，可以比较容易地把无根树的枚举问题与之联系起来解决。a) 双中心 找两棵深度相等，结点数之和为n的有根树根根相连即可。假设这两棵树的深度为sub_d1, sub_d2, 结点数为sub_n1, sub_n2, 根结点为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的可能形态未全部生成 do begin 找下一棵B 其实这是有根数枚举算法中的一步

43、将A与B 相连,得到一棵无根树 end; 若A的所有可能形态都已生成,则退出循环 找下一棵A until false; end; end;b) 单中心 与计数算法略不同的是，我们仍然把单中心无根树拆成两棵有根树，树A为中心的一棵深度最大的子树，余下的结点包括中心为树B。树A与树B的关系除了树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; 可能无法构成树 sub_n2:=n-sub_n1; sub_d2:=sub_d1+1; if sub_n2<sub_d2 then break; 可能无法构成树 找最大的A repeat fit(root2, root1, 0, sub_n2-1); 建立第一棵树B，满足树B最大的子树不大于树A 将A与B相连得到一棵无根树 while B的可能形态未全部生成 do begin 找下一棵B 其实这是有根数枚举算法中的一步 将A与B 相连,得到一棵无根树 end; 若A的所有可能形态都已生成,则退出循环 找下一棵A until false; end; end;

45、上述的无根树枚举算法实现了指定结点数的无根树的不重复的直接生成。 值得一提的是，对于无根树的枚举，另一种当前普遍的做法是搜索加判重。这种搜索算法优化后对于小规模问题的效果还是比较理想的。其主要优化措施其实就是利用上文中所提到的排序思想对判重进行优化（也可参见N-Block排序思想的应用）。 我们可以用按照枚举算法编写的生成程序与这种搜索算法作一个比较（测试环境：PIII 500MHz，192Mb RAM，Borland Pascal 7.0，下文同，用时单位：s）：N11121314151617181920构造用时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) 五. 拓展应用与启示1. NOI92 无根树 “无根树”，本身作为一道著名的信息学竞赛题（NOI92），可以使用本文所讨论的算法较为高效地解决。它的问题描述是这样的： 无根树与通常所说的树（有根树）很相似，它包括有结点和枝，但不含有根。无根树结点间只有相邻关系，而不存在父子结点关系。如图1所示，是一棵有7个结点的无根树；以图1的A为根结点得到图2所示的有根树，以图1的B为根结点得到图3所示的有根树，但从无根树角度来看，图1、图2

47、、图3是结构相同的无根树，同时无根树的结构与结点的名称无关。 有根树可以以字符串形式表示，其递归表示方法为：根结点（子树1 子树2 子树3）。 如图2、图3的有根树可以分别表示为A（B（CF（EGD）和B（ACF（EGD），需要注意的是，由于子树的表示顺序可以不同，所以一棵有根树可以有多种表示方法，如图3由字符串可表示为B（F（EGD）CA）或B（ACF（DEG）等。图1ABCDEFG图2ABCDFEG图3ABCDEGF 表示无根树时，可以以它的任一结点为根结点，将其看作有根树从而可以利用有根树的字符串表示形式来表示无根树。 任务1： 由键盘输入一个字符串表示的无根树，无根树的各结点的名称用互

48、不相同的大写英文字母表示。由用户输入一个结点的名称，程序应能够输出一种以该结点为根结点的字符串形式。 程序输出无根树的字符串形式时，各个结点的名称无关紧要，所有结点都以P表示，以后的各种输出也采用这种方式。 例如，用户输入无根树的字符串形式：A（B（CD（EF） 指定的根结点为： D 程序应能输出： P（P（PP）PP） P（PP（PP）P） P（PPP（PP） 任务2： 输入两个串表示的无根树，判断其结构是否一样。注意与结点名称无关，只考虑结构。 任务3： 输入无根树的总枝数M（1M11），输出所有技数为M互不相同的无根树，并记录总数。以字符串形式输出： 例如，M=5时，共有6种不同结构的无

49、根树，如下所示： 注意：各种树结构的字符串表达形式不唯一。 解答 任务一，仍采用链式存储结构，先找到新的根结点，然后可以使用一个递归过程依据原树建立一棵新的树。源程序见Task1.Pas。 任务二，使用对子树排序（排序的规则就象我们在上文中定义的一样）的手段可以避免不断交换子树以得到所有可能表示的复杂过程，从而比较高效地进行同构比较。先将两棵有根树分别进行子树排序，如果所得的有根树不同，那么我们对有根树1进行换根换根的过程其实就是任务一。每次换根以后同样要进行子树排序，然后判断有根树1 的新生树与（已排序的）有根树2是否相同。重复上述过程直到出现两树相同（说明同构）或有根树1的所有结点均已被用作根一次（说明两棵树本质不同）。源程序见Task2.Pas。任务三，对于一棵树来说，总枝数为结点数减1。所以任务三就是一个给定结点数的无根树枚举