Wiki NSI

Outils pour utilisateurs

Outils du site

Piste:
les_programmes_a_connaitre:algorithmique_term:cle_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:cle_arbre [2021/01/19 10:53]
mc created 		les_programmes_a_connaitre:algorithmique_term:cle_arbre [2022/04/29 11:57] (Version actuelle)
lt [Insérer une clé]
Ligne 1: Ligne 1:
-====== Rechercher une clé (noeud) dans un arbre de recherche, insérer une clé (noeud) ======+====== Rechercher ou insérer une clé dans un arbre de recherche 
 +======
  
 +====Rechercher une clé====
 +<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(15)
 +racine.insert_gauche(6)
 +racine.insert_droit(18)
 +
 +b_node = racine.get_gauche()
 +b_node.insert_gauche(3)
 +b_node.insert_droit(7)
 +
 +i_node = racine.get_droit()
 +i_node.insert_gauche(17)
 +i_node.insert_droit(20)
 +
 +c_node = b_node.get_gauche()
 +c_node.insert_gauche(2)
 +c_node.insert_droit(4)
 +
 +d_node = b_node.get_droit()
 +d_node.insert_droit(13)
 +
 +g_node = d_node.get_droit()
 +g_node.insert_gauche(9)
 +#--------fin de la construction de l'arbre binaire--------
 +T = racine
 +
 +"""
 +Objectif : Rechercher un noeud k dans un arbre binaire de recherche 
 +(complexité en O(n) dans le pire des cas)
 +Entrée : T->noeud racine, k->noeud recherché
 +Sortie:True/False
 +"""      
 +def arbre_recherche(T,k):
 +    if T == None:
 +        return False
 +    if k == T.get_valeur():
 +        return True
 +    if k<T.get_valeur():
 +        return arbre_recherche(T.get_gauche(),k)
 +    else:
 +        return arbre_recherche(T.get_droit(),k)
 +</code>
 +
 +====Insérer une clé====
 +<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(15)
 +racine.insert_gauche(6)
 +racine.insert_droit(18)
 +
 +b_node = racine.get_gauche()
 +b_node.insert_gauche(3)
 +b_node.insert_droit(7)
 +
 +i_node = racine.get_droit()
 +i_node.insert_gauche(17)
 +i_node.insert_droit(20)
 +
 +c_node = b_node.get_gauche()
 +c_node.insert_gauche(2)
 +c_node.insert_droit(4)
 +
 +d_node = b_node.get_droit()
 +d_node.insert_droit(13)
 +
 +g_node = d_node.get_droit()
 +g_node.insert_gauche(9)
 +#--------fin de la construction de l'arbre binaire--------
 +T = racine
 +
 +"""
 +Objectif : Insérer un noeud y dans un arbre de recherche 
 +(complexité en O(n) dans le pire des cas)
 +Entrée : T->noeud racine,y->noeud à insérer
 +Sortie : affiche(racine)
 +"""
 +def arbre_insertion(T,y):
 +    while T.get_droit()!=None or T.get_gauche()!=None:
 +        if y<T.get_valeur():
 +            T = T.get_gauche()
 +        else:
 +            T = T.get_droit()
 +    if y<T.get_valeur():
 +        y_node = T
 +        y_node.insert_gauche(y)
 +    else:
 +        y_node = T
 +        y_node.insert_droit(y)   
 +</code>
 +
 +===En lien avec cette page : ===
 +[[les_fiches_revisions:structure_des_donnees:arbres| Cours sur les arbres binaires de recherche]].
 +
 +[[les_fiches_revisions:algorithmique:algo_arbres|Algorithmes sur les arbres binaires et les arbres binaires de recherche]].
les_programmes_a_connaitre/algorithmique_term/cle_arbre.1611049986.txt.gz · Dernière modification: 2021/01/19 10:53 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