我正在嘗試為我的二叉搜索樹實現(xiàn)迭代器。為了實現(xiàn)這一點，我試圖通過樹進行有序遍歷并產(chǎn)生每個單獨的數(shù)據(jù)成員。這將允許我遍歷樹的每個項目。我的功能：def __iter__(self): """ in-order traversal of a binary search tree """ if self.root is not None: self.check(self.root)def check(self, cur_node): if cur_node is not None: self.check(cur_node.left) yield cur_node.data #if I were to print this data member, it would be fine self.check(cur_node.right)使用迭代測試此函數(shù)時，例如for i in tree:我收到此錯誤：TypeError: iter() returned non-iterator of type 'NoneType'
3 回答
滄海一幻覺
TA貢獻1824條經(jīng)驗 獲得超5個贊
要實現(xiàn)遞歸生成器，您不能只是“調(diào)用”自己，您需要提取元素并生成它們。
Python對此有一個特殊的語法：
yield from expr
whereexpr是可迭代的，它可以看作是
for x in expr:
yield x
使用它，您可以使用以下內(nèi)容實現(xiàn)樹的有序遍歷：
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def __iter__(self):
if self.left:
yield from self.left
yield self.data
if self.right:
yield from self.right
手掌心
TA貢獻1942條經(jīng)驗 獲得超3個贊
您通常希望迭代器作為獨立于數(shù)據(jù)結(jié)構(gòu)的實體，因此您可以在數(shù)據(jù)上使用多個迭代器，因此您可以多次迭代您的數(shù)據(jù)。下面，我將展示如何為基本 BST 類實現(xiàn)簡單的 DFS 算法。
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __iter__(self):
return BSTIterator(self)
class BSTIterator:
def __init__(self, root):
self.stack = []
curr = root
while curr:
self.stack.append(curr)
curr = curr.left
def __next__(self):
if not self.stack:
raise StopIteration()
node = self.stack.pop()
val = node.val
node = node.right
while node:
self.stack.append(node)
node = node.left
return val
def __iter__(self):
return self
root = Node(5, Node(3, Node(1), Node(4)), Node(10, (Node(6, None, Node(7)))))
list(root)
# [1, 3, 4, 5, 6, 7, 10]
九州編程
TA貢獻1785條經(jīng)驗 獲得超4個贊
線索是
iter() 返回 ....
所以你需要返回一個迭代器。你的類是一個迭代器，所以返回 self
def __iter__(self):
"""
in-order traversal of a binary search tree
"""
if self.root is not None:
self.check(self.root)
return self
您可能__next__也應(yīng)該實施以實際產(chǎn)生價值。
所以解決方案可能看起來像
class Tree:
def __init__(...): ...
def __iter__(self):
return self
def __next__(self):
if self.left is not None:
yield from self.left
yield self.data
if self.right is not None:
yield from self.right
您yield from在此處使用委托給子節(jié)點。請參閱https://docs.python.org/3/whatsnew/3.3.html#pep-380-syntax-for-delegating-to-a-subgenerator
實際上，您確實需要三個 yield 語句，因為您需要遍歷左右子節(jié)點，以及生成當前節(jié)點的值。
添加回答
舉報
0/150
提交
取消