6.6. Création de nos classes pour les arbres.#
#!pip install graphviz
6.6.1. Avec deux classes#
Le but de ce TP est de compléter la classe Nœud et la classe Arbres.
Important
Copier le code des cellules ci dessous dans un notebook et complétez les.
class Noeud:
"""Voir la documentation de la classe dans le README"""
def __init__(self):
pass
def __repr__(self):
return str(self.valeur)
def est_feuille(self):
pass
def cree_fils_gauche(self,valeur):
pass
def cree_fils_droit(self, valeur):
pass
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
from graphviz import Digraph
Show code cell content
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)
On peut ensuite tester.
racine = Noeud("A")
sous_arbre_gauche = racine.cree_fils_gauche("B")
sous_arbre_gauche.cree_fils_gauche("D")
racine.cree_fils_droit("C")
arbre = Arbrebin(racine)
arbre.show().render()
Important
Compléter le code ci-dessous pour obtenir l’arbre de calcul donné en exemple dans le cours.
racine =
expr = Arbrebin(racine)
expr.show().render()