Python en el orden de recorrido a una lista plana

Question

He creado un método de una clase TreeNode que estoy con ganas de volver una lista plana de una de recorrido de árbol para

Mi árbol de la muestra es:

El orden de salida en el recorrido debe ser: [1, 1, 0, 2, 1, 3, 1, 1, 0]

pero me estoy: [2, 1, 1, 0, 1, 3, 1, 1, 0]

Aquí está mi código:

def in_order_list(self, r = []): 
    hasLeft = self.left is not None 
    hasRight = self.right is not None 
    if self is None: 
     return 
    else: 
     if hasLeft: 
      self.left.in_order_list(r) 
     r.append(self.value) 
     if hasRight: 
      self.right.in_order_list(r) 
    return r 

qué alguien me pueda dar una pista de por qué está sucediendo esto?

Gracias Alex

Answer 1

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) 

Answer 2

Podría ser un problema con el argumento predeterminado para r = []

Ejemplo:

def foo(list=[]): 
    list.append(1) 
    print list 


foo() 
>>> [1] 

foo() 
>>> [1,1] 

Python es mantener la misma lista a través de múltiples llamadas a funciones.

intentar hacer el inicio de su función algo como:

def in_order_list(self, r=None): 
    if r is None: 
     r = [] 

Es posible que desee colocar el resto de su código, por lo que puede saber lo que hace que la función pre_order.

Answer 3

A) en primer lugar, según lo observado por campos.ddc, tener el [] asignado al valor del parámetro r es problemático. Para más detalles de este consultan this answer on Stackoverflow (es un muy error común)

B), parecería que su "auto si es Ninguno:" la prueba es redundante, si uno mismo lo había, que no sería capaz de llamar el método in_order_list (suponiendo que esto es un método en una clase, y no una función independiente)

C) el código podría simplificarse:

def in_order_list(self, r = None): 
    if not r: 
     r = [] 
    if self.left: 
     self.left.in_order_list(r) 
    r.append(self.value) 
    if self.right: 
     self.right.in_order_list(r) 

D) las preguntas que puedan preguntas "tarea", debe ser etiquetado como tal. > :(

Answer 4

Se puede escribir este tipo de cosas muy claramente como un generador, y evitar tener que manejar listas y añadiendo:

def in_order(tree): 
    if tree is None: return 

    for value in in_order(tree.left): yield value 
    yield tree.value 
    for value in in_order(tree.right): yield value 

Por ejemplo:

>>> class Node(object): 
...  def __init__(self, value, left=None, right=None): 
...    self.value, self.left, self.right = value, left, right 
... 
>>> x = Node(3) 
>>> x.left = Node(2) 
>>> x.left.left = Node(1) 
>>> x.left.left.left = Node(1) 
>>> x.left.left.right = Node(0) 
>>> x.left.right = Node(1) 
>>> x.right = Node(1) 
>>> x.right.left = Node(1) 
>>> x.right.right = Node(0) 
>>> 
>>> in_order(x) 
<generator object in_order at 0xb742dbbc> 
>>> list(in_order(x)) 
[1, 1, 0, 2, 1, 3, 1, 1, 0]