Cours NSI Terminale - Thème 5.
Dans ce classeur, nous allons mettre en oeuvre les algorithmes vus en cours. Nous partirons de deux classes :
Validez les cellules suivantes et analysez bien la structure proposée.
from graphviz import Digraph
class Noeud():
"""Représente un noeud dans un arbre binaire
- Propriétés :
* valeur : valeur du noeud
* gauche : noeud gauche ou None
* droit : noeud droit ou None
- Méthodes :
* est_feuille()
* __repr__() : affichage d'un noeud"""
def __repr__(self):
"""la méthode __repr__ définit ce qui sera affiché
lorsqu'on tapera l'objet dans Jupyter ou un terminal
Ici, on affiche juste la valeur du noeud"""
return str(f"## {self.valeur} ##")
def __init__(self,valeur):
self.valeur = valeur
self.gauche = None
self.droit = None
def est_feuille(self):
"""Renvoie un booleen selon que le noeud est une feuille"""
return self.gauche is None and self.droit is None
class Arbrebin:
"""Représente un objet arbre binaire
- Propriétés :
* racine : objet de type Noeud désignant la racine de l'arbre
- Méthodes :
* show() : représentation graphique de l'arbre à l'aide de graphviz
"""
def __init__(self, nd = None):
# Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel
self.racine = nd
def importe(self, tableau):
"""Importe un arbre depuis un tableau
["Noeud", [S_A_G], [S_A_D]]
[ ] désigne un arbre vide"""
def importe_tableau(tableau):
# Cas particuliers
if tableau == []:
return None
if len(tableau) == 1:
return Noeud(tableau[0])
# tableau a une longueur >= 2
nd = Noeud(tableau[0])
nd.gauche = importe_tableau(tableau[1])
nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None
return nd
self.racine = importe_tableau(tableau)
def show(self):
"""Renvoie un objet graphviz pour la visualisation graphique de l'arbre"""
def representation(dot, noeud, aretes):
# Ajoute la représentation du noeud à la représentation dot de l'arbre
if noeud is not None:
dot.node(str(id(noeud)), str(noeud.valeur))
# Appel récursif de la fonction representation
if noeud.gauche is not None:
representation(dot, noeud.gauche, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.gauche))))
if noeud.droit is not None:
representation(dot, noeud.droit, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.droit))))
dot = Digraph(comment="Arbre binaire", format='svg')
aretes = []
representation(dot, self.racine, aretes)
dot.edges(aretes)
return dot
Regardons notre classe en action : Nous allons recréer l'arbre exemple du cours.
# On crée la structure d'arbre à l'aide d'un tableau ["Noeud", [S_A_G], [S_A_D]]
arbre_liste = ["A",
["B", ["C",[],["E"]],
["D"]],
["F", ["G", ["I"]],
["H",["J", ["K"]]] ],
]
# On crée une instance vide de notre arbre
arbre = Arbrebin()
# On importe le tableau ci-dessus
arbre.importe(arbre_liste)
# On visualise l'arbre graphiquement
arbre.show()
Nous allons ajouter nos premières méthodes personelles à la classe Arbrebin. Commençons par la taille de l'arbre. Nous avons conçu un algorithme récursif en cours se basant sur le principe que la taille d'un arbre est égal à 1 + la taille du Sous Arbre Gauche + la taille du Sous Arbre Droit. Voici une implémentation de cet algorithme dans la classe Arbrebin, elle vous servira de modèle pour les autres méthodes que vous aurez à implémenter dans ce TD.
Vous remarquerez que pour éviter la multiplication des méthodes, nous créons une fonction locale taille_arbre
qui n'est visible que dans la méthode taille
. C'est cette fonction qui implémente en réalité l'algorithme, la méthode n'étant là que pour invoquer la fonction taille_arbre
sur la racine de l'arbre.
class Arbrebin:
"""Représente un objet arbre binaire
- Propriétés :
* racine : objet de type Noeud désignant la racine de l'arbre
- Méthodes :
* show() : représentation graphique de l'arbre à l'aide de graphviz
"""
def __init__(self, nd = None):
# Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel
self.racine = nd
def importe(self, tableau):
"""Importe un arbre depuis un tableau
["Noeud", [S_A_G], [S_A_D]]
[ ] désigne un arbre vide"""
def importe_tableau(tableau):
# Cas particuliers
if tableau == []:
return None
if len(tableau) == 1:
return Noeud(tableau[0])
# tableau a une longueur >= 2
nd = Noeud(tableau[0])
nd.gauche = importe_tableau(tableau[1])
nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None
return nd
self.racine = importe_tableau(tableau)
def show(self):
"""Renvoie un objet graphviz pour la visualisation graphique de l'arbre"""
def representation(dot, noeud, aretes):
# Ajoute la représentation du noeud à la représentation dot de l'arbre
if noeud is not None:
dot.node(str(id(noeud)), str(noeud.valeur))
# Appel récursif de la fonction representation
if noeud.gauche is not None:
representation(dot, noeud.gauche, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.gauche))))
if noeud.droit is not None:
representation(dot, noeud.droit, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.droit))))
dot = Digraph(comment="Arbre binaire", format='svg')
aretes = []
representation(dot, self.racine, aretes)
dot.edges(aretes)
return dot
def taille(self):
"""Renvoie la taille de l'arbre"""
def taille_arbre(nd):
# condition d'arrêt
if nd is None:
return 0
# Appel récursif
return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)
return taille_arbre(self.racine)
# Utilisation sur l'arbre exemple :
# On instancie notre arbre
arbre = Arbrebin()
arbre.importe(arbre_liste)
# On invique la méthode taille
arbre.taille()
En utilisant le même modèle que pour la taille, vous allez implémenter la méthode hauteur
déterminant la hauteur de l'arbre. Vous complèterez donc la cellule ci-dessous et vérifierez qu'elle passe bien le test.
class Arbrebin:
"""Représente un objet arbre binaire
- Propriétés :
* racine : objet de type Noeud désignant la racine de l'arbre
- Méthodes :
* show() : représentation graphique de l'arbre à l'aide de graphviz
"""
def __init__(self, nd = None):
# Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel
self.racine = nd
def importe(self, tableau):
"""Importe un arbre depuis un tableau
["Noeud", [S_A_G], [S_A_D]]
[ ] désigne un arbre vide"""
def importe_tableau(tableau):
# Cas particuliers
if tableau == []:
return None
if len(tableau) == 1:
return Noeud(tableau[0])
# tableau a une longueur >= 2
nd = Noeud(tableau[0])
nd.gauche = importe_tableau(tableau[1])
nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None
return nd
self.racine = importe_tableau(tableau)
def show(self):
"""Renvoie un objet graphviz pour la visualisation graphique de l'arbre"""
def representation(dot, noeud, aretes):
# Ajoute la représentation du noeud à la représentation dot de l'arbre
if noeud is not None:
dot.node(str(id(noeud)), str(noeud.valeur))
# Appel récursif de la fonction representation
if noeud.gauche is not None:
representation(dot, noeud.gauche, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.gauche))))
if noeud.droit is not None:
representation(dot, noeud.droit, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.droit))))
dot = Digraph(comment="Arbre binaire", format='svg')
aretes = []
representation(dot, self.racine, aretes)
dot.edges(aretes)
return dot
def taille(self):
"""Renvoie la taille de l'arbre"""
def taille_arbre(nd):
# condition d'arrêt
if nd is None:
return 0
# Appel récursif
return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)
return taille_arbre(self.racine)
def hauteur(self):
"""Renvoie la hauteur de l'arbre"""
def hauteur_arbre(nd):
# YOUR CODE HERE
raise NotImplementedError()
return hauteur_arbre(self.racine)
# Cellule de tests
arbre = Arbrebin()
arbre.importe(arbre_liste)
assert arbre.hauteur() == 5
# On indique la méthode taille
Voici la méthode permettant le parcours en profondeur préfixe. 0. Ajoutez-la à la classe Arbrebin 0. Vérifiez son bon fonctionnement 0. Implémentez de même les parcours suffixe et infixe. 0. Validez votre travail grâce à la cellule de tests.
Vous ferez attention de choisir les mêmes noms de méthodes que dans la cellule de test pour passer ces derniers avec succès.
def parcours_prefixe(self):
"""Renvoie la liste des noeuds dans un parcours Prefixe"""
def prefixe(noeud):
# Condition d'arrêt
if noeud is None:
return []
# Appel récursif et renvoi réponse
# La valeur est insérée AVANT les appels
return [noeud.valeur] + prefixe(noeud.gauche) + prefixe(noeud.droit)
return prefixe(self.racine)
```
class Arbrebin:
"""Représente un objet arbre binaire
- Propriétés :
* racine : objet de type Noeud désignant la racine de l'arbre
- Méthodes :
* show() : représentation graphique de l'arbre à l'aide de graphviz
"""
def __init__(self, nd = None):
# Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel
self.racine = nd
def importe(self, tableau):
"""Importe un arbre depuis un tableau
["Noeud", [S_A_G], [S_A_D]]
[ ] désigne un arbre vide"""
def importe_tableau(tableau):
# Cas particuliers
if tableau == []:
return None
if len(tableau) == 1:
return Noeud(tableau[0])
# tableau a une longueur >= 2
nd = Noeud(tableau[0])
nd.gauche = importe_tableau(tableau[1])
nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None
return nd
self.racine = importe_tableau(tableau)
def show(self):
"""Renvoie un objet graphviz pour la visualisation graphique de l'arbre"""
def representation(dot, noeud, aretes):
# Ajoute la représentation du noeud à la représentation dot de l'arbre
if noeud is not None:
dot.node(str(id(noeud)), str(noeud.valeur))
# Appel récursif de la fonction representation
if noeud.gauche is not None:
representation(dot, noeud.gauche, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.gauche))))
if noeud.droit is not None:
representation(dot, noeud.droit, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.droit))))
dot = Digraph(comment="Arbre binaire", format='svg')
aretes = []
representation(dot, self.racine, aretes)
dot.edges(aretes)
return dot
def taille(self):
"""Renvoie la taille de l'arbre"""
def taille_arbre(nd):
# condition d'arrêt
if nd is None:
return 0
# Appel récursif
return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)
return taille_arbre(self.racine)
# YOUR CODE HERE
raise NotImplementedError()
# Cellule de tests
arbre = Arbrebin()
arbre.importe(arbre_liste)
assert arbre.parcours_prefixe() == ['A', 'B', 'C', 'E', 'D', 'F', 'G', 'I', 'H', 'J', 'K']
assert arbre.parcours_suffixe() == ['E', 'C', 'D', 'B', 'I', 'G', 'K', 'J', 'H', 'F', 'A']
assert arbre.parcours_infixe() == ['C', 'E', 'B', 'D', 'A', 'I', 'G', 'F', 'K', 'J', 'H']
Pour finir, ajoutez à la classe Arbrebin la méthode parcours_largeur()
Vous vérifierez votre travail avec la cellule de tests. Il pourra être utile de revoir l'implémentation des files FIFO avec un tableau python.
class Arbrebin:
"""Représente un objet arbre binaire
- Propriétés :
* racine : objet de type Noeud désignant la racine de l'arbre
- Méthodes :
* show() : représentation graphique de l'arbre à l'aide de graphviz
"""
def __init__(self, nd = None):
# Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel
self.racine = nd
def importe(self, tableau):
"""Importe un arbre depuis un tableau
["Noeud", [S_A_G], [S_A_D]]
[ ] désigne un arbre vide"""
def importe_tableau(tableau):
# Cas particuliers
if tableau == []:
return None
if len(tableau) == 1:
return Noeud(tableau[0])
# tableau a une longueur >= 2
nd = Noeud(tableau[0])
nd.gauche = importe_tableau(tableau[1])
nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None
return nd
self.racine = importe_tableau(tableau)
def show(self):
"""Renvoie un objet graphviz pour la visualisation graphique de l'arbre"""
def representation(dot, noeud, aretes):
# Ajoute la représentation du noeud à la représentation dot de l'arbre
if noeud is not None:
dot.node(str(id(noeud)), str(noeud.valeur))
# Appel récursif de la fonction representation
if noeud.gauche is not None:
representation(dot, noeud.gauche, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.gauche))))
if noeud.droit is not None:
representation(dot, noeud.droit, aretes)
aretes.append((str(id(noeud)) , str(id(noeud.droit))))
dot = Digraph(comment="Arbre binaire", format='svg')
aretes = []
representation(dot, self.racine, aretes)
dot.edges(aretes)
return dot
def taille(self):
"""Renvoie la taille de l'arbre"""
def taille_arbre(nd):
# condition d'arrêt
if nd is None:
return 0
# Appel récursif
return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)
return taille_arbre(self.racine)
# YOUR CODE HERE
raise NotImplementedError()
# Cellule de tests
arbre = Arbrebin()
arbre.importe(arbre_liste)
assert arbre.parcours_largeur() == ['A', 'B', 'F', 'C', 'D', 'G', 'H', 'E', 'I', 'J', 'K']
Il est temps de passer aux arbres binaires de recherche. Un ABR est un arbre binaire particulier. Il est donc souhaitable que toutes les méthodes définies dans la classe Arbrebin soient aussi disponibles dans la classe Abr que nous allons créer.
Faire un copier/coller de ces dernières serait fort maladroit. La structure d'objet nous offre un mécanisme particulièrement intéressant ici : la notion *d'héritage. En faisant hériter notre classe Abr* de la classe Arbrebin, toutes les méthodes d'Arbrebin seront disponibles pour Abr et nous n'aurons juste qu'à nous soucier des méthodes spécifiques aux arbres binaires de recherche.
Afin de pouvoir commencer à manipuler nos ABR, nous allons implémenter la méthode insere
. Complétez la classe ci-dessous
class Abr(Arbrebin):
"""Arbre Binaire de Recherche
Hérite de la classe Arbre binaire"""
def __init__(self):
"""A l'initialisation, notre arbre est vide"""
self.racine = None
def insere(self, valeur):
"""Insère valeur dans note ABR
paramètre : valeur à insérer"""
def insere_noeud(nd, valeur):
# insère la valeur dans nd
# renvoie le noeud complété
# YOUR CODE HERE
raise NotImplementedError()
self.racine = insere_noeud(self.racine, valeur)
Si votre méthode insere
fonctionne, la cellule ci-dessous doit construire un ABR en utilisant l'arbre d'exemple.
Une fois votre classe au point, changez l'ordre de parcours de l'arbre de départ pour observer l'impact sur l'ABR construit. Vous constarerez alors que l'ABR est loin d'être unique : tout dépend de l'ordre d'insertion des valeurs. Un de ces ABR sera plus efficace pour la recherche. Trouvez-vous lequel ?
# Vous pouvez modifier le contenu de cette cellule !
# On crée un ABR vide
mon_abr = Abr()
# On insère les valeurs de notre arbre de départ dans un certain ordre
for v in arbre.parcours_prefixe():
mon_abr.insere(v)
mon_abr.show()
# Cellule de test
mon_abr = Abr()
for v in arbre.parcours_prefixe():
mon_abr.insere(v)
# les méthodes de Arbrebin sont disponibles pour Abr sans avoir eu a les recréer
# c'est la magie de l'héritage
assert mon_abr.hauteur() == 9
Pour la suite de notre activité, nous changerons un peu et jouerons avec les termes d'une suite célèbre. Peut-être la reconnaîtrez-vous ! Commmençons par construire notre ABR. Que constatez-vous ? Cet arbre est-il intéressant pour rechercher une valeur ?
suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]
suite_abr = Abr()
for v in suite:
suite_abr.insere(v)
suite_abr.show()
Pour résoudre ce problème, nos allons utiliser une technique surprenante : appeler l'aléatoire à la rescousse ! Vous allez constater qu'en mélangeant notre suite, la situation s'améliore très sensiblement !
from random import shuffle
suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]
shuffle(suite)
suite_abr = Abr()
for v in suite:
suite_abr.insere(v)
suite_abr.show()
Voilà qui est nettement mieux !!
Vous allez maintenant pour terminer cette activité implémenter la méthode recherche
qui prend une valeur en paramètre et renvoie un booleen selon que la valeur est dans l'arbre ou non.
class Abr(Arbrebin):
"""Arbre Binaire de Recherche
Hérite de la classe Arbre binaire"""
def __init__(self):
"""A l'initialisation, notre arbre est vide"""
self.racine = None
# YOUR CODE HERE
raise NotImplementedError()
suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987]
shuffle(suite)
suite_abr = Abr()
for v in suite:
suite_abr.insere(v)
assert suite_abr.recherche(233)
assert not suite_abr.recherche(317)