《江苏省李源》由会员分享，可在线阅读，更多相关《江苏省李源（21页珍藏版）》请在金锄头文库上搜索。
1、江苏省常州高级中学 李源n树，在计算机算法中是非常重要的非线形结构。即使 撇开树的其他广泛应用不说，单单对树本身的形态进 行思考与研究，也是一个十分有趣，且具有挑战性的 过程。引子引子4个结点的树（有向树）n常规的搜索加判重的做法：枚举算法枚举算法生成枚举同构状态与已有的解相比较添加n下面我们就来看一种不重复地生成所有确定结点数和深 度的有向树的构造性算法。n n不重复性：树的大小定义不重复性：树的大小定义n n不遗漏性：树的变换算法不遗漏性：树的变换算法树的大小定义树的大小定义n我们对树的“大小”作一个规定，使不同树结构之间的关系 有序化。n假设当前要比较树A与树B的大小（树A与树B的子树也
2、都要按照下述的大 小关系递归地从大到小排序）。比较过程为：若A的深度大于B，则AB；若A的深度小于B，则AB；若A的结点数小于B，则AB；若A与B的结点数相等，依次讨论A与B的子树：拥有较大子树的树较大。若当前讨论的子树相等，则讨论A与B 的下一棵子树。n现在回到枚举有向树的问题上来：对于深度为d，结点数为n 的所有形态的有向树，根据上面的比较规则，可以把它们从 大到小排成一个序列。举d=3，n=6为例，这个序列是：n进一步地，对于任意的n和d ，在相应序列中的第一棵 树和最后一棵树的形态是容易确定的，如下：n现在问题就转化为，根据上述的大小 定义，能否找到一种变换的规则，使 根据这种规则，可
3、以从最小的一棵树 开始，连续地、不遗漏不重复地生成 接下来的所有不同形态的树？n首先，从树的序列中的一个形态变换到另一个形态 ，是一个变小的过程。n在这个变换过程中，至少有一棵子树被变小了，变 小的过程是通过夺走它的一个子结点实现的（我们 用一个虚线框来表示被变小的子树）。变换过程变换过程n它们会适当地变大，然而由于它们在有向树大小比较的过 程中的地位比先前被变小的那棵子树要低，于是，总的说 来，整个有向树就被变小了。n结点被夺去 ；n排在它后面的某些子 树将会得到这个被夺 走的结点，或被重新 组合。 过程过程I I寻找被删去结点寻找被删去结点 过程过程II II将被删的结点重组到后面的子树中
4、将被删的结点重组到后面的子树中过程过程I I 寻找被删去结点寻找被删去结点n在选择被删去的结点时，其所在子树的变小对于整棵树的 影响必须尽量小。使它经过变换后恰好可以成为序列中紧 邻它的一棵树而不是跳跃性的变换。所以：n首先，这个被夺取的结点必然为叶结点。n第二，对于并列的若干子树，应当从后向前查找。过程过程I I 算法算法n从根出发，在子结点中从后向前找到 第一个非叶结点的结点，继续搜索直 到到达一个子结点均为叶子的结点为 止。是否可认为该结点的最后一个子结点为待删除结点呢？事 实上仍需进一步处理：假如，找到的待删除结点A为其父亲B唯一的子结点，也 就意味着如果将A从它的父结点B删除，那么以
5、B为根的那棵 子树的深度将会减少1n在对树的大小定义中，深度比结点数更优先。所以，在选择待删 除结点时，应该尽量选择删除后不影响子树深度的结点优先处理 。n因此，在找到A结点后，必须沿其父亲结点进行回溯，直到当前结 点以下的子树的深度不因删除A而改变为止（在上图中直到D结点 ），在回溯的过程中，如果经过某一结点，它还有另一个子结点 （比如上图中的C，它还有另一个子结点E），那么就舍弃原来找 到的结点A，把E定为待删除的结点。过程过程I I 算法算法如果将A从B断开，则以B、 C为根的子树的深度都会受 到影响。C有子结点E， ETarget回溯找到A， ATarget过程过程II II 将被删的
6、结点重组到后面的子树中将被删的结点重组到后面的子树中n在找到该结点并删除之后，又需要进行一系列的处理以形成 一棵新的树。在建立新树的时候要强调的一点就是，“要使整 棵树变小，但变小的幅度必须达到最小”。删除一个结点之后，会出现两种情况：n当前子树深度不变，结点数变小；n或者子树深度变小。下面就对这两种情况分别进行讨论。过程过程II II 算法算法 删除结点后子树深度不变删除结点后子树深度不变n接下来，对排列在被改动的这棵子树以后的其它子树 进行重新组合，使它们在满足不大于当前这棵子树的 情况下变得最大（同时将被删除的那个结点加入）。删除结点，使子树 变小将后面的子树重 组（最大化）变换完成过程
7、过程II II 算法算法 删除结点后子树深度变小删除结点后子树深度变小n对于删除结点后子树深度改变的，则要进行如下的处理（举例来 说）：F：要从父亲处删 除的结点。C E： 深度将会 变小。要进一步 处理。将F删去，处理E极 其兄弟（此处为空 ），连同删去的F ，以C为根进行重 组。处理C极其兄弟（D ），连同C以下的所 有子树，以C的父亲 B为根进行重组。得 到新的树。n完整的有根树枚举算法大致可以如下构成：1 读入读入d,nd,n 2 找第一棵树（最大的）找第一棵树（最大的） 3 while while 未全部生成未全部生成 dodo 这步判断可以用计数算法得到的总数来判断,也可以先求 得
8、最小的一棵树用来判断 4 找到待删除的结点找到待删除的结点target;target; 5 删除删除target;target; 6 对树进行变换对树进行变换; ; 包括上面的两种情况: 子树深度 改变, 以及深度未改变 7 end of whileend of while小结小结n虽然上面变换过程看似十分复杂，实质上它是以一种 简洁和严谨的规律为基础的。n在仔细的研究中，大家可以体会到变换过程的和谐： 它和自然数的递减与退位还颇有相似之处。比如说：为了使2000成为比它小，但又与它相差 最少的自然数：200019991000n类似地, 再看一个有向树变换的例子:删除结点，使子树 变小将后面的
9、子树重 组（最大化）变换完成n我们先从后向前找到一个待删除结点，删除它之后， 然后对其它子树进行了一定的变换（类似于上面把0 变成为9的过程），确保了整棵树变小的程度最小， 从而得到了序列中的下一棵有向树。n以上介绍的算法可以实现给定深度d，结点数n，按照从大到小的顺序变换生成所有形态的有向树。算法中涉及的树的复制，以及遍历等，复杂度均为O（n），并且在树的生成过程中完全没有重复生成，所以整个算法的耗时主要与不同形态树的总数有关。n该算法最直接的应用是“无根树”问题。下表可以 作为算法时间复杂度的直观参考。我们可以用按照枚举算法编写的生成程序与搜索算法作一个 比较（测试环境：PIII 500MHz，192Mb RAM，Borland Pascal 7.0，用时单位：s）：
