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

Les deux révisions précédentes Révision précédente
Prochaine révision 		Révision précédente
les_programmes_a_connaitre:algorithmique_term:parcours_arbre [2021/01/19 11:07]
mc 		les_programmes_a_connaitre:algorithmique_term:parcours_arbre [2022/05/13 11:18] (Version actuelle)
bh [Parcours en largeur d'abord]
Ligne 73: Ligne 73:
         préfixe(T.get_droit())         préfixe(T.get_droit())
 </code> </code>
 +
  
 ==== Parcours suffixe ==== ==== Parcours suffixe ====
Ligne 219: Ligne 220:
 </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.// //__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.1611050821.txt.gz · Dernière modification: 2021/01/19 11:07 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