枚举所有完整(标记)二叉树 [英] Enumerate all full (labeled) binary tree

问题描述

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

满二叉树是所有内部节点的度数为3，叶子的度数为1，根的度数为2的树.

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

示例:

<代码> *||* */||/||T C D F

解决方案

从评论中可以看出，问题很明显是枚举有根无序标记全二叉树.如这篇论文所述，带有n标签的树的数量是 (2n-3)!! 其中 !! 是 双阶乘函数.

以下python程序基于参考论文中的递归证明；我认为代码很简单，可以作为对算法的解释:

# 一个非常简单的节点表示.叶子是任何不是节点的东西.类节点(对象):def __init__(self, left, right):self.left = 左self.right = 正确def __repr__(self):返回 '​​(%s %s)' % (self.left, self.right)# 给定一棵树和一个标签，通过# 添加一个带有标签的新节点作为高于"一些现有节点或叶的子节点.def add_leaf(树，标签):产量节点(标签，树)如果是实例(树，节点):在 add_leaf(tree.left, label) 中为 left:产量节点(左，树.右)在 add_leaf(tree.right, label) 中的权利:产量节点(树.左，右)# 给定一个标签列表，生成每个有根、无序的全二叉树# 指定的标签.def enum_unordered(标签):如果 len(labels) == 1:产量标签[0]别的:对于 enum_unordered(labels[1:]) 中的树:对于 add_leaf(tree, labels[0]) 中的 new_tree:产生新树

对于n == 4，有(2*4 - 3)！！== 5！！== 1 * 3 * 5 == 15 树:

<预><代码>>>>对于 enum_unordered(("a","b","c","d")) 中的树:打印树...(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):如果 len(labels) == 1:产量标签[0]别的:对于范围内的 i(1, len(labels)):对于 enum_ordered(labels[:i]) 中的 left:对于 enum_ordered(labels[i:]) 中的权利:产量节点(左，右)

对于 5 个标签，我们有 C5-1 == 14:

<预><代码>>>>对于 enum_ordered(("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)((((a b) c) d) e)

I'm searching a practical algorithm for enumerating all full labeled binary tree.

A full binary tree is a tree where all internal nodes has a degree 3, the leaves has degree 1 and the root has a degree 2.

A labeled tree is a tree where all leaves has a unique label.

Example:

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

解决方案

From comments, it is clear that the question is to enumerate rooted unordered labelled full binary trees. As explained in this paper, the number of such trees with n labels is (2n-3)!! where !! is the double factorial function.

The following python program is based on the recursive proof in the referenced paper; I think the code is straight-forward enough that it will pass as an explanation of the algorithm:

# 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

For n == 4, there are (2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15 trees:

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

Another possible interpretation of the question was that it sought an enumeration of rooted ordered full binary trees with a specified list of labels. The number of such trees with n leaves is given by Cn-1, from the Catalan number sequence.

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)

For 5 labels, we have 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)

这篇关于枚举所有完整(标记)二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！