Python (resa): tutti i percorsi da foglie a radice in un albero

Question

Voglio generare tutti i percorsi da ogni foglia a radice in un albero. Mi piacerebbe farlo con i generatori, per risparmiare memoria (l'albero può essere grande). Ecco il mio codice:

def paths(self, acc=[]): 
    if self.is_leaf(): 
     yield [self.node]+acc 

    for child in self.children: 
     child.paths([self.node]+acc) 

Ma non funziona. Perché? Invocato alla radice, attraversa l'albero da cima a fondo, raccogliendo nodi in "acc". "acc" deve essere restituito in ogni foglia ...

is_leaf() è true se self.children è vuoto.

Answer 1

Questo codice cede solo foglie che sono (immediati) figli della radice. Gli altri vengono visitati, si arrendono alla funzione superiore, ma la funzione superiore non fa nulla con loro. Quello che ti serve è cederli dalla funzione inferiore a quella superiore:

def paths(self, acc=[]): 
    if self.is_leaf(): 
     yield [self.node]+acc 

    for child in self.children: 
     for leaf_path in child.paths([self.node]+acc): # these two 
      yield leaf_path       # lines do that 

Questo dovrebbe fare il trucco.

Answer 2

Al momento il ciclo for non corrisponde a yield. Si dovrebbe invece produrre tutti gli elementi che vengono generati dalla chiamata ricorsiva:

for child in self.children: 
    for path in child.paths([self.node]+acc): 
     yield path