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

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

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()

Or

yield ...

Любые идеи?


python recursion binary-tree preorder
person Damo    schedule 18.04.2015    source источник
comment
Какую ошибку вы получаете? Это что-то о объединении None и списка?   -  person YXD    schedule 18.04.2015
comment
1). Похоже, что preorder() — это вспомогательная функция, а не метод класса BinaryTree, поэтому называть ее методом немного запутанно. 2). Если tree является экземпляром BinaryTree, то tree.self.key неверно. 3). В Python вам редко нужны методы получения (или установки), вы просто получаете доступ к атрибутам напрямую. Например, preorder(tree.leftChild).   -  person PM 2Ring    schedule 18.04.2015

Ответы (4)


arrow_upward
5
arrow_downward

Вы уверены, что хотите 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)
person Francis Colas    schedule 18.04.2015
comment
Поскольку вы напрямую обращаетесь к tree.key, вы также можете использовать preorder(tree.leftChild) и preorder(tree.getRightChild). Кроме того, вы должны упомянуть, что для получения списка узлов таким образом вам нужно будет сделать что-то вроде nodes = list(preorder(tree)) или nodes = [node for node in preorder(tree)]. - person martineau; 18.04.2015
comment
Спасибо за предложение по поводу списка. Что касается другого вашего пункта, я обращаюсь к tree.key, потому что я не хочу гадать, существует ли метод getKey(), но я считаю, что tree.self.key OP может быть ошибочным. Уже было замечание об отсутствии необходимости в геттерах и сеттерах в Python, но здесь это действительно не к делу. - person Francis Colas; 18.04.2015
comment
Я упомянул о том, как создать список, из-за названия вопроса. Также обратите внимание, что это должно быть print tree.key, а не yield tree.key — OP хочет список узлов, а не смесь узлов и ключей. - person martineau; 18.04.2015
comment
Не было узлов, а были только ключи (по индукции: preorder давало только tree.key или то, что preorder давало). Но на самом деле OP, похоже, нужен список узлов, поэтому я отредактировал yield tree. - person Francis Colas; 18.04.2015

arrow_upward
2
arrow_downward

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

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)
person Óscar López    schedule 18.04.2015
comment
Большое спасибо за ответы. Я использую python v3.4, у меня не работает выражение yield, я все еще немного теряюсь между итераторами и генераторами... Во всяком случае, этот "если не дерево возвращает пустой список" устраняет проблему, с которой я столкнулся "может не + NoneType' - person Damo; 18.04.2015

arrow_upward
1
arrow_downward

Вы можете добавить второй аргумент в функцию 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)
person kvorobiev    schedule 18.04.2015

arrow_upward
0
arrow_downward

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

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 []
person Saksham Varma    schedule 18.04.2015
comment
Спасибо за ваш ответ работает отлично. Просто блуждаю, если это не двоичное дерево, как я могу перебрать всех детей, например. def preorder(tree): if tree: return [tree.key] + [preorder(child, msg) для дочернего элемента в tree.children] - person Damo; 19.04.2015
comment
@DamianSavage Да, но использование здесь понимания списка привело бы к списку списков, поскольку каждый вызов preorder возвращает список. Вы можете использовать цикл для достижения этого. Я обновлю свой ответ этим. - person Saksham Varma; 19.04.2015
comment
Вместо явного зацикливания вы можете использовать sum: return sum((preorder(child) for child in tree.children), [tree.key]). - person Francis Colas; 19.04.2015