Всем возможным двоичным деревьям дан только один обход

Question

Учитывая прохождение только по порядку (или только по / порядку) только двоичного дерева (не обязательно BST), как один код генерирует все возможные двоичные деревья при этом обходе?

Я понимаю, чточисло двоичных деревьев, возможных для данных n узлов, равно (2 ^ n) -n, но если у нас есть доступ к единственному обходу дерева, как мы можем закодировать этот алгоритм?

Answer 1

Делайте это рекурсивно.

def emptyTree():
    return None

def node(l,d,r):
    return (l,d,r)

def singleton(x):
    return (emptyTree(),x,emptyTree())

def allBT(trav,length):
    if length == 0:
        return [emptyTree()]
    if length == 1:
        return [singleton(trav[0])]
    trees = [node(emptyTree(),trav[0],right) for right in allBT(trav[1:],length-1)]
    trees += [node(left,trav[i],right) for i in xrange(1,length-1) for left in allBT(trav[:i],i) for right in allBT(trav[i+1:],length-i-1)]
    trees += [node(left,trav[length-1],emptyTree()) for left in allBT(trav[:length-1],length-1)]
    return trees

def allBinaryTrees(trav):
    return allBT(trav,len(trav))

Кстати, ваше число двоичных деревьев неверно.Существует ровно одно дерево с 0 узлами и одно с 1 узлом, есть два с двумя узлами.Рекурсия равна

T(n) = \sum_{i = 0}^{n-1} T(i)*T(n-i-1)

, поскольку мы можем выбрать каждый элемент в качестве корневого и объединить каждую возможность для узлов i до с каждой возможностью для узлов n-i-1 после.Таким образом T(3) = 5, T(4) = 14, T(5) = 42, T(6) = 132, ...