Table des matières

Parcourir un arbre de différentes façons

Parcours préfixe

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

Parcours suffixe

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

Parcours infixe

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

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

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

En lien avec cette page :

Cours sur les arbres binaires.

Algorithmes sur les arbres binaires et les arbres binaires de recherche.