在二叉搜索树中产生数据成员

Question

我正在尝试为我的二叉搜索树实现迭代器。为了实现这一点，我试图通过树进行有序遍历并产生每个单独的数据成员。这将允许我遍历树的每个项目。

我的功能：

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)

使用迭代测试此函数时，例如

for i in tree:

我收到此错误：

TypeError: iter() returned non-iterator of type 'NoneType'

Answer 1

要实现递归生成器，您不能只是“调用”自己，您需要提取元素并生成它们。Python对此有一个特殊的语法： yield from exprwhereexpr是可迭代的，它可以看作是 for x in expr:     yield x使用它，您可以使用以下内容实现树的有序遍历：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

Answer 2

您通常希望迭代器作为独立于数据结构的实体，因此您可以在数据上使用多个迭代器，因此您可以多次迭代您的数据。下面，我将展示如何为基本 BST 类实现简单的 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 selfroot = Node(5, Node(3, Node(1), Node(4)), Node(10, (Node(6, None, Node(7)))))list(root)# [1, 3, 4, 5, 6, 7, 10]

Answer 3

线索是iter() 返回 ....所以你需要返回一个迭代器。你的类是一个迭代器，所以返回 selfdef __iter__(self):    """    in-order traversal of a binary search tree    """    if self.root is not None:        self.check(self.root)    return self您可能__next__也应该实施以实际产生价值。所以解决方案可能看起来像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在此处使用委托给子节点。请参阅https://docs.python.org/3/whatsnew/3.3.html#pep-380-syntax-for-delegating-to-a-subgenerator实际上，您确实需要三个 yield 语句，因为您需要遍历左右子节点，以及生成当前节点的值。