Можете ли вы определить несколько разных итераторов для класса Python?

Question

Я пишу очень простой класс Tree:

class Tree: 
    def __init__(self, value_ = None, children_ = None): 
     self.value = value_ 
     self.children = children_ 

Я хотел бы быть в состоянии выполнять как DFS и BFS обход с помощью простого цикла, а именно:

t = Tree() 
# ...fill tree... 

for node in t: 
    print(node.value) 

В C++, например, вы можете иметь несколько типов итераторов - поэтому я мог бы определить как DFS, так и BFS-итератор и использовать тот или иной вариант в зависимости от того, какой тип обхода я хотел сделать. Можно ли это сделать в Python?

Answer 1

Вы можете иметь несколько методов возвращающихся итераторов и иметь «по умолчанию» один как __iter__. Ниже приведено простое бинарное дерево, где итератор «по умолчанию» делает DFS и который дополнительно поддерживает BFS с раздельным способом:

from collections import deque 

class Tree(object): 
    def __init__(self, value): 
     self.value = value 
     self.left = None 
     self.right = None 

    def __iter__(self): 
     if self.left: 
      for x in self.left: 
       yield x 

     yield self.value 

     if self.right: 
      for x in self.right: 
       yield x 

    def bfs(self): 
     q = deque([self]) 
     while q: 
      x = q.popleft() 
      if x: 
       yield x.value 
       q.extend([x.left, x.right]) 

Краткий Пример использования:

root = Tree(2) 
root.left = Tree(1) 
root.right = Tree(4) 
root.right.left = Tree(3) 
root.right.right = Tree(5) 

print list(root) # [1, 2, 3, 4, 5] 
print list(root.bfs()) # [2, 1, 4, 3, 5] 

Answer 2

Вы можете написать отдельные методы для своего класса для двух типов итераций. Это могут быть, например, генераторы, которые дают значения в любом порядке. Вы бы тогда написать что-то вроде:

for node in t.depth_first(): 
    # ... 

for node in t.breadth_first(): 
    # ...