====== Parcourir un arbre de différentes façons ======

==== Parcours préfixe ====

<code python>
#---Classe permettant l'implémentation de l'arbre binaire---
class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None

   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node

   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node

   def get_valeur(self):
      return self.valeur

   def get_gauche(self):
      return self.enfant_gauche

   def get_droit(self):
      return self.enfant_droit

#---------------------fin de la classe---------------------

#--------début de la construction de l'arbre binaire-------
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')

b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')
#--------fin de la construction de l'arbre binaire--------
T = racine

"""
Objectif : Parcourir l'arbre à l'aide du parcours préfixe
Entrée : T->noeud racine
Sortie: - 
"""
def préfixe(T):
    if T != None:     
        print(T.get_valeur())
        préfixe(T.get_gauche())
        préfixe(T.get_droit())
</code>


==== Parcours suffixe ====
<code python>
#---Classe permettant l'implémentation de l'arbre binaire---
class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None

   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node

   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node

   def get_valeur(self):
      return self.valeur

   def get_gauche(self):
      return self.enfant_gauche

   def get_droit(self):
      return self.enfant_droit

#---------------------fin de la classe---------------------

#--------début de la construction de l'arbre binaire-------
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')

b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')
#--------fin de la construction de l'arbre binaire--------
T = racine

"""
Objectif : Parcourir l'arbre à l'aide du parcours suffixe
Entrée : T->noeud racine
Sortie: - 
"""        
def suffixe(T):
    if T != None:     
        suffixe(T.get_gauche())
        suffixe(T.get_droit())
        print(T.get_valeur())
</code>

==== Parcours infixe ====
<code python>
#---Classe permettant l'implémentation de l'arbre binaire---
class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None

   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node

   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node

   def get_valeur(self):
      return self.valeur

   def get_gauche(self):
      return self.enfant_gauche

   def get_droit(self):
      return self.enfant_droit

#---------------------fin de la classe---------------------

#--------début de la construction de l'arbre binaire-------
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')

b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')
#--------fin de la construction de l'arbre binaire--------
T = racine

"""
Objectif : Parcourir l'arbre à l'aide du parcours infixe
            Dans un arbre binaire de recherche -> Renvoie les valeurs dans l'ordre croissant
Entrée : T->noeud racine
Sortie: - 
"""
def infixe(T):
    if T != None:     
        infixe(T.get_gauche())
        print(T.get_valeur())
        infixe(T.get_droit())
</code>
//__Remarque :__ Dans un arbre binaire de recherche, le parcours infixe permet de faire apparaître les valeurs de l'arbre dans l'ordre croissant.//

==== Parcours en largeur d'abord ====

<code python>
#---Classe permettant l'implémentation de l'arbre binaire---
class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None

   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node

   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node

   def get_valeur(self):
      return self.valeur

   def get_gauche(self):
      return self.enfant_gauche

   def get_droit(self):
      return self.enfant_droit

#---------------------fin de la classe---------------------

#--------début de la construction de l'arbre binaire-------
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')

b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')
#--------fin de la construction de l'arbre binaire--------
T = racine

"""
Objectif : Parcourir l'arbre à l'aide du parcours en largeur d'baord
Entrée : T->noeud racine
Sortie: - 
"""
f = []

def parcours_largeur(T):
    f.append(T)
    while len(f) !=0:                            
        x=f.pop(0)                             
        return x
        if T.get_gauche != None:
            T.get_gauche.append(x.gauche)
            f.append(T.get_gauche)
        if T.get_droit !=None:
            T.get_droit.append(x.droit)
            f.append(T.get_droit)

</code>



===En lien avec cette page : ===
[[les_fiches_revisions:structure_des_donnees:arbres| Cours sur les arbres binaires]].

[[les_fiches_revisions:algorithmique:algo_arbres|Algorithmes sur les arbres binaires et les arbres binaires de recherche]].