时间戳

首页 > 解决方案 > 为什么这个简单的递归树遍历算法会失败？

python - 为什么这个简单的递归树遍历算法会失败？

问题描述

我编写了一个递归算法来遍历 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']

为什么会这样？非常感谢

标签： pythontreenestedgeneratortraversal

解决方案

traverse返回一个生成器对象。因此，在traverse调用时，您必须遍历返回的结果并产生每个值或使用语句yield from：

for child in parent: 
   yield from traverse(child)

但是，您当前的解决方案因 a 失败，RecursionError: maximum recursion depth exceeded因为您仅捕获整数值上的迭代发生（引发 a 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']

推荐阅读