print_trees.py

class Node():
    def __init__(self, children):
        self.children = children

    def __repr__(self):
        return 'Node(%s)' % repr(self.children)

    def extents(self):
        n = len(self.children)
        if n == 0:
            return (0, 0)
        if n == 1:
            return self.children[0].extents()
        ex0 = self.children[0].extents()
        ex1 = self.children[1].extents()
        return (ex0[0] + ex1[0] + 1,
                ex1[1] + ex0[1] + 1)

    def depth(self):
        n = len(self.children)
        if n == 0:
            return 1
        if n == 1:
            return 2 + self.children[0].depth()
        return 4 + max(self.children[0].depth(),
                       self.children[1].depth())

    def position(self, pos):
        self.pos = pos
        n = len(self.children)
        if n == 0:
            return
        if n == 1:
            self.children[0].position(pos)
            return
        self.children[0].position(pos - self.children[1].extents()[0] - 1)
        self.children[1].position(pos + self.children[0].extents()[1] + 1)

    def print(self, arr, depth=0):
        arr[self.pos][depth] = 'o'

        n = len(self.children)
        if n == 0:
            return
        if n == 1:
            arr[self.pos][depth+1] = '-'
            self.children[0].print(arr, depth+2)
            return
        arr[self.pos][depth+1] = '-'
        arr[self.pos][depth+2] = '+'
        for i in range(self.children[0].pos + 1, self.pos):
            arr[i][depth+2] = '|'
        arr[self.children[0].pos][depth+2] = '+'
        arr[self.children[0].pos][depth+3] = '-'
        self.children[0].print(arr, depth+4)
        for i in range(self.pos+1, self.children[1].pos):
            arr[i][depth+2] = '|'
        arr[self.children[1].pos][depth+2] = '+'
        arr[self.children[1].pos][depth+3] = '-'
        self.children[1].print(arr, depth+4)

def generate_trees(i):
    if i <= 1:
        yield Node([])
        return

    for child in generate_trees(i - 1):
        yield Node([child])

    for child1_size in range(1, i - 1):
        for child1 in generate_trees(child1_size):
            child2_size = i - 1 - child1_size
            for child2 in generate_trees(child2_size):
                yield Node([child1, child2])

def print_tree(tree, indent):
    tree.position(tree.extents()[0])
    extents = tree.extents()
    depth = tree.depth() + indent
    arr = []
    for i in range(-extents[0] - 1, extents[1]):
        arr.append([' '] * depth)
    tree.print(arr, indent)
    return [''.join(line) for line in arr]


def print_trees(i):
    trees = enumerate(generate_trees(i))
    while True:
        try:
            i,tree1 = next(trees)
        except StopIteration:
            return
        try:
            j,tree2 = next(trees)
        except StopIteration:
            arr1 = print_tree(tree1, 3)
            print("tree %i:" % (i + 1))
            for line in arr1:
                print(line)
            print()
            return

        arr1 = print_tree(tree1, 3)
        arr2 = print_tree(tree2, 3)
        ex1 = tree1.extents()[0]
        ex2 = tree2.extents()[0]
        for i in range(ex1, ex2):
            arr1.insert(0, '')
        for i in range(ex2, ex1):
            arr2.insert(0, '')
        for i in range(len(arr1), len(arr2)):
            arr1.append('')
        for i in range(len(arr2), len(arr1)):
            arr2.append('')
        arr1.insert(0, "tree %i:" % (j))
        arr2.insert(0, "tree %i:" % (j + 1))
        for line1, line2 in zip(arr1, arr2):
            print("%-25s%s" % (line1, line2))
        print()

import sys
print_trees(int(sys.argv[1]))