本文共 2059 字，大约阅读时间需要 6 分钟。

深度优先生成器实现

Node类的定义与实现

在本节中，我们将定义一个Node类，该类用于表示树形结构中的节点，并实现深度优先遍历的生成器功能。Node类的主要功能包括：

代码实现

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 child in self:            yield from child.depth_first()

深度优先遍历的测试与验证

为了验证depth_first方法的实现是否正确，我们可以通过以下步骤进行测试：

树的结构示例

假设树的结构如下：

root├─ child1│   ├─ child3│   └─ child4├─ child2│   └─ child5

测试代码

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))for ch in root.depth_first():    print(ch)

普通深度优先实现的比较

相比自定义生成器方法，传统的深度优先遍历实现往往需要引入额外的迭代器对象。其典型实现思路如下：

具体实现代码

class DepthFisrtIterator(object):    def __init__(self, start_node):        self._node = start_node        self._children_iter = None        self._child_iter = None    def __iter__(self):        return self    def __next__(self):        if self._children_iter is None:            self._children_iter = iter(self._node)            return self._node        elif self._child_iter:            try:                nextchild = next(self._children_iter)                return nextchild            except StopIteration:                self._child_iter = None                return next(self)        else:            self._children_iter = next(self._children_iter).depth_first()            return next(self)

总结

通过上述实现，可以清楚地看到深度优先生成器的两种不同实现方式。自定义生成器方法更为简洁高效，充分利用了Python的生成器特性，而传统的迭代器方法则通过组合多个迭代器来实现深度优先遍历。选择哪一种方式取决于具体的性能需求和实现场景。在实际应用中，推荐采用生成器方法，因其代码简洁且易于扩展。