带递归生成器的 BST

Question

我有一个树 class，我向其中添加了一个 in_order 递归方法（似乎运行良好）。因为我想遍历我的 Tree 对象，我想我可以实现 next 下的相同逻辑，但是我得到了一个无限生成器循环。

你能告诉我我错过了什么吗？

class Tree:

    def __init__(self, left=None, right=None, data=None):
        self.data=data
        self.right=right
        self.left=left

    def in_order(self):
        if self.left is not None:
            yield from self.left.in_order()
        yield (self.data)
        if self.right is not None:
            yield from self.right.in_order()

    def __iter__(self):

        return self

    def __next__(self):
        if self.left is not None:
            yield from self.left.__next__()
        yield(self.data)
        if self.right is not None:
            yield from self.right.__next__()



t4 = Tree(data=5)
t6 = Tree(data=32)
t5 = Tree(data=10)
t1 = Tree(data=8, left=t4, right=t5)
t2 = Tree(data=35, left=t6)
t3 = Tree(left=t1, right=t2, data=20)


# Works well
gen = (t3.in_order())
for e in gen:
    print(e)

# Gets into an infinite loop
for e in t3:
    print(e)

Answer 1

class Tree:

    def __init__(self, left=None, right=None, data=None):
        self.data=data
        self.right=right
        self.left=left

    def in_order(self):
        if self.left is not None:
            yield from self.left.in_order()
        yield (self.data)
        if self.right is not None:
            yield from self.right.in_order()

    def __iter__(self):
        if self.left is not None:
            yield from self.left
        yield(self.data)
        if self.right is not None:
            yield from self.right



t4 = Tree(data=5)
t6 = Tree(data=32)
t5 = Tree(data=10)
t1 = Tree(data=8, left=t4, right=t5)
t2 = Tree(data=35, left=t6)
t3 = Tree(left=t1, right=t2, data=20)


# Works well
gen = (t3.in_order())
for e in gen:
    print(e)

# Works well
for e in t3:
    print(e)

将 yield 与 __next__ 一起使用时，您正在进行无限递归，如果将其删除，问题就解决了

test online

Answer 2

评论的扩展版本：

class Tree:
    # can be simplified with @dataclass    
    def __init__(self, left=None, right=None, data=None):
        self.data=data
        self.right=right
        self.left=left

    def __iter__(self):
        if self.left is not None:
            yield from self.left
        yield (self.data)
        if self.right is not None:
            yield from self.right

     in_order = __iter__

测试：

t4 = Tree(data=5)
t6 = Tree(data=32)
t5 = Tree(data=10)
t1 = Tree(data=8, left=t4, right=t5)
t2 = Tree(data=35, left=t6)
t3 = Tree(left=t1, right=t2, data=20)
list(t3)
# returns [5, 8, 10, 20, 32, 35]

带递归生成器的 BST

BST with recursive generator

python

recursion

yield

generator

binary-search-tree