Algorithmes Arbres Binaires de recherche
Les Arbres Binaires de recherche peuvent être implémentés avec la POO.
En plus du constructeur de la classe Noeud, nous allons utiliser 3 méthodes :
-
rechercher
-
inserer
-
supprimer
La méthode insrrer
sera utilisée de manière successive sur les éléments d'une liste dans la méthode inserer_tout
.
Définition de la classe Noeud et de son construteur⚓︎
Dans le code qui suit les lignes des codes des méthodes ont été mélangées. Il faut les remettre dans l'ordre.
Rechercher
if v < self.v:
if self.v == v:
def rechercher(self, v):
return False
return True
''' Renvoie True si v est une étiquette de l'arbre, False sinon'''
else:
return False
if self.ag == None:
return self.ad.rechercher(v)
else:
return self.ag.rechercher(v)
if self.ad == None:
else:
Inserer
Seule une partie du code de la méthdoe inserer
a été retrouvée. Le reste est a écrire.
Pour permettre un ajout de noeuds par lot, nous utlisons la méthode inserer_tout
Ainsi pour représenter un ABR avec les noeuds 15,17,21,10,8,7 et 25, nous écrivons.
Supprimer
Pour la méthode supprimer
tout est à écrire
Extra
Le code fonctionne mais ne vérifie jamais si la condition d'unicité des clés est respectée pour les ABR. Écrire un supplément dans le code qui ajoute cette vérification.