Enumerar todo el árbol binario completo (etiquetado)

Estoy buscando un algoritmo práctico para enumerar todos los árboles binarios etiquetados completos.

Un árbol binario completo es un árbol donde todos los nodos internos tienen un grado 3, las hojas tienen un grado 1 y la raíz tiene un grado 2.

Un árbol etiquetado es un árbol donde todas las hojas tienen una etiqueta única.

Ejemplo:

* |\ | \ * * /| |\ / | | \ TCDF 

A partir de los comentarios, queda claro que la pregunta es enumerar árboles binarios completos etiquetados desordenados desarraigados. ¡Como se explica en este documento , el número de tales árboles con n tags es (2n-3)!! donde !! Es la doble función factorial .

El siguiente progtwig de Python se basa en la prueba recursiva en el documento al que se hace referencia; Creo que el código es lo suficientemente directo como para que pase como una explicación del algoritmo:

 # 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 

Para n == 4 , hay (2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15 (2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15 (2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15 árboles:

 >>> for tree in enum_unordered(("a","b","c","d")): print tree ... (a (b (cd))) ((ab) (cd)) (b (a (cd))) (b ((ac) d)) (b (c (ad))) (a ((bc) d)) ((a (bc)) d) (((ab) c) d) ((b (ac)) d) ((bc) (ad)) (a (c (bd))) ((ac) (bd)) (c (a (bd))) (c ((ab) d)) (c (b (ad))) 

Otra posible interpretación de la pregunta fue que buscó una enumeración de árboles binarios completos ordenados y enraizados con una lista específica de tags. El número de tales árboles con n hojas viene dado por C n-1 , de la secuencia numérica catalana .

 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) 

Para 5 tags, tenemos C 5-1 == 14 :

 >>> for tree in enum_ordered(("a","b","c","d", "e")): print tree ... (a (b (c (de)))) (a (b ((cd) e))) (a ((bc) (de))) (a ((b (cd)) e)) (a (((bc) d) e)) ((ab) (c (de))) ((ab) ((cd) e)) ((a (bc)) (de)) (((ab) c) (de)) ((a (b (cd))) e) ((a ((bc) d)) e) (((ab) (cd)) e) (((a (bc)) d) e) ((((ab) c) d) e)