Arbres binaires

Introduction

Nous avons vu de façon générale, les arbres dans la partie précédente. Nous allons restreindre un peu notre champ d'action en nous consacrant maintenant uniquement aux arbres binaires.

Propriétés

Avant de continuer notre réflexion sur les arbres binaires, nous allons tenter de comprendre pourquoi cette structure hiérarchique est intéressante.

L'arbre ci-dessous est un arbre binaire un peu particulier car il est complet, c'est à dire que les nœuds de cet arbre ont tous exactement un fils gauche et un fils droit, sauf les feuilles bien entendu...

Implémentation

Vous avez déjà implémenté ou mis en œuvre de nombreux types abstraits de données linéaires : piles, files, listes...
L'arbre binaire n'est pas un type linéaire, mais il est tout à fait possible de l'implémenter en python.
Dans certains cas il est intéressant d'implémenter un arbre dans une liste Python. Cependant dans cette situation, il n'est pas forcément facile de trouver les fils d'un nœud, et on perd l'intérêt de la structure récursive.

Nous choisirons une implémentation en POO qui ressemble à celle utilisée pour implémenter les listes chaînées :

class Arbre:
    def __init__(self, valeur = None, filsgauche = None, filsdroit = None):
        self.valeur = valeur
        self.filsgauche = filsgauche
        self.filsdroit = filsdroit	
				

Afin de faciliter votre travail, une méthode d'affichage des arbres binaires a déjà été implémentée. Vous n'aurez donc, pour utiliser cette nouvelle classe, qu'a télécharger le fichier classe_arbre.py à l'enregistrer et à l'importer en début de script.

Pour comprendre le fonctionnement de la classe Arbre, construisez et affichez l'arbre hetre ci-contre.

L'affichage se fait grâce à la méthode dessine() de la classe.

from classe_arbre import * hetre = ... hetre.dessine()

SOLUTION

Une application : les arbres arithmétiques

Nous avons vu dans la première partie qu'il était possible de coder une expression arithmétique dans un arbre binaire. En effet l'arithmétique correspond à la combinaison d'un opérateur (+, -, x, /) et de deux opérandes (entiers, réels...).

Par exemple l'arbre arithmétique ci-contre représente l'expression (x+1)(3y+2).

L'intérêt de construire un tel arbre à partir d'une expression arithmétique est multiple :

• C'est utile pour calculer cette expression (il faut bien comprendre qu'ici "(x+1)(3y+2)" est de type str et que si l'on connaît les valeur de x et de y il n'est pas simple de calculer sa valeur).
• Cela peut être utile pour résoudre de manière formelle une équation
• Cela peut être utile également pour calculer de manière formelle la dérivée d'une expression.

Vous trouverez ci-dessous l'algorithme (récursif) qui permet de calculer la valeur d'une expression arithmétique contenue dans un arbre binaire :

méthode calcule(arbre arithmétique)

	entrée : arbre binaire arithmétique
	sortie : valeur de l'expression arithmétique
	
	Si l'arbre est une feuille alors :
		renvoyer valeur de la feuille
	Sinon si l'étiquette du nœud est '+' alors:
		renvoyer calcule(filsgauche) + calcule(filsdroit)
	Sinon si l'étiquette du nœud est '-' alors:
		renvoyer calcule(filsgauche) - calcule(filsdroit)
	Sinon si l'étiquette du nœud est '*' alors:
		renvoyer calcule(filsgauche) * calcule(filsdroit)
	Sinon si l'étiquette du nœud est '/' alors:
		renvoyer calcule(filsgauche) / calcule(filsdroit)
					 

	
class Arbrearith(Arbre):
	''' La classe Arbrearith hérite des méthodes de Arbre '''
	
	def calcule(self): # mais elle implémente aussi ses propres fonctionnalités
		...
	
					 

Un problème binaire : le morse

Même si le morse est un langage binaire un peu démodé, il peut être intéressant de se pencher sur la possibilité d'un décodage rapide de tel message pour voir l’intérêt des arbres binaires.

Nous baserons notre travail sur le dictionnaire de morse ci-dessous :

dicomorse = { 'A':'.-', 'B':'-...','C':'-.-.', 'D':'-..', 'E':'.','F':'..-.', 'G':'--.', 'H':'....','I':'..','J':'.---','K':'-.-','L':'.-..', 'M':'--', 'N':'-.','O':'---', 'P':'.--.', 'Q':'--.-','R':'.-.', 'S':'...','T':'-','U':'..-', 'V':'...-', 'W':'.--','X':'-..-', 'Y':'-.--', 'Z':'--..','1':'.----', '2':'..---', '3':'...--','4':'....-', '5':'.....', '6':'-....','7':'--...', '8':'---..', '9':'----.','0':'-----', ', ':'--..--', '.':'.-.-.-','?':'..--..', '/':'-..-.', '-':'-....-','(':'-.--.', ')':'-.--.-',' ':'.......'}
				 

Construire l'arbre binaire

La première chose à faire est de transformer ce dictionnaire en arbre binaire.
La règle de construction pour une lettre sera la suivante :

• On part de la racine de l'arbre
• Si le premier caractère est un trait on suit la branche de droite
• Si le premier caractère est un point on suit la branche de gauche
• On traite ainsi tous les traits et les points du caractère
• l'étiquette du nœud final sera la lettre codée

On doit ainsi obtenir l'arbre suivant :

insertion_gauche(valeur): # permet d'insérer un nœud-fils à gauche du nœud courant, en précisant son étiquette
			
insertion_droite(valeur):  # idem à droite   
						

Décoder un message

Une fois cet arbre construit, nous allons l'utiliser pour décoder un message en morse.

Parlons un peu de complexité

Pour décoder un message en morse, il est normalement nécessaire de parcourir tout le dictionnaire de morse pour trouver le caractère qui correspond au code reçu.
Il est donc nécessaire, au pire, de faire 43 comparaisons ( = le nombre de caractères présents dans notre dictionnaire de morse ).

Pour trouver un caractère dans l'arbre que vous venez de construire, il suffit au contraire de suivre le "bon" chemin. Dans le pire des cas on doit faire 6 comparaison !
On voit ainsi le gain qu'il y a si on cherche ensuite "souvent" à décoder un code morse.
Mais bien sur ici le morse est une excuse pour voir plus loin 😏...

Décodons !

Maintenant que vous maîtrisez le concept, il ne vous reste plus qu'à l'utiliser pour décoder un message en morse.