基于Python生成器实现树的广度优先遍历方法问询

Great question! Since you're aiming to mirror the elegant generator-based approach of the depth-first traversal from David Beazly's Python Cookbook—avoiding queues and per-method state entirely—here's a solution that leans into generator composition and recursion, just like the DFS example.

The Core Idea #

Breadth-first traversal processes nodes level by level. Instead of tracking a queue, we can use generators to pass along the current level of nodes, then recursively yield from the next level (all children of the current level's nodes). This keeps the logic stateless and aligned with the functional style of the DFS method.

Updated Node Class with breadth_first #

class Node:
    def __init__(self, value):
        self._value = value
        self._children = []

    def __repr__(self):
        return 'Node({!r})'.format(self._value)

    def add_child(self, node):
        self._children.append(node)

    def __iter__(self):
        return iter(self._children)

    def depth_first(self):
        yield self
        for c in self:
            yield from c.depth_first()

    def breadth_first(self):
        # Start with the current node as the first level
        yield self
        # Recursively process the next level (all children of current level)
        yield from self._breadth_next_level([self])

    def _breadth_next_level(self, nodes):
        # Collect all children of the current level nodes
        next_level = []
        for node in nodes:
            next_level.extend(node._children)
        # If there are nodes in the next level, yield them all, then recurse
        if next_level:
            yield from next_level
            yield from self._breadth_next_level(next_level)

Example Usage #

if __name__ == '__main__':
    root = Node(0)
    child1 = Node(1)
    child2 = Node(2)
    root.add_child(child1)
    root.add_child(child2)
    child1.add_child(Node(3))
    child1.add_child(Node(4))
    child2.add_child(Node(5))

    print("Breadth-first traversal:")
    for ch in root.breadth_first():
        print(ch)
    # Outputs: Node(0), Node(1), Node(2), Node(3), Node(4), Node(5)

Why This Works #

• No queues: We don't maintain a persistent queue structure—instead, we pass the current level of nodes to the recursive helper generator.
• No internal state: The breadth_first method doesn't store any state (like a queue instance) on the Node object; all state is passed between generator calls.
• Generator elegance: Just like depth_first, we use yield and yield from to compose generators, keeping the code concise and readable.

The helper method _breadth_next_level handles the level progression: it collects all children of the current level, yields them, then recurses on that new level. This mirrors how the DFS method uses recursion to dive into children, but here we're stepping through levels instead of branches.

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