如何编写Python递归生成器与迭代器？以二叉树迭代器为例

核心思路 #

递归生成器的关键是利用yield from语法，它可以直接迭代另一个生成器/可迭代对象，并把每个产出的值传递到当前生成器中。这样你就能像写普通递归遍历函数那样，把递归逻辑转化为生成器，完美适配__iter__的需求。

代码示例（中序遍历） #

先定义基础的二叉树节点类，再实现递归生成器版的__iter__：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self, root=None):
        self.root = root
    
    # 递归生成器实现中序遍历的__iter__
    def __iter__(self):
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        return inorder(self.root)

为什么这样可行？ #

• __iter__返回的是inorder(self.root)生成器对象，天然符合Python迭代器协议（生成器本身就是迭代器）。
• 递归调用inorder(node.left)时，yield from会遍历左子树的生成器，把左子树的节点值依次产出；接着产出当前节点的值；最后再遍历右子树的生成器。整个过程完全遵循递归遍历的逻辑，不需要手动维护栈结构。

其他遍历方式的递归生成器实现 #

如果需要前序或后序遍历，只需调整yield和yield from的顺序：

前序遍历

def __iter__(self):
    def preorder(node):
        if node:
            yield node.val
            yield from preorder(node.left)
            yield from preorder(node.right)
    return preorder(self.root)

后序遍历

def __iter__(self):
    def postorder(node):
        if node:
            yield from postorder(node.left)
            yield from postorder(node.right)
            yield node.val
    return postorder(self.root)

什么时候用递归生成器？ #

当你的遍历逻辑用递归写更清晰（比如带过滤条件的遍历、复杂嵌套的树结构遍历），手动写非递归的栈维护会变得繁琐且容易出错时，递归生成器就是最优选择——代码简洁，逻辑和普通递归遍历完全一致，可读性极高。

内容的提问来源于stack exchange，提问作者wangjianyu