рекурсивная функция python возвращает узлы без потомков в дереве - PullRequest
Новая
       22

рекурсивная функция python возвращает узлы без потомков в дереве

0 голосов
/ 21 мая 2018 
     0
   /   \
  1     2
 / \   /|\
3   4 5 6 7

Я пытаюсь вернуть узлы без дочерних элементов (3,4,5,6,7) из объекта с помощью рекурсивной функции.

Работает с использованием глобальной переменной и этой функции: 

def find(self, nodes):
    if not hasattr(self, 'children'): 
        nodes.append(self)
    else:
        for i in self.children:
            i.find(nodes)


nodes = []
node.find(nodes) # can be any node (0,1,2,3,4, etc.)
print(nodes)

Но я бы хотел использовать return в моей функции.Я пробовал что-то вроде этого: 

   def find2(self):
    if not hasattr(self, 'children'): 
        return self
    else:
        for i in self.children:
            return i.find2()


nodes = root.find2()
print(nodes)

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

Я застрял, вы можете мне помочь?Как «вернуть результат для каждой итерации рекурсивной функции в переменную»?Спасибо

Ответы [ 3 ]

0 голосов
/ 21 мая 2018

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

def find(self):
    if not hasattr(self, 'children'):
        return [self]

    nodes = []

    for child in self.children:
        return nodes.extend(child.find())

    return nodes

# ...

nodes = root.find()
print(nodes)
0 голосов
/ 21 мая 2018

Это пример ввода: 

     0
   /   \
  1     2
 / \   /|\
3   4 5 6 7

Подумайте, что вы хотите, чтобы (рекурсивная) функция возвращала для каждого из узлов:

  • при вызове в корне(0), он должен возвращать полный результат (3, 4, 5, 6, 7)
  • при вызове на листовом узле (например, 5), он должен возвращать этот узел (5)
  • для любого другого узла (например, 1), он делает так, как если бы это был корневой узел меньшего дерева

Итак, иногда он возвращает один результат, а иногда и много.Ошибка в вашем коде здесь, потому что функция заканчивается при первом возврате, она не возвращает много: 

    for i in self.children:
        return i.find2()

Есть два решения:

  • сделать функцию генератораили
  • сделать функцию, которая возвращает список (сделать так, чтобы он возвращал список всегда, даже если в нем только один элемент!)

Итак, вариант 1: 

def find(self):
    if not hasattr(self, 'children'): 
        yield self
    else:
        for child in self.children:
            yield from child.find()

вариант 2: 

def find(self):
    if not hasattr(self, 'children'): 
        return [self]
    else:
        rtn = []
        for child in self.children:
            for result in child.find():
                rtn.append(result)
        return rtn

Я предпочитаю генератор.Кроме того, мне не особенно нравится тот факт, что некоторые из ваших узлов имеют атрибут children, а другие нет.Я бы удостоверился, что у всех них было children, которое могло быть пустым или непустым.Затем код становится: 

def find_leaves(self):
    if self.children:
        for child in self.children:
            yield from child.find_leaves()
    else:
        yield self
0 голосов
/ 21 мая 2018

Обратите внимание, что в вашем базовом случае вы возвращаете один узел.Затем этот узел передается обратно в рекурсии и в конечном итоге возвращается.Т.е. вернувшийся вами узел - первый, без дочерних узлов.Есть несколько способов исправить эту проблему (например, возвращая и объединяя списки), но я думаю, что естественный способ сделать это - сделать вашу функцию генератором.Для этого просто замените return на yield.Затем возвращаемое значение функции функционирует как итератор, причем каждая итерация дает следующее значение, которое будет «возвращено» при выполнении до завершения функции.

...