Cours NSI Terminale - Thème 1.
# Validez cette cellule pour importer graphviz
# Ce module permet de dessiner des arbres et des graphes
from graphviz import Digraph
Dans ce TP nous allons implémenter une classe permettant de représenter un arbre binaire.
On va pour cela créer un objet Noeud qui aura 3 propriétés (ou attributs) :
Les deux propriétés gauche et droit seront des instances de la classe Noeud. Si il n'y a pas de sous arbre gauche ou droit, on indiquera la valeur None dans les propriétés correspondantes.
Dans notre classe Noeud, nous créerons 3 méthodes :
En supposant la classe Noeud créée, voici comment on l'utilise pour créer cet arbre
arbre = Noeud("A")
sous_arbre_gauche = arbre.cree_fils_gauche("B")
sous_arbre_gauche.cree_fils_gauche("D")
arbre.cree_fils_droit("C")
# Quelques vérifications possibles
print(arbre.est_feuille())
print(arbre.droit.est_feuille())
print(arbre.gauche.valeur)
# Affiche False True B
class Noeud():
# 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
def __repr__(self):
return str(self.valeur)
# Codez ici les méthodes demandées
# YOUR CODE HERE
raise NotImplementedError()
# Testez ici les méthodes de votre classe
a = Noeud(2)
a
# Tester l'exemple de départ
racine = Noeud("A")
sous_arbre_gauche = racine.cree_fils_gauche("B")
sous_arbre_gauche.cree_fils_gauche("D")
racine.cree_fils_droit("C")
assert not racine.est_feuille()
assert racine.droit.est_feuille()
assert racine.gauche.valeur == "B"
On peut compléter cette classe Noeud par une nouvelle classe décrivant un objet Arbrebin. Un arbre va contenir le Noeud racine ainsi que des méthodes permettant l'affichage de l'arbre ou appliquant des algorithmes sur cet arbre.
Nous verrons un peu plus tard dans l'année quelques uns de ces algorithmes. Néanmoins, pour vous donner un aperçu, voici une première ébauche de la classe Arbrebin qui nous sera utile pour visualiser facilement les arbres sur lesquels nous travaillerons.
Dans un premier temps, il n'est pas strictement nécessaire de comprendre les détails du fonctionnement de la méthode show car celle-ci fait appel à de la récursivité qui sera étudiée un peu plus tard.
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, racine):
self.racine = racine
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
arbre = Arbrebin(racine)
arbre.show()
A présent, vous utiliserez la classe Noeud et Arbrebin et les méthodes que vous avez développées pour représenter l'arbre suivant dans la variable expr
Les opérations seront représentées par des chaînes de caractères. Les feuilles seront des entiers.
# YOUR CODE HERE
raise NotImplementedError()
expr = Arbrebin(racine)
# Validation de la réponse
assert racine.valeur == "+"
assert racine.droit.valeur == 1
expr.show()
# Afficher le sous arbre gauche :
Arbrebin(racine.gauche).show()
Nous en resterons la pour le moment. Nous reviendrons sur les arbres plusieurs fois au cours de l'année car cette structure permet de mettre en oeuvre des algorithmes intéressants. Nous complèterons donc notre classe arbre au fur à mesure de la progression de nos conaissance, en particulier lorsque nous étudierons la récursivité.