calcul dans un arbre binaire en python

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            

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