Dans ce TP nous allons implémenter une classe permettant de représenter un arbre binaire.

Voici le schéma de la structure envisagée pour la classe Arbrebin

classe Arbrebin

La propriété valeur contiendra la valeur associée au noeud. Les propriétés gauche et droit seront les sous arbres gauche et droit. Ces deux propriétés seront donc des instances de la classe Arbrebin. Si il n'y a pas de sous arbre gauche ou droit, on indiquera la valeur None dans les propriétés correspondantes.

La méthode est_feuille renverra un bouléen selon que l'objet est une feuille ou non. La méthode cree_fils_gauche() prend en paramètre une valeur et crée un fils à gauche dont la valeur est passée en paramètres.

Exemple d'utilisation de la classe Arbrebin

En supposant la classe Arbrebin créée, voici comment on l'utilise pour créer cet arbre : arbre exemple

arbre = Arbrebin("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 Arbrebin():
    
    # la méthode __repr__ définit ce qui sera affiché
    # lorsqu'on tapera l'objet dans Jupyter ou un terminal
    # Ici, on affiche juste al 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 = Arbrebin(2)
a
# Tester l'exemple de départ

arbre = Arbrebin("A")
sous_arbre_gauche = arbre.cree_fils_gauche("B")
sous_arbre_gauche.cree_fils_gauche("D")
arbre.cree_fils_droit("C")

assert not arbre.est_feuille()
assert arbre.droit.est_feuille()
assert arbre.gauche.valeur == "B"

A présent, vous utiliserez la classe Arbrebin et les méthodes que vous avez développées pour représenter l'arbre suivant dans la variable expr expression

Les opérations seront représentées par des chaînes de caractères. Les feuilles seront des entiers.

expr = ...
# YOUR CODE HERE
raise NotImplementedError()
# Validation de la réponse
assert expr.valeur == "+"
assert expr.droit.valeur == 1