如何使 class 可迭代，但如果修改 class 则迭代器不会被修改？

Question

我是 python 和一般编码的新手，所以我很迷茫。我编写了一个 "Node" class（如下图底部所示），它实例化了一个二叉搜索树和一些方法，如 insert() 和 elements()（其中 returns按顺序遍历树的元素列表）。我应该使这个 class 可迭代："iter__(self) should return a NodeIterator, which returns elements from the tree in sorted order. Modifying the tree should not modify existing iterators." 我正在尝试通过立即将此代码插入 class 来做到这一点：

 def __iter__(self):
    x=self.copy()
    x.i=0
    return x

def next(self):
    lst=x.elements()
    #??? No idea what to do from here.

我定义了 x=self.copy() 来试图掩盖修改树不应该修改迭代器的事实，但我不知道这是否是正确的想法。这是我的节点 class，其中一个方法中使用了装饰器：

def depth(old_f):
''' Write a decorator that overrides the standard behavior of
a function that returns True or False and instead returns
0 for False or n for number of recursive calls needed to
return True.
'''
    def new_f(*args):
        res = old_f(*args)
        if res is True:
            return 1
        elif res:
            return 1 + res
        else:
            return 0
    return new_f


Class Node(object):
'''
Modify your Node class from homework 4 as follows:

Two elements that compare equal shouldn't be allowed in the Tree. If a
copy is inserted, throw an AlreadyExistsException with the error
message "Element [x] is already in the tree".

__iter__(self) should return a NodeIterator, which returns elements from
the tree in sorted order. Modifying the tree should not modify
existing iterators.
'''
count = 0

def __init__(self, val, left=None, right=None):
    self.Val = val
    self.Left = left
    self.Right = right
    Node.count += 1

def __repr__(self):
    '''If the node has neither a left nor right child,
    simply return Node(val). Else, return Node(x, val, y),
    where x and y are recursive calls that return the
    left and right children, respectively.
    '''
    if self.Left is None and self.Right is None:
        return "Node({})".format(self.Val)
    else:
        return "Node({}, {}, {})".format(self.Left, self.Val, self.Right)

@depth
def search(self, element):
    ''' Finds whether a given element is in the tree.
    Returns True if the element is found, else returns False.

    Give it the depth decorator you defined earlier.
    '''
    if element == self.Val:
        return True
    elif self.Val > element and self.Left is not None:
        return self.Left.search(element)
    elif self.Val < element and self.Right is not None:
        return self.Right.search(element)
    else:
        return False

def insert(self, element):
    ''' Insert an element into a binary search tree rooted
    at this Node. After insertion, return the modified node.

    Our implementation will allow duplicate nodes. The left subtree
    should contain all elements <= to the current element, and the
    right subtree will contain all elements > the current element.
    '''
    if element <= self.Val:
        if self.Left is not None:
            self.Left.insert(element)
        else:
            self.Left = Node(element)
    else:
        if self.Right is not None:
            self.Right.insert(element)
        else:
            self.Right = Node(element)
    return self

def elements(self):
    ''' Return a list of the elements visited in an inorder traversal:
    http://en.wikipedia.org/wiki/Tree_traversal
    Note that this should be the sorted order if you've inserted all
    elements using your previously defined insert function.
    '''
    if self.Left is None and self.Right is None:
        return [self.Val]
    elif self.Left is None and self.Right is not None:
        return [self.Val] + self.Right.elements()
    elif self.Left is not None and self.Right is None:
        return self.Left.elements() + [self.Val]
    else:
        return self.Left.elements() + [self.Val] + self.Right.elements()

Answer 1

不要在 class 上定义 next；当你想要的是 iterable 而不是 迭代器。为此，您定义 __iter__ 并使其 return 成为对象副本上的全新迭代器。

由于您已经有了一个 elements 方法可以有效地对您的 Node 进行快照，因此使用它来制作快照迭代器并不难；复制结构没有意义，因为无论如何您只是按顺序迭代，elements 可以为您完成工作（并且在快照上使用更少的内存来启动）。通常，我只是让 __iter__ 成为一个生成器函数，例如：

 def __iter__(self):
     # Python 3 simple version
     yield from self.elements()
     # Python 2 or 3 version
     for x in self.elements():
         yield x

但是由于您的作业需要一个特殊的 NodeIterator class，那不行。为此，您需要创建一个新的 class（可能在您现有的 Node class 中定义以命名空间）：

class Node(object):
    ...
    class NodeIterator(object):
        def __init__(self, node):
            self.it = iter(node.elements())

        def __iter__(self):
            return self

        def next(self):
            return next(self.it)
        __next__ = next  # Makes code work on Py2 and Py3 without modification

    def __iter__(self):
        return NodeIterator(self)

当 __iter__ 的生成器函数（使用 yield 魔法的函数）非常简单时，您会明白为什么我通常不会为特殊的 class 烦恼，但那是基本结构。你可以 read more about iterators on the Python wiki, or about the basic interfaces on the Python collections ABC documentation.

如何使 class 可迭代，但如果修改 class 则迭代器不会被修改？

How to make a class iterable, but not have the iterator modified if you modify the class?

python

iterator

binary-search-tree