如何生成所有具有 n 节点和 m 级深度的树?分支因子是可变的，在树本身内不需要是恒定的

Question

我相信这个问题非常简单^

例如，5 节点 3 级算法将消除

A
|
B
|
C
|
D
|
E 

但不是

A
/|
B C D

E

这与(至少对我来说(相同

A
/|
D C B
/
E

例如，3 节点 2 级算法将仅生成以下内容：

(1)               (2)             (3)
A                 B               C
/         or     /        or    /  
B   C             A   C           A   B

请注意，我认为下面的树与上面的 (2( 相同：

B
/ 
C   A

Answer 1

解决方案的基本结构将是递归的，尽管精确的细节会有所不同，具体取决于您为生成假设的精确等价类。在这里，您需要考虑诸如节点是否被标记以及节点的子节点是否有序等问题。这些选择中的每一个都定义了一个非常不同但同样有趣的生成问题。

基本算法是找出可能的子集的枚举，通过为每个等价类仅生成一个规范条目来遵守为特定问题定义的等价类。例如，对于具有有序子项的未标记树，我们可以从枚举节点计数的所有有序分区开始;对于给定的分区，我们将形成指定大小的所有不同可能子树的笛卡尔乘积。如果我们不关心子树的顺序，我们需要找到某种方法来制作子树的规范列表：我们可以首先按总大小对子树进行排序，但随后我们需要两个相同大小的子树的规范顺序。这很棘手，但有解决方案。

我认为您的问题不仅有许多节点，而且具有特定的节点标签，因此具有相同形状但不同标签的两棵树被认为是不同的。但是，您希望子项的顺序与比较无关。所有节点都有唯一标签的事实使问题变得非常容易处理：我们可以枚举可用标签的非空子集，因为我们知道用标签的一个子集生成的树必须都与用不同子集生成的树不同。由于子树本身是无序的，我们可以通过保持子树根的排序来规范化(任何排序都与其他任何排序一样好(。

因此，我们最终得到过程GenTrees(R, D, N)，其中R是根标签，D是后代标签的集合，N是最大树深度，可以定义如下：

• 如果D为空，则返回一个单例集，其中的树仅由指示的根节点组成。

• (为了提高效率(如果N为 1，则返回一个单例集，其中树由指示的根节点组成，其余节点作为叶子。(效率较低的步骤是"如果N为 0，则返回空集"。但最好通过检查N == 1来快捷方式。

• 否则，从一组空的可能树开始，然后

• 对于D的每个非空子集S(这些是根节点的子节点(：

  • 对于每个有序分区PD - S到|S|子集(这些是每个子树的剩余后代(：

    • 将具有根R且子项在GenTrees(Si, Pi, N-1)中的所有树添加到返回集。(这是一个笛卡尔产品。在这里，S的顺序是任意的，但必须是一致的;按升序对标签进行排序将是一个明显的解决方案。

通过对上述内容进行一些测试，我用 Python 编写了一个示例实现。它没有试图提高效率，基本上是使用 python 生成器对上述内容的转录。(生成器的优点是，我们不必用数百万棵可能的树来填充内存;我们一次只生成一棵。

如果它比措辞更清楚，这里是：

from functools import reduce
from itertools import product
class tree(object):
def __init__(self, root, kids=()):
self.root = root
self.kids = tuple(kids)
def __str__(self):
'''Produce an S-expr for the tree.'''
if self.kids:
return "(%s %s)" % (self.root,
' '.join(str(kid) for kid in self.kids))
else:
return self.root
def append(part, wherewhat):
part[wherewhat[0]].append(wherewhat[1])
return part
def gentrees(root, labels, N):
if not labels or N <= 1:
yield tree(root, labels if N else ())
else:
for p in product((0,1), repeat = len(labels)):
if any(p):
nexts, roots = reduce(append, zip(p, labels), ([], []))
for q in product(range(len(roots)), repeat = len(nexts)):
kidsets = reduce(append, zip(q, nexts), tuple([] for i in roots))
yield from (tree(root, kids)
for kids in product(*(gentrees(root, rest, N-1)
for root, rest in zip(roots, kidsets))))    
def alltrees(labels, N):
for i, root in enumerate(labels):
yield from gentrees(root, labels[:i] + labels[i+1:], N)

最后一个函数遍历所有可能的根，并调用每个根的根。下面是一个示例输出，针对三个节点和最大深度 2(此函数计算链接中的深度，而不是节点(：

>>> print('n'.join(map(str,alltrees("ABC",2))))
(A (C B))
(A (B C))
(A B C)
(B (C A))
(B (A C))
(B A C)
(C (B A))
(C (A B))
(C A B)

值得注意的是，生成的树的数量随着节点标签的数量呈指数增长。除非你将自己限制在非常小的树上，否则你应该尽可能尝试修剪生成递归(自上而下或自下而上或两者兼而有之(。