Wiki NSI

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

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

Cours sur les arbres binaires de recherche.

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