从注释中可以明显看出，问题在于枚举有根的无序标记全二进制树。正如上文本文，这些树木的编号为
n标签是
(2n-3)!!这里
!!是双阶乘功能。
以下python程序基于参考文献中的递归证明；我认为代码很简单，因此可以作为算法的解释：
# A very simple representation for Nodes. Leaves are anything which is not a Node.class Node(object): def __init__(self, left, right): self.left = left self.right = right def __repr__(self): return '(%s %s)' % (self.left, self.right)# Given a tree and a label, yields every possible augmentation of the tree by# adding a new node with the label as a child "above" some existing Node or Leaf.def add_leaf(tree, label): yield Node(label, tree) if isinstance(tree, Node): for left in add_leaf(tree.left, label): yield Node(left, tree.right) for right in add_leaf(tree.right, label): yield Node(tree.left, right)# Given a list of labels, yield each rooted, unordered full binary tree with# the specified labels.def enum_unordered(labels): if len(labels) == 1: yield labels[0] else: for tree in enum_unordered(labels[1:]): for new_tree in add_leaf(tree, labels[0]): yield new_tree
对于
n == 4，有
(2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15树：
>>> for tree in enum_unordered(("a","b","c","d")): print tree... (a (b (c d)))((a b) (c d))(b (a (c d)))(b ((a c) d))(b (c (a d)))(a ((b c) d))((a (b c)) d)(((a b) c) d)((b (a c)) d)((b c) (a d))(a (c (b d)))((a c) (b d))(c (a (b d)))(c ((a b) d))(c (b (a d)))对这个问题的另一种可能解释是，它试图枚举带有指定标签列表的有序有序全二叉树。由加泰罗尼亚数列给出的有n片叶子的这种树木的数目。
Cn-1
def enum_ordered(labels): if len(labels) == 1: yield labels[0] else: for i in range(1, len(labels)): for left in enum_ordered(labels[:i]): for right in enum_ordered(labels[i:]): yield Node(left, right)
对于5个标签，我们有：
C5-1 == 14
>>> for tree in enum_ordered(("a","b","c","d", "e")): print tree... (a (b (c (d e))))(a (b ((c d) e)))(a ((b c) (d e)))(a ((b (c d)) e))(a (((b c) d) e))((a b) (c (d e)))((a b) ((c d) e))((a (b c)) (d e))(((a b) c) (d e))((a (b (c d))) e)((a ((b c) d)) e)(((a b) (c d)) e)(((a (b c)) d) e)((((a b) c) d) e)
