Python, возвращающий список из рекурсивного метода

Question

Я использую двоичное дерево, описанное в этой книге, решение проблем с помощью алгоритмов и структур данных

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

Уже существует метод обхода предварительного заказа, определенный следующим образом.

def preorder(tree):
    if tree:
        print(tree.self.key)
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

Я просто хочу добавить возвращаемое значение в список посещенных узлов. Так что я могу сделать что-то вроде

for i in preorder(tree):
    etc...

У меня проблемы с возвратом списка из рекурсивного метода. Рекурсия останавливается, как только она достигает "возврата", я попробовал варианты, используя

return [tree.self.key] + preorder()

Или же

yield ...

Есть идеи?

Answer 1

Ты уверен что хочешь tree.self.key а не просто tree.key когда вы печатаете?

В противном случае решение с yield from (Python 3.3+):

def preorder(tree):
    if tree:
        yield tree
        yield from preorder(tree.getLeftChild())
        yield from preorder(tree.getRightChild())

Или с простым yield:

def preorder(tree):
    if tree:
        yield tree
        for e in preorder(tree.getLeftChild()):
            yield e
        for e in preorder(tree.getRightChild()):
            yield e

Обратите внимание, что с помощью yield или же yield from превращает функцию в функцию генератора; в частности, если вам нужен фактический список (например, для индексации, нарезки или отображения), вам нужно явно создать его: list(preorder(tree)),

Если у вас разное количество детей, его легко адаптировать:

def preorder(tree):
    if tree:
        yield tree
        for child in tree.children:
            yield from preorder(child)

Answer 2

Вы должны фактически вернуть значение из рекурсивной функции (в настоящее время это просто печать значений). И вы должны построить список по ходу дела, и, возможно, немного очистить код - что-то вроде этого:

def preorder(tree):
    if not tree:
        return []
    # optionally, you can print the key in this line: print(self.key)
    return [tree.key] + preorder(tree.leftChild) + preorder(tree.rightChild)

Answer 3

Вы можете добавить второй аргумент preorder функция, что-то вроде

def preorder(tree, visnodes):
    if tree:
        visnodes.append(tree.self.key)
        print(tree.self.key)
        preorder(tree.getLeftChild(), visnodes)
        preorder(tree.getRightChild(), visnodes)

...
vn = []
preorder(tree, vn)

Answer 4

Вы можете просто вернуть объединенный список для каждого рекурсивного вызова, который объединяет текущий ключ, левое поддерево и правое поддерево:

def preorder(tree):
        if tree:
            return ([tree.key] + preorder(tree.getLeftChild()) +
                    preorder(tree.getRightChild()))
        return []

Для n-арного дерева:

def preorder(tree):
    if tree:
        lst = [tree.key]
        for child in tree.children:
            lst.extend(preorder(child))
        return lst
    return []