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

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 expr

whereexpr是可迭代的，它可以看作是

 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 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]

Answer 3

线索是

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__也应该实施以实际产生价值。

所以解决方案可能看起来像

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 语句，因为您需要遍历左右子节点，以及生成当前节点的值。