Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== 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]].
Wiki NSI

Outils pour utilisateurs

Outils du site

Outils de la page
