Почему этот простой рекурсивный алгоритм обхода дерева терпит неудачу? - PullRequest
Новая
       28

Почему этот простой рекурсивный алгоритм обхода дерева терпит неудачу?

0 голосов
/ 13 января 2019

Я написал рекурсивный алгоритм для обхода вложенных итераторов в Python. Я не понимаю, почему он успешно распечатывает элементы, но не дает их в качестве генератора.

Пока мне удалось распечатать элементы: 

tree = [[1,2],[3,[['abcde',['f']],'gh']]]

def traverse_printing(parent): 
     try: 
         for child in parent: 
              traverse(child) 
     except TypeError: 
         print(parent) 

>>> traverse_printing(tree)                                                                                                                                                                                    
1
2
3
a
b
c
...

Я изо всех сил пытаюсь превратить его в генератор. 

def traverse(parent): 
     try: 
         for child in parent: 
              traverse(child) 
     except TypeError: 
         yield parent

traverse(tree) в настоящее время не работает. Результат: 

>>> list(traverse(tree))                                                                                                                                                                              
[]

Ожидаемый результат будет [1,2,3,'a','b','c','d','e','f','g','h']

Почему это так? Большое спасибо

1 Ответ

0 голосов
/ 13 января 2019

traverse возвращает объект генератора. Таким образом, при вызове traverse вы должны перебрать возвращаемый результат и получить каждое значение или использовать оператор yield from: 

for child in parent: 
   yield from traverse(child)

Однако ваше текущее решение завершается с ошибкой RecursionError: maximum recursion depth exceeded, потому что вы только перехватываете повторение по целочисленному значению (которое вызывает TypeError). Цикл над строкой является допустимой операцией в Python, следовательно, бесконечные рекурсивные вызовы. Таким образом вам нужно будет проверить фактические типы parent: 

def traverse(parent): 
  if isinstance(parent, str):
     yield from parent
  elif isinstance(parent, int):
     yield parent
  else: 
     for child in parent: 
        yield from traverse(child) 

list(traverse(tree))

Выход: 

[1, 2, 3, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
...