En lugar de llamar self.left/right.
in
_order_list()
, que está llamando self.left/right.
pre
_order_list()
.
para lograr lo que desea hacer una función generador podría ser mejor (menos memoria que consume y más Pythonic) que se acumule los valores de una lista:
class Tree(object):
...
def in_order(self):
if self.left is not None:
for value in self.left.in_order():
yield value
yield self.value # <-- yielding the value of the node, not the node itself
if self.right is not None:
for value in self.right.in_order():
yield value
...
tree = Tree(...)
in_order_values = list(tree.in_order())
De esta manera, usted don' t tiene que crear una lista, si sólo desea iterar sobre los valores:
for value in tree.in_order():
...
el algoritmo funciona así: el generador desciende primero de forma recursiva a lo largo de la rama izquierda de cada nodo hasta que llega a una sin sub-izquierda nodo. Luego produce el valor del nodo actual. Después de eso, hace lo mismo en el subnodo derecho, pero comienza en el nodo actual, no en el nodo raíz. Si suponemos que no hay ciclos en el árbol y no hay ramas infinitas, definitivamente habrá nodos hoja, es decir, nodos sin sub-nodo izquierdo o derecho. Nodos IOW, para los cuales se alcanzan ambos casos base (self.left/right is None
). Por lo tanto, las llamadas recursivas volverán, con suerte antes de que nos quedemos sin memoria o lleguemos al límite de la pila.
El bucle sobre self.left/right.in_order()
es necesario debido al hecho de que lo que la llamada a in_order()
retornos es un generador, por lo tanto, la función de generador de nombres . El generador devuelto debe estar agotado de alguna manera, p. a través de un bucle.En el cuerpo del ciclo volvemos a ceder los valores en un nivel, donde vuelven a producirse nuevamente, hasta que alcanzan el nivel superior. Ahí usamos los valores.
Si desea recuperar los nodos sí mismos en lugar de sólo sus campos de valor, usted podría hacerlo de esta manera:
class Tree(object):
...
def in_order(self):
if self.left is not None:
for node in self.left.in_order():
yield node
yield self # <-- yielding the node itself
if self.right is not None:
for node in self.right.in_order():
yield node
Es posible que desee hacer esto, porque no sólo se puede seguir teniendo acceso a los valores de los nodos:
for node in tree.in_order():
do_something_with(node.value)
sino también que puede hacer lo que quiera con los nodos:
for node in tree.in_order():
whatever(node.some_other_attribute)
Dónde está pre lista de orden definida. ¿Cuál es la estructura de datos del gráfico? –