
supposons (voir figure ci-dessus) que nous dispositions d’un arbre binaire (AB) dans lequel est stocké 1 calcul constitué de plusieurs opérations
on peut réaliser certaines opérations comme taille, hauteur, affichage …
nous allons nous concentrer sur 1 autre problème intéressant : comment faire concrètement l’opération stockée
- étape 1 : création de l’arbre avec la classe Nœud
- étape 2 : gestion d’une opération élémentaire, « + » par exemple
- étape 3 : gestion des 4 opérations élémentaires pour un arbre à 1 niveau
- étape 4 : généralisation
la classe Nœud 🥴
un nœud est constitué de 3 attributs :
- value : ce qui est stocké dans le nœud (1 valeur ou 1 opération)
- left : ce qui est stocké dans le fils gauche (1 nœud)
- right : ce qui est stocké dan le fils droit (1 nœud aussi)
class Noeud:
def __init__(self, v, l, r):
"""initialisation des attributs"""
self.value = v
self.left = l
self.right = r
🧙♂️ pensez ensuite à simplifier votre problème (pour le complexifier ensuite), c’est à dire à le « casser » en petit morceaux facile à résoudre
la méthode « + » 👽
pour simplifier le problème, imaginons que nous n’ayons qu’1 opération et que notre arbre n’a qu’1 niveau : calculons 2 + 3
voici la méthode .calcul() associée à la classe Nœud, gérant l’addition, sur 1 niveau
def calcul(self):
return self.left.value + self.right.value
.calcul() « + », »-« , »* », »/ » (1 niveau) 😻
complexifions notre programme en gérant les 4 opérations de base, toujours sur 1 niveau de calcul
def calcul(self):
if self.value == "+":
return self.left.value + self.right.value
elif self.value == "-":
return self.left.value - self.right.value
elif self.value == "*":
return self.left.value * self.rigth.value
elif self.value == "/":
return self.left.value / self.rigth.value
voila nous avons traiter les 4 opérations, assez facilement d’ailleurs !
reste maintenant à voir si le programme fonctionne dans le cas général …
la méthode .calcul() (général) 👏
si on teste la méthode .calcul (uniquement avec l’addition ou celle avec les 4 opérations), on se rend compte qu’elle ne fonctionne pas ; que ce passe-t-il ?
les messages d’erreurs fournis par python sont très utiles : ils indiquent que certaines opérations (addition par exemple) ne sont pas possibles
en effet, pour notre exemple initial, impossible de soustraire « + » et 4
la dernière étape de notre problème consiste donc à regarder, pour 1 nœud considéré, le contenu du fils gauche et celui du fils droit :
- si nous avons 2 nombres, il faut renvoyer le résultat du « calcul » avec l’opération du nœud sur lequel on est
- si il y a, par exemple, un opérateur à gauche, il faut d’abord faire le calcul à gauche ; idem pour la droite ; puis faire l’opération considérée
- c’est précisément de la récursivité !
class Noeud():
def __init__(self, l, v, r):
self.value = v
self.left = l
self.right = r
def calcul(self):
if self.value == "+":
return self.left.calcul() + self.right.calcul()
elif self.value == "-":
return self.left.calcul() - self.right.calcul()
elif self.value == "*":
return self.left.calcul() * self.right.calcul()
elif self.value == "/":
return self.left.calcul() / self.right.calcul()
else:
return self.value
mon_operation = Noeud(Noeud(Noeud(None,3,None),"+",Noeud(Noeud(None,2,None),"*",Noeud(None,5,None))),"-",Noeud(None,4,None))
print(mon_operation.calcul())
à bientôt, math13net

Poster un Commentaire