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