Wiki NSI

Outils pour utilisateurs

Outils du site

Piste:
les_programmes_a_connaitre:algorithmique_term:parcours_arbre

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Prochaine révision 		Révision précédente
les_programmes_a_connaitre:algorithmique_term:parcours_arbre [2021/01/19 10:49]
mc created 		les_programmes_a_connaitre:algorithmique_term:parcours_arbre [2022/05/13 11:18] (Version actuelle)
bh [Parcours en largeur d'abord]
Ligne 4: Ligne 4:
  
 <code python> <code python>
-VARIABLE +#---Classe permettant l'implémentation de l'arbre binaire--- 
-T : arbre +class ArbreBinaire: 
-x : noeud+   def __init__(self, valeur): 
 +      self.valeur = valeur 
 +      self.enfant_gauche = None 
 +      self.enfant_droit = None
  
-DEBUT +   def insert_gauche(self, valeur): 
-PARCOURS-PREFIXE(T) : +      if self.enfant_gauche == None: 
-  si T ≠ NIL : +         self.enfant_gauche = ArbreBinaire(valeur) 
-    x ← T.racine +      else: 
-    affiche x.clé +         new_node = ArbreBinaire(valeur) 
-    PARCOURS-PREFIXE(x.gauche) +         new_node.enfant_gauche = self.enfant_gauche 
-    PARCOURS-PREFIXE(x.droit) +         self.enfant_gauche = new_node 
-  fin si + 
-FIN+   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> </code>
 +
  
 ==== Parcours suffixe ==== ==== Parcours suffixe ====
 <code python> <code python>
-VARIABLE +#---Classe permettant l'implémentation de l'arbre binaire--- 
-T : arbre +class ArbreBinaire: 
-x : noeud+   def __init__(self, valeur): 
 +      self.valeur = valeur 
 +      self.enfant_gauche = None 
 +      self.enfant_droit = None
  
-DEBUT +   def insert_gauche(self, valeur): 
-PARCOURS-SUFFIXE(T) : +      if self.enfant_gauche == None: 
-  si T ≠ NIL : +         self.enfant_gauche = ArbreBinaire(valeur) 
-    x ← T.racine +      else: 
-    PARCOURS-SUFFIXE(x.gauche) +         new_node = ArbreBinaire(valeur) 
-    PARCOURS-SUFFIXE(x.droit) +         new_node.enfant_gauche = self.enfant_gauche 
-    affiche x.clé +         self.enfant_gauche = new_node 
-  fin si + 
-FIN+   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> </code>
  
 ==== Parcours infixe ==== ==== Parcours infixe ====
 <code python> <code python>
-VARIABLE +#---Classe permettant l'implémentation de l'arbre binaire--- 
-T : arbre +class ArbreBinaire: 
-x : noeud+   def __init__(self, valeur): 
 +      self.valeur = valeur 
 +      self.enfant_gauche = None 
 +      self.enfant_droit = None
  
-DEBUT +   def insert_gauche(self, valeur): 
-PARCOURS-INFIXE(T) : +      if self.enfant_gauche == None: 
-  si T ≠ NIL : +         self.enfant_gauche = ArbreBinaire(valeur) 
-    x ← T.racine +      else: 
-    PARCOURS-INFIXE(x.gauche) +         new_node = ArbreBinaire(valeur) 
-    affiche x.clé +         new_node.enfant_gauche = self.enfant_gauche 
-    PARCOURS-INFIXE(x.droit) +         self.enfant_gauche = new_node 
-  fin si + 
-FIN+   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> </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]].
les_programmes_a_connaitre/algorithmique_term/parcours_arbre.1611049756.txt.gz · Dernière modification: 2021/01/19 10:49 de mc

Outils de la page

Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial 4.0 International
CC Attribution-Noncommercial 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki