J'essaye d'implémenter un itérateur dans mon arbre de recherche binaire. Pour y parvenir, j'essaie de faire un parcours dans l'ordre dans l'arborescence et de produire chaque membre de données individuel. Cela me permettra de parcourir chaque élément de l'arborescence.
Ma fonction:
TypeError: iter() returned non-iterator of type 'NoneType'
Lors du test de cette fonction avec une itération telle que
for i in tree:
Je reçois cette erreur:
def __iter__(self):
"""
in-order traversal of a binary search tree
"""
if self.root is not None:
self.check(self.root)
def check(self, cur_node):
if cur_node is not None:
self.check(cur_node.left)
yield cur_node.data #if I were to print this data member, it would be fine
self.check(cur_node.right)
3 Réponses :
L'indice est
iter () a renvoyé ....
Vous devez donc renvoyer un itérateur. Votre classe est un itérateur, donc retournez self
class Tree:
def __init__(...): ...
def __iter__(self):
return self
def __next__(self):
if self.left is not None:
yield from self.left
yield self.data
if self.right is not None:
yield from self.right
Vous devriez probablement implémenter également __next__ pour obtenir réellement la valeur.
La solution pourrait donc ressembler à
def __iter__(self):
"""
in-order traversal of a binary search tree
"""
if self.root is not None:
self.check(self.root)
return self
Vous utilisez ici yield from pour déléguer aux nœuds enfants. Voir https: / /docs.python.org/3/whatsnew/3.3.html#pep-380-syntax-for-delegating-to-a-subgenerator
Vous avez en fait besoin de trois instructions yield, car vous devez parcourir à la fois les enfants gauche et droit, ainsi que produire la valeur du nœud actuel.
Changer l'état interne d'une opération d'énumération est une mauvaise idée ... et si plusieurs utilisateurs veulent itérer le même arbre en même temps?
Je traverse une boucle infinie? J'ai fait un léger ajustement à votre code en éditant cur_node.left en self.cur_node.left. Êtes-vous sûr que nous avons besoin de 3 déclarations de rendement?
J'ai mis à jour ceci pour résoudre le problème de multi-threading et utiliser les attributs de classe.
Pour implémenter un générateur récursif, vous ne pouvez pas simplement "appeler" vous-même, vous devez extraire des éléments et les produire.
Python a une syntaxe spéciale pour cela:
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def __iter__(self):
if self.left:
yield from self.left
yield self.data
if self.right:
yield from self.right
où expr est itérable, et il peut être vu comme un raccourci pour
for x in expr:
yield x
En utilisant ceci, vous pouvez implémenter la traversée dans l'ordre d'un arbre avec quelque chose comme:
yield from expr
Vous voulez généralement que votre itérateur soit une entité distincte de votre structure de données, afin que vous puissiez avoir plusieurs itérateurs sur vos données, et ainsi vous pouvez itérer sur vos données plusieurs fois. Ci-dessous, je montre comment mettre en œuvre un algorithme DFS simple pour une classe BST de base.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __iter__(self):
return BSTIterator(self)
class BSTIterator:
def __init__(self, root):
self.stack = []
curr = root
while curr:
self.stack.append(curr)
curr = curr.left
def __next__(self):
if not self.stack:
raise StopIteration()
node = self.stack.pop()
val = node.val
node = node.right
while node:
self.stack.append(node)
node = node.left
return val
def __iter__(self):
return self
root = Node(5, Node(3, Node(1), Node(4)), Node(10, (Node(6, None, Node(7)))))
list(root)
# [1, 3, 4, 5, 6, 7, 10]