我最近一直在研究我的生成器函数和表达式,但我不太确定如何解决这个问题。我如何使用生成器函数来生成然后按顺序打印值?
我使用 python 列表构建了 BST
bst = [20, [10, [5, [2, [], []], [8, [], []]], [15, [], []]], [30, [25, [22, [], []], [27, [], []]], [35, [], [37, [], []]]]]
如果我要打印中序遍历,我没有问题。因此,如果我为以下函数调用 inorder(bst)
:
def inorder(tree):
if tree:
inorder(tree[1])
print (tree[0])
inorder(tree[2])
我得到这个输出。
2
5
8
10
15
20
22
25
27
30
35
37
我认为生成器表达式同样简单
def inorder(tree):
if tree:
inorder(tree[1])
yield (tree[0])
inorder(tree[2])
我遇到的问题是让我的 main 迭代函数中产生的内容。我认为它应该是这样的
test= inorder(bst)
for i in range(0,len(l)): # l is the number of items in bst
print (next(test))
它不是迭代整个函数的结果,而是简单地在迭代开始之前停止它。
20
Traceback (most recent call last):
File "functionGenerator.py", line 64, in <module>
print(next(test))
StopIteration
我需要做什么才能使我的函数发生器正常运行?
最佳答案
您的 inorder()
实现未正确递归。您仅打印树的当前顶部节点。这是因为仅调用 inorder(tree[1])
或 inorder(tree[2])
返回生成器对象,您不会迭代这些生成器。
使用
def inorder(tree):
if tree:
yield from inorder(tree[1])
yield tree[0]
yield from inorder(tree[2])
yield from
expression将生成器委托(delegate)给另一个生成器,从该子生成器生成直到完成。这样你就可以正确地递归。
如果您使用的是较旧的 Python 版本(Python 3.3 之前),则需要手动迭代递归调用:
def inorder(tree):
if tree:
for sub in inorder(tree[1]):
yield sub
yield tree[0]
for sub in inorder(tree[2]):
yield sub
接下来,您可以迭代 inorder()
生成器:
>>> for node in inorder(bst):
... print(node)
...
2
5
8
10
15
20
22
25
27
30
35
37
尽管使用 next()
也可以:
>>> tree = inorder(bst)
>>> print(next(tree))
2
>>> print(next(tree))
5
但是迭代更干净,并且一旦引发 StopIteration
就会自动停止。
关于python - 中序遍历的生成器函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48497230/