Создание всех возможных деревьев глубины N?

Question

У меня есть несколько разных типов узлов дерева, каждый из которых может иметь от 0 до 5 детей. Я пытаюсь вычислить алгоритм генерации всех возможных деревьев глубины < = N. Любая помощь здесь? Мне трудно понять, как рекурсивно ходить по дереву, учитывая, что каждое изменение, которое я делаю для узла, может выставлять новые поддеревья (или удалять старые).

Answer 1

Вы можете создать функцию, содержащую цикл for, который добавляет элементы в многомерный массив и вызывает эту функцию еще раз, пока дерево не будет завершено. Я не могу привести примеры, поскольку я не знаю, какой язык вы предпочитаете.

Answer 2

http://books.google.co.uk/books?id=56LNfE2QGtYC&pg=PA23&lpg=PA23&dq=hansel%27s+algorithm&source=bl&ots=vMbfFj-iZi&sig=E0cI5XhVZ3q1Lg9eAJ_1zYQm53U&hl=en&ei=8udlStuKJ8ehjAfJ1ZSUAQ&sa=X&oi=book_result&ct=result&resnum=1

Answer 3

Вот программа Python Я написал, что я думаю, что делает то, что вы просите. Он вернет все возможные деревья с учетом исходного узла. По сути, это сводится к хитрости с манипуляциями с битами: если у узла есть 5 детей, тогда есть 2 = 32 разных возможных поддеревья, поскольку каждый ребенок может независимо присутствовать или не присутствовать в поддереве.

Код:

#!/usr/bin/env python 

def all_combos(choices): 
    """ 
    Given a list of items (a,b,c,...), generates all possible combinations of 
    items where one item is taken from a, one from b, one from c, and so on. 

    For example, all_combos([[1, 2], ["a", "b", "c"]]) yields: 

     [1, "a"] 
     [1, "b"] 
     [1, "c"] 
     [2, "a"] 
     [2, "b"] 
     [2, "c"] 
    """ 
    if not choices: 
     yield [] 
     return 

    for left_choice in choices[0]: 
     for right_choices in all_combos(choices[1:]): 
      yield [left_choice] + right_choices 

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

    def all_subtrees(self, max_depth): 
     yield Node(self.value) 

     if max_depth > 0: 
      # For each child, get all of its possible sub-trees. 
      child_subtrees = [list(self.children[i].all_subtrees(max_depth - 1)) for i in range(len(self.children))] 

      # Now for the n children iterate through the 2^n possibilities where 
      # each child's subtree is independently present or not present. The 
      # i-th child is present if the i-th bit in "bits" is a 1. 
      for bits in xrange(1, 2 ** len(self.children)): 
       for combos in all_combos([child_subtrees[i] for i in range(len(self.children)) if bits & (1 << i) != 0]): 
        yield Node(self.value, combos) 

    def __str__(self): 
     """ 
     Display the node's value, and then its children in brackets if it has any. 
     """ 
     if self.children: 
      return "%s %s" % (self.value, self.children) 
     else: 
      return str(self.value) 

    def __repr__(self): 
     return str(self) 

tree = Node(1, 
[ 
    Node(2), 
    Node(3, 
    [ 
     Node(4), 
     Node(5), 
     Node(6) 
    ]) 
]) 

for subtree in tree.all_subtrees(2): 
    print subtree 

Вот графическое представление тестового дерева:

 
    1 
/\ 
2 3 
    /|\ 
    4 5 6 

А вот выход из запуска программы:

 
1 
1 [2] 
1 [3] 
1 [3 [4]] 
1 [3 [5]] 
1 [3 [4, 5]] 
1 [3 [6]] 
1 [3 [4, 6]] 
1 [3 [5, 6]] 
1 [3 [4, 5, 6]] 
1 [2, 3] 
1 [2, 3 [4]] 
1 [2, 3 [5]] 
1 [2, 3 [4, 5]] 
1 [2, 3 [6]] 
1 [2, 3 [4, 6]] 
1 [2, 3 [5, 6]] 
1 [2, 3 [4, 5, 6]] 

Если вы хотите Я мог бы перевести это на другой язык. Вы не указали, поэтому я использовал Python; код будет немного более подробным в Java или C++ или что-то еще, поскольку я очень хорошо использовал преимущества Python в списках.

Answer 4

Если единственное различие между типами узлов - это число детей, то генерация каждого возможного дерева только с типом узла с наибольшим количеством детей также будет генерировать каждое возможное дерево для любой комбинации узлов, имеющих равное или меньшее количество детей.

Это своего рода глотком ...

Другими словами, если 5 детей является максимальным, то некоторые из возможных деревьев из всего за 5 дочерних узлов будет иметь узлы, которые имеют, например, два фактических детей и трех нулевых указателей. Это практически то же самое, что и узел с двумя детьми.