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

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

其中expr是可迭代的，可以看作是

 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