列举所有的满（有标签）二叉树

Question

列举所有的满（有标签）二叉树

pythonalgorithmdata-structurescatalan

6

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

完整的二叉树指的是每个内部节点都有3个度数，叶子节点具有1个度数，根节点具有2个度数。

标记树是指每个叶子节点都具有唯一标签的树。

例如：

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

- Giggi

你难道不是在寻找一种树遍历算法吗？http://en.wikipedia.org/wiki/Tree_traversal - domino

每个叶子的深度都相同吗？ - us2012

@domino 遍历只枚举单棵树的节点，而不是一组树。 - us2012

你想只打印叶子节点吗？你能给出该树的输出示例吗？ - pcalcao

树的深度是可变的，而叶子节点的数量是已知的。 - Giggi

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

从评论中可以清楚地看出，问题是要枚举有根无序标记完全二叉树。如这篇论文所解释的那样，带有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个叶子树的数量由 C_n-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个标签，我们有C_5-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)