Geek asks and answers

List all complete (tagged) binary tree

I am looking for a practical algorithm for listing the entire complete labeled binary tree.

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

A tagged tree is a tree where all leaves have a unique label.

Example:

    *
    |\
    | \
    *  *
   /|  |\
  / |  | \
 T  C  D  F
+5
source share
1 answer

From the comments it can be seen that the question is to list the root unordered labeled full binary trees. As explained in this article , the number of such trees with labels n (2n-3)!!, where !!is the double factorial function .

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

, . 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)
+9

More articles:


All Articles