算法合集之《树的枚举》

《算法合集之《树的枚举》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、江苏省常州高级中学李源树的枚举树，在计算机算法中是非常重要的非线形结构。即使撇开树的其他广泛应用不说，单单对树本身的形态进行思考与研究，也是一个十分有趣，且具有挑战性的过程引子4个结点的树（有向树）常规的搜索加判重的做法：枚举算法生成枚举同构状态与已有的解相比较添加下面我们就来看一种不重复地生成所有确定结点数和深度的有向树的构造性算法。不重复性：树的大小定义不遗漏性：树的变换算法树的大小定义我们对树的“大小”作一个规定，使不同树结构之间的关系有序化。假设当前要比较树A与树B的大小（树A与树B的子树也都要按照下述的大小关系递归地从大到小排序）

2、。比较过程为：若A的深度大于B，则A>B；若A的深度小于B，则AB；若A的结点数小于B，则A

3、根据上述的大小定义，能否找到一种变换的规则，使根据这种规则，可以从最小的一棵树开始，连续地、不遗漏不重复地生成接下来的所有不同形态的树？首先，从树的序列中的一个形态变换到另一个形态，是一个变小的过程。在这个变换过程中，至少有一棵子树被变小了，变小的过程是通过夺走它的一个子结点实现的（我们用一个虚线框来表示被变小的子树）。变换过程它们会适当地变大，然而由于它们在有向树大小比较的过程中的地位比先前被变小的那棵子树要低，于是，总的说来，整个有向树就被变小了。结点被夺去；排在它后面的某些子树将会得到这个被夺走的结点，或被重新组合。过程I寻找被删去结

4、点过程II将被删的结点重组到后面的子树中过程I寻找被删去结点在选择被删去的结点时，其所在子树的变小对于整棵树的影响必须尽量小。使它经过变换后恰好可以成为序列中紧邻它的一棵树而不是跳跃性的变换。所以：首先，这个被夺取的结点必然为叶结点。第二，对于并列的若干子树，应当从后向前查找。过程I算法从根出发，在子结点中从后向前找到第一个非叶结点的结点，继续搜索直到到达一个子结点均为叶子的结点为止。是否可认为该结点的最后一个子结点为待删除结点呢？事实上仍需进一步处理：假如，找到的待删除结点A为其父亲B唯一的子结点，也就意味着如果将A从它的父结点B删除，那

5、么以B为根的那棵子树的深度将会减少1……在对树的大小定义中，深度比结点数更优先。所以，在选择待删除结点时，应该尽量选择删除后不影响子树深度的结点优先处理。因此，在找到A结点后，必须沿其父亲结点进行回溯，直到当前结点以下的子树的深度不因删除A而改变为止（在上图中直到D结点），在回溯的过程中，如果经过某一结点，它还有另一个子结点（比如上图中的C，它还有另一个子结点E），那么就舍弃原来找到的结点A，把E定为待删除的结点。过程I算法如果将A从B断开，则以B、C为根的子树的深度都会受到影响。C有子结点E，E→Target回溯找到A，A→Target过

6、程II将被删的结点重组到后面的子树中在找到该结点并删除之后，又需要进行一系列的处理以形成一棵新的树。在建立新树的时候要强调的一点就是，“要使整棵树变小，但变小的幅度必须达到最小”。删除一个结点之后，会出现两种情况：当前子树深度不变，结点数变小；或者子树深度变小。下面就对这两种情况分别进行讨论。过程II算法删除结点后子树深度不变接下来，对排列在被改动的这棵子树以后的其它子树进行重新组合，使它们在满足不大于当前这棵子树的情况下变得最大（同时将被删除的那个结点加入）。删除结点，使子树变小将后面的子树重组（最大化）变换完成过程II算法删除结点后子树

7、深度变小对于删除结点后子树深度改变的，则要进行如下的处理（举例来说）：F：要从父亲处删除的结点。CE：深度将会变小。要进一步处理。将F删去，处理E极其兄弟（此处为空），连同删去的F，以C为根进行重组。处理C极其兄弟（D），连同C以下的所有子树，以C的父亲B为根进行重组。得到新的树。完整的有根树枚举算法大致可以如下构成：1读入d,n2找第一棵树（最大的）3while未全部生成do{这步判断可以用计数算法得到的总数来判断,也可以先求得最小的一棵树用来判断}4找到待删除的结点target;5删除target;6对树进行变换;{包括上面的两种情况:

8、子树深度改变,以及深度未改变}7endofwhile小结虽然上面变换过程看似十分复杂，实质上它是以一种简洁和严谨的规律为基础的。在仔细的研究中，大家可以体会到变换过程的和谐：它和