У меня есть несколько различных типов узлов дерева, каждый из которых может иметь от 0 до 5 дочерних элементов. Я пытаюсь придумать алгоритм для создания всех возможных деревьев глубины ‹= N. Любая помощь здесь? Мне трудно понять, как рекурсивно пройтись по дереву, учитывая, что каждое изменение, которое я делаю в узле, может открывать новые поддеревья (или удалять старые).
Генерация всех возможных деревьев глубины N?
Ответы (4)
Вот программа Python, которую я написал, и я думаю, что она делает то, что вы просите. Он вернет все возможные деревья с учетом начального узла. По сути, это сводится к трюку с битовыми манипуляциями: если у узла 5 потомков, то существует 25 = 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.
Вы можете создать функцию, содержащую цикл for, который добавляет элементы в многомерный массив и снова вызывает эту функцию, пока дерево не будет завершено. Я не могу привести примеры, так как не знаю, какой язык вы предпочитаете.
Если единственная разница между типами узлов заключается в количестве дочерних элементов, то генерация всех возможных деревьев только с типом узла с наибольшим количеством дочерних элементов также будет генерировать все возможные деревья для любой комбинации узлов, имеющих равное или меньшее количество дочерних элементов.
Это какой-то глоток...
Иными словами, если 5 дочерних элементов — это максимум, то некоторые из возможных деревьев, состоящих только из 5 дочерних узлов, будут иметь узлы, которые имеют, например, двух фактических дочерних элементов и три нулевых указателя. Это практически то же самое, что иметь узел только с двумя потомками.
O(2^n)
). Это невозможно даже для относительно небольшого N. - person mmx   schedule 29.10.2009