Рекурсивное дерево Python
Я новичок в программировании и хочу определить функцию, которая позволяет мне находить элемент в недвоичном дереве и отслеживать все родительские элементы этого элемента в списке. Дерево закодировано как кортеж, где индекс 0 — это родительский элемент, а индекс 1 — список его дочерних элементов. Список содержит кортеж для каждого дочернего элемента, составленный так же, как и раньше (индекс 0 — родительский, а индекс 1 — дочерний).
Пример:
tree_data = (
'Alan', [
(
'Bob', [
('Chris', []),
(
'Debbie', [
('Cindy', [])
]
)
]
),
(
'Eric', [
('Dan', []),
(
'Fanny', [
('George', [])
]
)
]
),
('Hannah', [])
]
)
Поиск «Джорджа» вернет следующее: ['George', 'Eric'. 'Alan']
Пока у меня есть следующее: мне удалось добавить только элемент и прямой родитель, но не дальше.
Также, если я добавлю оператор return в функцию, результат будет None. Был бы признателен за небольшую помощь.
lst = []
def list_parentals(tree, element):
if tree[0] == element:
lst.append(element)
else:
for child in tree[1]:
list_parentals(child, element)
if child[0] == element:
lst.append(tree[0])
На первый взгляд, возвращайте True всякий раз, когда вы добавляете значение в список. Вы делаете это, когда tree[0] == element или когда рекурсивная функция возвращает True.
Ответы 2
Вместо того, чтобы вести список извне, вы можете создавать его по ходу дела.
def list_parentals(tree, element, parents):
this, children = tree
new_parents = [this] + parents
if this == element:
return new_parents
else:
for child in children:
x = list_parentals(child, element, new_parents)
# If x is not None, return it
if x:
return x
list_parentals(t, 'George', [])
# ['George', 'Fanny', 'Eric', 'Alan']
Поскольку «моя рекурсивная функция возвращает None», это очень, очень классическая проблема. Вы найдете сотни подробных ответов об этом на SO, ища эти слова.
Короче говоря, рекурсивная функция должна всегда что-то возвращать, а не только тогда, когда она что-то находит. Как правило, в таком примере вы должны вернуть результат, когда нашли правильный лист. Но если вы не хотите, чтобы этот результат был потерян, вы также должны что-то вернуть, когда вы вызываете ту рекурсию, которая нашла лист. И когда вы вызываете ту рекурсию, которая вызвала ту рекурсию, которая нашла лист.
Имейте в виду, что в конечном результате вы получите возвращаемое значение первого вызова list_parentals. Если этот первый вызов ничего не возвращает, то не имеет значения, что некоторые рекурсивные подвызовы сделали это.
Во-вторых, способ построить такой путь как раз и состоит в том, чтобы воспользоваться преимуществами рекурсии. Попытка создать список в глобальной переменной, когда вы найдете соответствующий лист, непроста. И вы можете в конечном итоге попытаться вычислить это с помощью итеративного алгоритма, когда весь смысл рекурсии состоит в том, чтобы сделать это за вас.
Вот рабочий рекурсивный метод (я старался максимально приблизить его к вашему собственному коду)
tree=('Alan', [('Bob', [('Chris', []), ('Debbie', [('Cindy', [])])]), ('Eric', [('Dan', []), ('Fanny', [('George', [])])]), ('Hannah', [])])
def list_parentals(tree, element):
if tree[0] == element:
return [element]
else:
for child in tree[1]:
sub=list_parentals(child, element)
if sub:
return [tree[0]] + sub
return []
r=list_parentals(tree, 'George')
print(f"{r=}")
Логика этого заключается в том, что list_parental(tree, 'George') возвращает путь в дереве к листу «Джордж» или [] (или None, или False, не имеет значения), если такой лист не найден.
Итак (просто думайте об этом как о математическом выражении, а не как о коде, пока), list_parental(('Alan', [('Bob', [('Chris', []), ('Debbie', [('Cindy', [])])]), ('Eric', [('Dan', []), ('Fanny', [('George', [])])]), ('Hannah', [])]), 'George') это просто Alan плюс `list_parental(('Эрик', [('Дэн', []), ('Фанни', [(' Георгий', [])])]), 'Георгий').
``list_parental(('Эрик', [('Дэн', []), ('Фанни', [('Джордж', [])])]), 'Джордж')is justЭрикpluslist_parental(('Фанни ', [('Джордж', [])]), 'Джордж')`.
list_parental(('Fanny', [('George', [])]), 'George') это просто Fanny плюс list_parental(('George', []), 'George').
list_parental(('George', []), 'George') это просто George.
Чтобы сохранить эту согласованность, все возвращаемые значения должны быть списками.
Отсюда мой код.
list_parental(tree, leafName) — это [leafName] корень дерева соответствия leafName.
Еще
list_parental(tree, leafName) является [tree[0]] + list_parental(child, leafName), если один из дочерних элементов содержит leafName, то есть если list_parental(child, leafName) не пуст.
Ты никогда не меняешься
element. Какое бы значение оно ни имело при первом вызове, оно всегда передается в качестве аргумента рекурсивному вызову, поэтому к результату может быть добавлено только одно имя.