Python in ordine di attraversamento di una semplice lista

Question

ho creato un metodo di una classe TreeNode che sto volendo restituire un elenco piatta di un albero, al fine di attraversamento

Il mio albero di esempio è:

L'attraversamento in ordine di uscita dovrebbe essere: [1, 1, 0, 2, 1, 3, 1, 1, 0]

ma sto ottenendo: [2, 1, 1, 0, 1, 3, 1, 1, 0]

Qui è il mio codice:

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 

Qualcuno in grado di darmi un indizio sul perché questo sta accadendo?

Grazie Alex

Answer 1

Invece di chiamare self.left/right.in_order_list(), si sta chiamando self.left/right.pre_order_list().

per realizzare ciò che si vuole fare una funzione generatore potrebbe essere migliore (meno memoria lunga e più divinatorio) rispetto ad accumulare i valori in un elenco:

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()) 

In questo modo, si don' t deve creare un elenco se desideri solo per scorrere i valori:

for value in tree.in_order(): 
    ... 

l'algoritmo funziona così: il generatore prima discende ricorsivamente lungo il ramo sinistro di ogni nodo fino a quando non colpisce uno senza sub-sinistra nodo. Quindi restituisce il valore del nodo corrente. Dopo di ciò, fa lo stesso sul sub-nodo destro, ma a partire dal nodo corrente, non dal nodo radice. Se supponiamo che non ci siano cicli nell'albero e nessun ramo infinito, allora ci saranno sicuramente nodi foglia, cioè nodi senza sub-nodo sinistro o destro. Nodi IOW, per i quali sono stati raggiunti entrambi i casi di base (self.left/right is None). Pertanto, le chiamate ricorsive torneranno, speriamo prima che la memoria sia esaurita o il limite massimo.

Il ciclo sopra self.left/right.in_order() occorre dovuto al fatto che ciò che la chiamata alla in_order() rendimenti è un generatore, quindi il funzionamento del generatore di nome . Il generatore restituito deve essere in qualche modo esaurito, ad es. attraverso un ciclo.Nel corpo del loop restituiamo i valori su un livello, dove vengono nuovamente restituiti, fino a raggiungere il livello più alto. Lì usiamo i valori.

Se si desidera recuperare i nodi themself invece di solo i loro campi di valore, si potrebbe fare così:

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 

Probabilmente vuole fare questo, perché non solo si può ancora accedere ai valori di i nodi:

for node in tree.in_order(): 
    do_something_with(node.value) 

ma anche si può fare quello che vuoi con i nodi:

for node in tree.in_order(): 
    whatever(node.some_other_attribute) 

Answer 2

Potrebbe essere un problema con l'argomento predefinito per r = []

Esempio:

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


foo() 
>>> [1] 

foo() 
>>> [1,1] 

Python sta mantenendo la stessa lista sopra chiamate di funzione multipli.

provare a fare l'inizio della vostra funzione di qualcosa di simile:

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

Si potrebbe desiderare di inviare il resto del codice, in modo che possiamo sapere che cosa quella funzione pre_order fa.

Answer 3

A) innanzitutto come indicato da campos.ddc, avere assegnato il valore [] al parametro r è problematico. Per i dettagli di questa consultano this answer on Stackoverflow (si tratta di un molto bug comune)

B) sembrerebbe il vostro "se self è Nessuno:" test è ridondante, se per sé era nessuno, non sarebbe in grado di chiamare il metodo in_order_list (supponendo che questo è un metodo in una classe, e non una funzione autonoma)

C) il codice potrebbe essere semplificata:

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) domande che sono probabili "compiti a casa" domande, dovrebbe essere etichettato come tale > :(

Answer 4

È possibile scrivere questo genere di cose davvero ordinatamente come un generatore , ed evitare di dover gestire gli elenchi e aggiungendo:

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 

Ad esempio:

>>> 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]