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

Question

我正在搜索一个实用的算法来枚举所有完整标记的二叉树.

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

带标签的树是一棵树,其中所有叶子都有唯一的标签.

例:

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

Answer 1

从评论中可以清楚地看出,问题是枚举有根无序标记的完整二叉树.正如本文所解释的那样,带有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)