demo1
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() # Example 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)) child2.add_child(Node(6)) for ch in root.depth_first(): print(ch) # Outputs Node(0), Node(1), Node(3), Node(4), Node(2), Node(5)
输出：
Node(0) Node(1) Node(3) Node(4) Node(2) Node(5) Node(6)
demo2
class Node2: 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): return DepthFirstIterator(self) class DepthFirstIterator(object): ''' Depth-first traversal ''' 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): # Return myself if just started; create an iterator for children if self._children_iter is None: self._children_iter = iter(self._node) return self._node # If processing a child, return its next item elif self._child_iter: try: nextchild = next(self._child_iter) return nextchild except StopIteration: self._child_iter = None return next(self) # Advance to the next child and start its iteration else: self._child_iter = next(self._children_iter).depth_first() return next(self)