Chapitre 6 : Les arbres binaires.

Insérer dans Python l'arbre suivant à l'aide d'une liste de listes.

Une feuille aura ce format : [valeur,None,None]

Écrire une fonction ajout_feuille_gauche(liste_arbre, valeur) qui prend en paramètre un arbre sous forme de liste et une valeur.

Elle fonctionnera de manière récursive ainsi :

• Si l’enfant gauche de la racine est vide, on place la valeur à cet endroit.
• Sinon, on exécute cette fonction dans le sous-arbre gauche.

Dans le contexte, un arbre est ici stocké dans des listes de listes (format [etiquette, gauche, droite]). Par exemple :

["Olivier",
 ["Julien", None, None],
 ["Léa", None, None]]

On représente un arbre binaire par une liste de la forme [etiquette, gauche, droite], où gauche et droite sont soit None, soit des sous-arbres au même format.

Écrire en Python les fonctions suivantes :

• taille(arbre) : renvoie le nombre total de nœuds de l’arbre.
• hauteur(arbre) : renvoie la hauteur de l’arbre (un arbre réduit à un seul nœud a une hauteur égale à 1 ; l’arbre vide a une hauteur de 0).
• nombre_de_feuilles(arbre) : renvoie le nombre de feuilles (nœuds sans enfant) de l’arbre.

Exemple de structure :

["Olivier",
 ["Julien", None, None],
 ["Léa", None, None]]

On représente un arbre binaire par une liste [etiquette, gauche, droite], où gauche et droite sont soit None, soit des sous-arbres au même format.

1. lecture_prefixe(arbre) : renvoie la liste des valeurs rencontrées en ordre préfixe (racine, gauche, droite).
2. lecture_infixe(arbre) : renvoie la liste des valeurs en ordre infixe (gauche, racine, droite).
3. lecture_postfixe(arbre) : renvoie la liste des valeurs en ordre postfixe (gauche, droite, racine).

Compléter le code pour créer l’instance arbre et tous ses descendants en utilisant ajout_gauche / ajout_droit.

On représente un arbre binaire avec la classe ArbreBinaire (valeur, gauche, droit). Écrire les fonctions suivantes :

• taille(arbre) : renvoie le nombre total de nœuds (0 si l’arbre est vide) ;
• hauteur(arbre) : renvoie la hauteur (0 si vide, 1 si un seul nœud) ;
• nombre_feuilles(arbre) : renvoie le nombre de feuilles (nœuds sans enfant).

On représente un arbre binaire avec la classe ArbreBinaire (valeur, gauche, droit). Écrire des fonctions qui renvoient la liste des valeurs rencontrées :

1. lecture_prefixe(racine) : ordre préfixe (racine, gauche, droite) ;
2. lecture_infixe(racine) : ordre infixe (gauche, racine, droite) ;
3. lecture_postfixe(racine) : ordre postfixe (gauche, droite, racine).

On représente un arbre binaire avec la classe ArbreBinaire (valeur, gauche, droit).

Écrire une fonction parcours_largeur(arbre) qui renvoie la liste des valeurs rencontrées lors du parcours en largeur de l’arbre (niveau par niveau de gauche à droite).

Pour cela, on utilisera une classe File permettant de gérer une file FIFO avec les méthodes :

• enfiler(x) : ajoute un élément en fin de file ;
• defiler() : retire et renvoie le premier élément de la file ;
• est_vide() : renvoie True si la file est vide.

Exemple :

#         'A'
#        /   \ 
#      'B'   'C'
#     /  \      \
#   'D'  'E'    'F'
# Le parcours en largeur renvoie : ['A', 'B', 'C', 'D', 'E', 'F']

On représente une expression mathématique sous forme d’arbre binaire à l’aide de la classe ArbreBinaire. Chaque nœud contient soit un opérateur (+, -, *, /), soit un entier.

Programmer une fonction Python evaluer qui prend comme paramètre un objet ArbreBinaire contenant une expression mathématique et qui renvoie le résultat numérique.

Nous avons l’habitude de noter les expressions arithmétiques avec des parenthèses comme par exemple : \((2 + 3) \times 5\).

