python - 枚举所有完整(标记)的二叉树

我正在寻找一种实用的算法来枚举所有全标记的二叉树。

完整的二叉树是一棵树，其中所有内部节点的度数为3，叶子的度数为1，根的度数为2。

带标签的树是所有叶子都有唯一标签的树。

例子:

    *
    |\
    | \
    *  *
   /|  |\
  / |  | \
 T  C  D  F

最佳答案

从注释中可以明显看出问题是要枚举 Root过的无序标记全二进制树。如this paper中所述，带有n标签的此类树的数量为(2n-3)!!，其中!!是double factorial function。

以下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)))

对这个问题的另一种可能解释是，它试图枚举带有指定标签列表的有序有序全二叉树。从Catalan number sequence中通过C给出具有n个叶子的此类树的数量。

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个标签，我们有C == 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)

关于python - 枚举所有完整(标记)的二叉树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14900693/