python retournant une liste à partir d'une méthode récursive

Question

Im en utilisant un arbre binaire décrit dans ce livre problem solving with algorithms and data structures

class BinaryTree: 
    def __init__(self,rootObj): 
     self.key = rootObj 
     self.leftChild = None 
     self.rightChild = None 

Il existe déjà une méthode de pré-commande défini traversal comme suit.

def preorder(tree): 
    if tree: 
     print(tree.self.key) 
     preorder(tree.getLeftChild()) 
     preorder(tree.getRightChild()) 

Je veux juste ajouter une valeur de retour de la liste des nœuds visités. Donc, je peux faire quelque chose comme

for i in preorder(tree): 
    etc... 

J'ai du mal à retourner une liste d'une méthode récursive. La récursion arrête dès qu'elle touche le « retour » que j'ai essayé d'utiliser les variations

return [tree.self.key] + preorder() 

Ou

yield ... 

Toutes les idées?

Answer 1

Vous avez à fait retour une valeur de la fonction récursive (actuellement, il est juste l'impression des valeurs). Et vous devez construire la liste que vous allez, et nettoyer peut-être le code un peu - quelque chose comme ceci:

def preorder(tree): 
    if not tree: 
     return [] 
    # optionally, you can print the key in this line: print(self.key) 
    return [tree.key] + preorder(tree.leftChild) + preorder(tree.rightChild) 

Answer 2

Vous pouvez ajouter deuxième argument à la fonction preorder, quelque chose comme

def preorder(tree, visnodes): 
    if tree: 
     visnodes.append(tree.self.key) 
     print(tree.self.key) 
     preorder(tree.getLeftChild(), visnodes) 
     preorder(tree.getRightChild(), visnodes) 

... 
vn = [] 
preorder(tree, vn) 

Answer 3

Êtes-vous sûr que vous voulez tree.self.key et pas simplement tree.key lorsque vous imprimez?

Sinon, une solution avec yield from (Python 3.3+):

def preorder(tree): 
    if tree: 
     yield tree 
     yield from preorder(tree.getLeftChild()) 
     yield from preorder(tree.getRightChild()) 

Ou avec de simples yield:

def preorder(tree): 
    if tree: 
     yield tree 
     for e in preorder(tree.getLeftChild()): 
      yield e 
     for e in preorder(tree.getRightChild()): 
      yield e 

Notez que l'utilisation yield ou yield from transforme la fonction en generator function; en particulier, si vous voulez une liste réelle (pour l'indexation, le découpage ou l'affichage par exemple), vous devrez le créer explicitement: list(preorder(tree)).

Si vous avez un nombre variable d'enfants, il est facile d'adapter:

def preorder(tree): 
    if tree: 
     yield tree 
     for child in tree.children: 
      yield from preorder(child) 

Answer 4

Vous pouvez simplement retourner une liste concaténée pour chaque appel récursif, qui combine la clé actuelle, le sous-arbre gauche et le sous-arbre droit :

def preorder(tree): 
     if tree: 
      return ([tree.key] + preorder(tree.getLeftChild()) + 
        preorder(tree.getRightChild())) 
     return [] 

Pour un arbre n-aire:

def preorder(tree): 
    if tree: 
     lst = [tree.key] 
     for child in tree.children: 
      lst.extend(preorder(child)) 
     return lst 
    return []