Comment stocker une valeur dans une liste pendant une traversée dans un arbre?

Question

J'ai essayé de trouver un moyen efficace et facile de stocker la valeur de traversée de l'arbre (dans l'ordre) dans une liste pour un traitement ultérieur, mais je ne reçois pas un moyen approprié pour l'exécuter.

La raison pour laquelle je le veux est de trouver le mode dans l'arborescence. J'ai essayé global variables mais je ne suis pas un fan de celui-ci, rend le code mauvais. J'ai essayé la fonction de rendement mais cela ne semble pas très bien. (Je l'ai un peu d'espoir pour cela)

def inorder(self,root): 
     if not root: 
      return 
     self.inorder(root.left) 
     self.store(root.val) 
     self.inorder(root.right) 

Merci, Prerit

Answer 1

Si vous utilisez Pyhotn 3.3+, vous pouvez utiliser yield et yield from expressions:

class Node: 

    def __init__(self, val, left=None, right=None): 
     self.val = val 
     self.left = left 
     self.right = right 

    def inorder(self, root): 
     if not root: 
      return 
     yield from self.inorder(root.left) 
     yield root.val 
     yield from self.inorder(root.right) 

     # # For Python 3.2- 
     # for val in self.inorder(root.left): 
     #  yield val 
     # yield root.val 
     # for val in self.inorder(root.right): 
     #  yield val 

Utilisation:

# Traverse 
n = Node('top', Node('left'), Node('right')) 
for val in n.inorder(n): 
    print(val) 
# -> prints `left`, `top`, `right` 

# get as a list 
list(n.inorder(n)) # -> ['left', 'top', 'right']