枚举所有的全（标记）二叉树 [英] Enumerate all full (labeled) binary tree
问题描述
我在寻找一个实用的算法枚举所有的全标二叉树。
一个满二叉树是树，所有的内部节点都有个度3，树叶已度为1和根都有个度2。
一个标号树是树，所有的叶子具有独特的标签。
例如：
*
| \
| \
* *
/ | | \
/ | | \
T C D F
从评论，很显然，这个问题是列举扎根无序标注全二叉树。正如本文，这些树木与数n 标签是（2N-3）!! ，其中 !! 是的双阶乘功能。
下面蟒程序是基于在所引用的纸张的递归证明;我认为，code是直截了当的，以至于它会通过为算法的说明：
＃一个很简单的重新presentation的节点。叶子是什么，这是不是一个节点。
类节点（对象）：
高清__init __（个体经营，左，右）：
self.left =左
self.right =右
高清__repr __（个体经营）：
回报'（％s％S）'％（self.left，self.right）
＃鉴于一棵树和一个标签，产量树的一切可能增强
＃添加与标签作为一个孩子上面一些现有的节点或叶子一个新的节点。
高清add_leaf（树，标签）：
产量节点（标签，树）
如果isinstance（树节点）：
对于留在add_leaf（tree.left，标签）：
产量节点（左，tree.right）
对于权add_leaf（tree.right，标签）：
产量节点（tree.left，右）
＃鉴于标签的列表，每个产生根深蒂固，无序的满二叉树与树
＃指定的标签。
高清enum_unordered（标签）：
如果len（标签）== 1：
产量标签[0]
其他：
对于树enum_unordered（标签[1：]）：
对于new_tree在add_leaf（树，标签[0]）：
产量new_tree
有关ñ== 4 ，还有（2 * 4 - 3）！ == 5！ == 1 * 3 * 5 = = 15 树：
＆GT;＆GT;＆GT;对于树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））
（一（C（B D）））
（（A C）（B D））
（C（A（B D）））
（C（（A，B）D））
（C（B（A D）））
这个问题的另一个可能的跨pretation是，它试图扎根订购标签的指定表满二叉树的枚举。这种树木的数量n叶由给出ç<子> N-1 ，从加泰罗尼亚数字序列。
高清enum_ordered（标签）：
如果len（标签）== 1：
产量标签[0]
其他：
因为我在范围内（1，LEN（标签））：
对于留在enum_ordered（标签[我]）：
对于权enum_ordered（标签[我：]）：
产量节点（左，右）
有关5的标签，我们有 C <子> 5-1 == 14 ：
＆GT;＆GT;＆GT;对于树enum_ordered（（A，B，C，D，E））：打印树
...
（A（B（C（D E））））
（一（二（（C D）E）））
（一（（B C）（D E）））
（一（（B（C D））E））
（一（（（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）））五）
（（一（（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屋！