Il existe une autre notation utilisée par certaines calculatrices, appelée notation postfixe, qui n’utilise pas de parenthèses. L’expression arithmétique précédente est alors obtenue en saisissant successivement 2, puis 3, puis l’opérateur +, puis 5, et enfin l’opérateur *. On modélise cette saisie par le tableau [2, 3, '+', 5, '*'].

Autre exemple, la notation postfixe de \(3 \times 2 + 5\) est modélisée par le tableau :

[3, 2, '*', 5, '+']

D’une manière plus générale, la valeur associée à une expression arithmétique en notation postfixe est déterminée à l’aide d’une pile en parcourant l’expression de gauche à droite :

• si l’élément parcouru est un nombre, on le place au sommet de la pile,
• si l’élément parcouru est un opérateur, on récupère les deux éléments situés au sommet de la pile et on leur applique l’opérateur, puis on place le résultat au sommet de la pile,
• à la fin du parcours, il reste alors un seul élément dans la pile qui est le résultat de l’expression arithmétique.

Dans cet exercice, on se limitera aux opérations * et +.

Complète la fonction eval_expression qui reçoit en paramètre une liste python représentant la notation postfixe d’une expression arithmétique et qui renvoie sa valeur.

⭐ Exemple :

>>> eval_expression([2, 3, '+', 5, '*'])
25

Une expression arithmétique ne comportant que les quatre opérations \(+\), \(-\), \( \times \), \( \div \) peut être représentée sous forme d’arbre binaire. Les nœuds internes sont des opérateurs et les feuilles sont des nombres. Dans un tel arbre, la disposition des nœuds joue le rôle des parenthèses que nous connaissons bien.

En parcourant en profondeur infixe l’arbre binaire ci-dessus, on retrouve l’expression notée habituellement :

\((3 \times (8 + 7)) – (2 + 1)\)

La classe Expr ci-après permet d’implémenter une structure d’arbre binaire pour représenter de telles expressions.

Compléter la méthode récursive infixe qui renvoie une chaîne de caractères contenant des parenthèses représentant l’expression arithmétique sur laquelle on l’applique.

Un arbre binaire de caractères est stocké sous la forme d’un dictionnaire où les clés sont les caractères des nœuds de l’arbre et les valeurs, pour chaque clé, la liste des caractères des fils gauche et droit du nœud.

Par exemple, l’arbre

est stocké dans

a = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'],'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], 'H':['','']}

Écrire une fonction récursive taille prenant en paramètres un arbre binaire arbre sous la forme d’un dictionnaire et un caractère lettre qui est la valeur du sommet de l’arbre, et qui renvoie la taille de l’arbre, à savoir le nombre total de nœud.

On observe que, par exemple, arbre[lettre][0], respectivement arbre[lettre][1], permet d’atteindre la clé du sous-arbre gauche, respectivement droit, de l’arbre arbre de sommet lettre.

Exemple :

>>> taille(a, 'F')
9

Il est moins usuel mais nous pouvons programmer un parcours préfixé en itératif à l'aide de l'algorithme suivant :

fonction parcours_prefixe_iteratif(arbre):
    créer une pile p
    insérer l'arbre dans la pile 
    tant que la pile p n'est pas vide 
        depiler un element de la pile que l'on nommera element 
        traiter la racine de cet element en l'affichant par exemple
        si le sous-arbre droit n'est pas vide :
            on empile dans p le sous-arbre droit
        si le sous arbre gauche n'est pas vide :
            on empile dans p le sous-arbre gauche

Coder ceci en python à l'aide des classes ArbreBinaire et Pile. On pourra utiliser un arbre des exercices précédents.

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud représenté par un triplet (g, x, d) où x est l’étiquette du nœud et g et d sont les sous-arbres gauche et droit.

On souhaite écrire une fonction parcours_largeur qui prend en paramètre un arbre binaire et qui renvoie la liste des étiquettes des nœuds de l’arbre parcourus en largeur.

Exemples :

>>> arbre = ( ( (None, 1, None), 2, (None, 3, None) ),
...           4,
...           ( (None, 5, None), 6, (None, 7, None) ) )
>>> parcours_largeur(arbre)
[4, 2, 6, 1, 3, 5, 7]