06a Les arbres
Table des matières
2. 📏 Notions générales sur les arbres
4. 👣 Le parcours en profondeur des arbres binaires
5. 🌳 Parcours en largeur d’un arbre binaire
6. 🧮 Une application de l’arbre binaire : notation polonaise inversée
Compétences évaluables :
- Identifier des situations nécessitant une structure de données arborescente.
- Evaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.)
- Calculer la taille et la hauteur d’un arbre
- Parcourir un arbre de différentes façons (ordres infixe, préfixe, suffixe ; ordre en largeur d’abord)
1. 🌳 Terminologie
⚓︎
1.1. 📚 Vocabulaire
⚓︎
Un arbre est une structure hiérarchique composée de nœuds, utilisée pour représenter des données organisées selon des relations de parenté.
📌 En langage plus mathématique : un arbre est un graphe non orienté, connexe, sans cycle, dans lequel un nœud racine sert de point de départ.
🧠 À retenir :
- Chaque nœud (ou sommet) a au plus un père (sauf la racine qui n’en a pas).
- Un nœud peut avoir 0 ou plusieurs fils.
- Un nœud sans fils est une feuille.
- Un nœud avec au moins un fils est un nœud interne.
- Chaque nœud est souvent associé à une étiquette.
1.2. 🌲 Exemples d’arbres
⚓︎
👪 Arbre généalogique :
📝 Arbre syntaxique (analyse grammaticale) :
🧮 Arbre d'expression mathématique :
Exemple pour l'expression (y/2 - t) × (75 + z) :
🎯 Activité n° 1 : Représenter l’expression 3 + 73 - 13
✔️ Solution
-
/ \
+ 13
/ \
3 73
🌐 DOM (Document Object Model) pour représenter une page HTML :
💾 Arborescence des fichiers dans un système UNIX :
2. 📏 Notions générales sur les arbres
⚓︎
🧮 Définitions importantes :
- La taille d’un arbre = nombre total de nœuds
- La profondeur d’un nœud = distance (en nombre d’arêtes) de ce nœud à la racine
- La hauteur d’un arbre = profondeur maximale parmi tous ses nœuds
🎯 Convention dans ce cours :
- Arbre vide → hauteur = 0
- Arbre réduit à la racine seule → hauteur = 1
📌 Attention : certains livres définissent l’arbre vide avec une hauteur -1 (on s’y adaptera selon le contexte).
🔍 Exemple d’analyse :
- Taille = 8
- Profondeur de G = 3 (G → K → C)
- Profondeur de Z = 4 (Z → F → B → C)
- Hauteur de l’arbre = 4
3. 🌿 Les arbres binaires
⚓︎
3.1. 🧩 Définition
⚓︎
🔄 L’arbre de l’expression a × b + c - d + e est un arbre binaire :
🧠 Définition récursive d’un arbre binaire :
- Soit un arbre vide
- Soit une racine et exactement deux sous-arbres : un gauche et un droit
📌 Un nœud peut donc avoir 0, 1 ou 2 fils
🪄 Pour ne pas oublier un fils, on représente l’arbre vide avec un petit symbole, comme ci-dessous :
📘 À bien maîtriser : le vocabulaire précis
-
Un nœud possède :
-
un fils gauche
-
un fils droit
-
Un arbre binaire est constitué :
-
d’un sous-arbre gauche
- d’un sous-arbre droit
🧩 Donc :
- Le fils gauche est la racine du sous-arbre gauche
- Le fils droit est la racine du sous-arbre droit
🎯 Activité n°2 : Identifier des sous-arbres
Entourer en rouge le sous-arbre gauche, en bleu le sous-arbre droit, et en vert le sous-arbre droit du sous-arbre gauche dans l’arbre suivant :
✔️ Solution
- 🔴 Le sous-arbre gauche est tout le bloc de gauche à partir du premier embranchement.
- 🔵 Le sous-arbre droit est tout le bloc de droite.
- 🟢 Le sous-arbre droit du sous-arbre gauche est celui qui descend à droite depuis le fils gauche de la racine.
🔢 Activité n°3 : Arbres binaires et indexation dans un tableau
Quelle propriété ont les indices des fils gauches et droits dans un tableau représentant un arbre binaire ? par exemple pour l'arbre précédent ['a', 'c', 'e', 'g', 'b', None, 'f']
🧠 Solution
✅ Si l’indexation commence à 1 :
- Fils gauche =
2 * i- Fils droit =
2 * i + 1✅ Si l’indexation commence à 0 :
- Fils gauche =
2 * i + 1- Fils droit =
2 * i + 2🧪 Exemple avec une indexation à partir de 1 :
- Pour le nœud à l’indice
3→ fils gauche à6, fils droit à7
🧮 Activité n°4 : Arbre à partir d’un tableau
Voici un tableau représentant un arbre binaire :
['*', '-', 5, 2, 6, None, None, None, None, None, None, None, None, None, None]
🔧 Le dessiner et interpréter ce qu’il représente.
✏️ Solution
Représentation de l’arbre :
📋 Texte* / \ - 5 / \ 2 6Interprétation : Cet arbre représente une expression mathématique.
- La racine
*indique une multiplication.- Le sous-arbre gauche est une soustraction
2 - 6.- Le sous-arbre droit est la constante
5.👉 L’expression est donc : (2 − 6) × 5
3.2. 🧪 Type Abstrait de Donnée (TAD) pour un arbre binaire
⚓︎
📘 Voici les fonctions de l’interface minimale pour manipuler un arbre binaire immutable (modifiable uniquement par création d’un nouvel arbre) :
| Fonction | Description |
|---|---|
nvNd(x: Elt) -> Noeud |
Crée un nœud contenant une valeur x |
contenu(noeud: Noeud) -> Elt |
Renvoie la valeur contenue dans un nœud |
nvAv() -> Arbre |
Crée un arbre vide |
nvAB(noeud, g, d) -> Arbre |
Crée un arbre dont la racine est noeud, avec g et d comme sous-arbres gauche et droit |
estArbreVide(arbre: Arbre) -> bool |
Renvoie True si l’arbre est vide |
racine(arbre: Arbre) -> Noeud |
Donne la racine de l’arbre |
gauche(arbre: Arbre) -> Arbre |
Renvoie le sous-arbre gauche |
droite(arbre: Arbre) -> Arbre |
Renvoie le sous-arbre droit |
🌲 Activité n°5 : Créer un arbre avec le TAD
Créer l’arbre ci-dessous à l’aide des fonctions d’interface du TAD :
📝 Le contenu de chaque nœud est une chaîne : "A", "B", etc.
🛠️ Solution
# Étape 1 : Création des nœuds
noeud_A = nvNd("A")
noeud_C = nvNd("C")
noeud_E = nvNd("E")
noeud_G = nvNd("G")
noeud_B = nvNd("B")
noeud_F = nvNd("F")
# Étape 2 : Sous-arbre gauche (C avec fils G et B)
sous_arbre_gauche_C = nvAB(noeud_C, nvAB(noeud_G, nvAv(), nvAv()), nvAB(noeud_B, nvAv(), nvAv()))
# Étape 3 : Sous-arbre droit (E avec un seul fils droit F)
sous_arbre_droit_E = nvAB(noeud_E, nvAv(), nvAB(noeud_F, nvAv(), nvAv()))
# Étape 4 : Arbre final avec racine A
arbre_complet = nvAB(noeud_A, sous_arbre_gauche_C, sous_arbre_droit_E)
3.3. Caractéristiques d’un arbre binaire
⚓︎
❤️ À retenir :
- La taille d’un arbre est le nombre total de nœuds (on n’inclut pas les arbres-vides).
- La profondeur d’un nœud est le nombre de nœuds entre ce nœud et la racine.
- La hauteur d’un arbre est la profondeur maximale parmi tous ses nœuds.
🌳 Activité n°6 : Calcul de la taille d’un arbre
🧮 Déterminer la taille de l’arbre ci-dessous :
✅ Solution
✅ L’arbre contient les nœuds A, C, E, G, B et F. 👉 Taille de l’arbre = 6
🎓 Convention pour la profondeur :
Deux conventions sont admises (elles seront indiquées au BAC) :
-
📏 Convention 1 : La racine est de profondeur 1
-
🧱 Convention 2 : La racine est de profondeur 0
❤️ Quelle que soit la convention :
- La profondeur d’un fils = profondeur du père + 1
- Deux nœuds avec la même profondeur sont à même distance de la racine
🧠 Activité n°7 : Taille, hauteur, arêtes, profondeur
Fournir la taille, la hauteur, le nombre d’arêtes de cet arbre, et la profondeur du nœud C : On supposera que la racine est au niveau 0.
📌 Solution
- 🌳 Taille : 7 nœuds (A, B, C, D, E, F, G)
- 📏 Hauteur : la racine est au niveau 0 ; les feuilles (D, E, F, G) sont au niveau 2 → Hauteur = 2
- 🧩 Nombre d’arêtes = 7 – 1 = 6
- 🧮 Profondeur du nœud C = 1
🧠 Cet arbre est complet car tous les niveaux sont remplis jusqu'à la hauteur maximale, et toutes les feuilles sont au même niveau.
🪢 Activité n°8 : Arbre filiforme
Même exercice :
📌 Solution
- 🌳 Taille : 7 nœuds
- 📏 Hauteur : le dernier nœud G est au niveau 6 → Hauteur = 6
- 🧩 Nombre d’arêtes = 6
- 🧮 Profondeur du nœud C = 2
⚠️ Cet arbre est filiforme (ou dégénéré) car il se comporte comme une liste chaînée : un seul chemin.
🧩 Activité n°9 : Arbre déséquilibré
Une dernière analyse :
📌 Solution
- 🌳 Taille : 7 nœuds
- 📏 Hauteur : les nœuds E et G sont à la profondeur 4 → Hauteur = 4
- 🧩 Nombre d’arêtes = 6
- 🧮 Profondeur du nœud C = 2
Cet arbre est déséquilibré, avec une profondeur irrégulière. Il n’est ni complet, ni filiforme.
🌳 Hauteur et taille d’un arbre binaire complet (convention : racine à profondeur 0)
Un arbre binaire complet est un arbre dans lequel tous les niveaux sont complètement remplis. Cela signifie que chaque nœud interne a deux enfants, et que le dernier niveau est plein.
On suppose ici que la profondeur de la racine est 0.
🧩 Exemple 1 : Arbre de hauteur 1
| Niveau | Nombre de nœuds |
|---|---|
| 0 | 1 = 2⁰ |
| 1 | 2 = 2¹ |
🧮 Taille totale : 1 + 2 = 3 nœuds
🧩 Exemple 2 : Arbre de hauteur 2
| Niveau | Nombre de nœuds |
|---|---|
| 0 | 1 = 2⁰ |
| 1 | 2 = 2¹ |
| 2 | 4 = 2² |
🧮 Taille totale : 1 + 2 + 4 = 7 nœuds
🧩 Exemple 3 : Arbre de hauteur 3
Cet arbre est complet : tous les nœuds internes ont deux enfants.
| Niveau | Nombre de nœuds |
|---|---|
| 0 | 1 = 2⁰ |
| 1 | 2 = 2¹ |
| 2 | 4 = 2² |
| 3 | 8 = 2³ |
🧮 Taille totale : 1 + 2 + 4 + 8 = 15 nœuds
📏 Formule générale : Taille d’un arbre binaire complet
Si un arbre a une hauteur h (avec racine à profondeur 0), alors :
\(\text{Taille}\) = \(2^{h+1} - 1\)
- Pour h = 3 : \(2^{4} - 1\) = \(16 - 1 = 15\)
- Pour h = 4 : \(2^{5} - 1\) = \(32 - 1 = 31\)
🧠 Pourquoi la formule fonctionne ?
Chaque niveau \(i\) (de 0 à \(h\)) contient \(2^i\) nœuds.
Donc la taille totale est la somme géométrique :
\(n = 2^0 + 2^1 + 2^2 + \dots + 2^h = 2^{h+1} - 1\)
C’est une propriété classique des puissances de 2.
🧮 Astuce Python pour vérifier :
import math
n = 15
hauteur = int(math.log2(n + 1)) - 1 # pour convention racine à profondeur 0
print("Hauteur estimée :", hauteur) # Résultat : 3
Python
Activité n° 10 : Arbres binaires et vocabulaire :
| Calculer la taille d'un Arbre Complet dont on vous donne la hauteur: |
|---|
| Si on considère une profondeur de 1 pour la racine : |
| - Hauteur h = 1 : Taille n = 1 |
| - Hauteur h = 2 : Taille : n = 1 + 2 = 3 |
| - Hauteur h = 3 : La taille : n = 1 + 2 + ... |
| - Hauteur h = 4 : La taille : n = |
| - Hauteur h = 5 : La taille: n = |
| Quelle fonction mathématique permettrait de trouver la hauteur h connaissant la taille n de l'arbre complet ? |
| Si on considère une profondeur de 0 pour la racine : |
| - Hauteur h = 0 : Taille n = 1 |
| - Hauteur h = 1 : Taille : n = 1 + 2 = 3 |
| - Hauteur h = 2 : La taille : n = 1 + 2 + ... |
| - Hauteur h = 3 : La taille : n = |
| - Hauteur h = 4 : La taille: n = |
| Quelle fonction mathématique permettrait de trouver la hauteur h connaissant la taille n de l'arbre complet ? |
Solution
1. Profondeur de 1 pour la racine⚓︎
Si on considère que la racine est à une profondeur de 1, alors la taille n d'un arbre binaire complet de hauteur h peut être calculée de la manière suivante :
- Hauteur h = 1 : Taille
n = 1 - Hauteur h = 2 : Taille
n = 1 + 2 = 3 - Hauteur h = 3 : Taille
n = 1 + 2 + 4 = 7 - Hauteur h = 4 : Taille
n = 1 + 2 + 4 + 8 = 15 - Hauteur h = 5 : Taille
n = 1 + 2 + 4 + 8 + 16 = 31
Formule générale :
Pour une hauteur h, la taille d'un arbre binaire complet est donnée par la somme des puissances de 2 :
\(n = 2^0 + 2^1 + 2^2 + \dots + 2^{h-1} = 2^h - 1\)
Pour trouver la hauteur h connaissant la taille n :
On peut inverser la formule pour obtenir :
\(h = \log_2(n + 1)\)
2. Profondeur de 0 pour la racine⚓︎
Si on considère que la racine est à une profondeur de 0, alors la taille n d'un arbre binaire complet de hauteur h peut être calculée de la manière suivante :
- Hauteur h = 0 : Taille
n = 1 - Hauteur h = 1 : Taille
n = 1 + 2 = 3 - Hauteur h = 2 : Taille
n = 1 + 2 + 4 = 7 - Hauteur h = 3 : Taille
n = 1 + 2 + 4 + 8 = 15 - Hauteur h = 4 : Taille
n = 1 + 2 + 4 + 8 + 16 = 31
Formule générale :
Pour une hauteur h, la taille d'un arbre binaire complet est donnée par :
\(n = 2^0 + 2^1 + 2^2 + \dots + 2^h = 2^{h+1} - 1\)
Pour trouver la hauteur h connaissant la taille n :
On peut inverser la formule pour obtenir :
\(h = \log_2(n + 1) - 1\)
Encadrements de la hauteur d'un Arbre Binaire 🌲 Les deux cas extrêmes étant :
- Arbre binaire filiforme
- Arbre binaire complet
On en déduit que pour un arbre binaire quelconque, situé entre ces deux cas particuliers extrêmes, on peut encadrer la hauteur de l'arbre binaire quelconque à l'aide de la formule suivante :
🧮 Encadrement avec une profondeur 1 pour la racine :
⌈log2(n+1)⌉ ≤ h ≤ n
Remarque : les signes ⌈ ⌉ indiquent simplement un arrondi à l'entier supérieur.
🧮 Encadrement avec une profondeur 0 pour la racine :
⌊log2(n)⌋ ≤ h ≤ n - 1
Les signes ⌊ ⌋ signifient d'arrondir à l'inférieur.
📌 Exemple : un arbre binaire complet de 15 nœuds possède une hauteur de 4 si la racine a une profondeur de 1.
Si on tape ceci dans Python :
>>> import math
>>> math.log2(15+1)
4.0
>>> math.log2(16+1)
4.087462841250339
❇️ Python :
On voit alors qu'un arbre de 15 nœuds a une hauteur comprise dans [4; 15].
Par contre, avec 16 nœuds, on obtient une hauteur comprise dans [5; 16].
✅ C'est normal : avec 15 nœuds, l'arbre serait complet dans le meilleur des cas. Si on en rajoute un, il faut nécessairement rajouter un étage…
3.4. Implémentation simple à partir de liste
⚓︎
💡 De manière plus surprenante, il existe une méthode pour implémenter un arbre binaire (structure hiérarchique) avec une liste (structure linéaire). Ceci peut se faire par le biais d'une astuce sur les indices :
🧩 Les fils du nœud d'indice i sont placés aux indices 2i+1 et 2i+2.
Cette méthode est connue sous le nom de « méthode d'Eytzinger », et utilisée notamment en généalogie pour numéroter facilement les individus d’un arbre généalogique.
📌 Exemple :
🧠 Pour comprendre facilement la numérotation, il suffit de s'imaginer l’arbre complet (en rajoutant les fils vides) et de faire une numérotation en largeur, niveau par niveau :
Activité n° 11 : Arbres binaires et liste :
Si on note Δ le sous-arbre vide, dessiner l'arbre représenté par la liste : a = [3, 4, Δ, 7, 5]
Solution
3.5. ❤️1ère implémentation de la structure ARBRE BINAIRE sous forme de tuple❤️
⚓︎
🧠 Capytale : arbre_binaire_tuple
🧩 Activité n° 12 : Arbres binaires et les fonctions
Implémenter cette structure de base :
def arbreVide():
pass
def noeud(e, g=None, d=None):
# retourne la valeur du noeud, son fils gauche et son fils droit s'ils existent
pass
def etiquette(arbre):
# retourne la valeur de la racine
pass
def gauche(arbre):
# retourne le sous arbre gauche
pass
def droit(arbre):
# retourne le sous arbre droit
pass
def estVide(arbre):
pass
❇️ Solution :
def arbreVide():
return None
def noeud(e, g=None, d=None):
return (e, g, d)
def etiquette(arbre):
if arbre :
return arbre[0]
def gauche(arbre):
if arbre :
return arbre[1]
def droit(arbre):
if arbre :
return arbre[2]
def estVide(arbre):
return arbre is None
🌳 Activité n° 13 : Construire un arbre avec les fonctions
Soit l'arbre suivant :
Construire cet arbre avec l’implémentation précédente.
❇️ Solution :
arbre = noeud("A",
noeud("B", noeud("D"), noeud("E")),
noeud("C", None, None))
🧠 Activité n° 14 : Fonction hauteur
Implémenter l’algorithme de la fonction hauteur et tester-la sur l’arbre précédent.
Voici l’algorithme (convention 1 pour la racine) :
HAUTEUR(T) :
si T est vide :
renvoyer 0
sinon :
renvoyer 1 + max(HAUTEUR(gauche), HAUTEUR(droit))
❇️ Solution :
def hauteur(arbre):
if estVide(arbre):
return 0
else:
return 1 + max(hauteur(gauche(arbre)), hauteur(droit(arbre)))
# Test :
print(hauteur(arbre)) # Doit renvoyer 3
📏 Activité n° 15 : Fonction taille
Implémenter la fonction taille et tester-la.
TAILLE(T) :
si T = NIL :
renvoyer 0
sinon :
renvoyer 1 + TAILLE(gauche) + TAILLE(droit)
❇️ Solution :
def taille(arbre):
if estVide(arbre):
return 0
else:
return 1 + taille(gauche(arbre)) + taille(droit(arbre))
# Test :
print(taille(arbre)) # Doit renvoyer 6
🧠 Capytale : arbre_binaire_POO_v1
3.6. ❤️2ème implémentation de la structure ARBRE BINAIRE avec la POO et une classe❤️
⚓︎
🔧 Activité n° 16 : Arbres binaires et POO
Implémenter la structure ARBRE avec une seule classe :
class Noeud:
def __init__(self, valeur = None, g = None, d = None):
pass
def estVide(self):
pass
❓ Question : expliquer le rôle de chaque méthode de la classe Noeud.
❇️ Solution :
class Noeud:
def __init__(self, valeur=None, g=None, d=None):
self.valeur = valeur
self.g = g
self.d = d
def estVide(self):
return self.valeur is None
__init__(self, valeur=None, g=None, d=None) Constructeur de la classe. Il initialise un nœud avec une valeur (valeur) et des références aux sous-arbres gauche (g) et droit (d). Par défaut, le nœud est vide (valeur None).
estVide(self) Méthode qui retourne True si le nœud est vide, c'est-à-dire si sa valeur est None. Cela permet de savoir si l'arbre contient des données ou non.
🌲 Activité n° 17 : Construire un arbre avec la classe Noeud
Soit l'arbre suivant :
Compléter les commandes :
E = Noeud('E')
D = Noeud('D')
???
arbre = Noeud('A', B, C)
On implantera aussi l’arbre T :
T = Noeud('A')
T.g = Noeud('B')
???
❇️ Solution :
# Arbre 1
E = Noeud('E')
D = Noeud('D')
B = Noeud('B', D, E)
F = Noeud('F')
C = Noeud('C', None, F)
arbre = Noeud('A', B, C)
# Arbre T
# Création de la racine
T = Noeud('A')
# Ajout du sous-arbre gauche et droit de A
T.g = Noeud('B')
T.d = Noeud('C')
# Ajout des sous-arbres de B
T.g.g = Noeud('D')
T.g.d = Noeud('E')
# Ajout du sous-arbre gauche de E
T.g.d.g = Noeud('F')
# Ajout du sous-arbre droite de F
T.g.d.g.d = Noeud('G')
🌲 Activité n° 18 : Arbres binaires et POO
🌳 Il est possible d'afficher un arbre binaire dans la console Python, pour cela, nous allons utiliser la fonction affiche :
def affiche(arbre):
if arbre != None:
return (arbre.valeur,affiche(arbre.g),affiche(arbre.d))
Cette fonction renvoie une série de tuples de la forme (valeur,arbre_gauche, arbre_droite), comme "arbre_gauche" et "arbre_droite" seront eux-mêmes affichés sous forme de tuples, on aura donc un affichage qui ressemblera à :
(valeur,(valeur_gauche,arbre_gauche_gauche,arbre_gauche_droite),(valeur_droite,arbre_droite_gauche,arbre_droite_droite)),
mais comme "arbre_gauche_gauche" sera lui-même représenté par un tuple...
Ajouter :
print(affiche(arbre))
print(affiche(T))
Remarque : en implémentant la méthode affiche cela donnerait :
def affiche2(self):
if self.g and self.d:
return self.valeur, self.g.affiche2(), self.d.affiche2()
elif self.g:
return self.valeur,self.g.affiche2(),None
elif self.d:
return self.valeur,None, self.d.affiche2()
else:
return self.valeur, None, None
Ajouter :
print(arbre.affiche2())
print(T.affiche2())
❇️ Solution :
# affichage fonctionnelle en tuple imbriqué
print(affiche(arbre))
print(affiche(T))
# méthode dans la classe
print(arbre.affiche2())
print(T.affiche2())
🌲 Activité n° 19 : Arbres binaires et POO : fonction hauteur
Implémenter l’algorithme de la fonction hauteur et tester l’arbre précédent.
Voici l’algorithme correspondant à la fonction hauteur : (convention 1 pour la racine)
HAUTEUR(T) :
si T est vide :
renvoyer 0
sinon :
renvoyer 1 + max(HAUTEUR(T du sous-arbre gauche), HAUTEUR(T du sous-arbre droit))
fin si
La fonction max renvoie la plus grande valeur des 2 valeurs passées en paramètre (exemple : max(5,6) renvoie 6).
❇️ Solution :
def hauteur(T):
if T is None:
return 0
else:
return 1 + max(hauteur(T.g), hauteur(T.d))
🌲 Activité n° 20 : Arbres binaires et POO : méthode hauteur2
Implémenter l’algorithme de la méthode hauteur2 et tester l’arbre précédent.
Tester avec l’arbre T qui devrait avoir une hauteur de 5.
❇️ Solution :
def hauteur2(self):
"""
Méthode calculant la hauteur de l'arbre.
"""
if self is None or self.estVide(): # Vérifie si l'arbre est vide
return 0
else:
hauteur_gauche = self.g.hauteur2() if self.g else 0
hauteur_droite = self.d.hauteur2() if self.d else 0
return 1 + max(hauteur_gauche, hauteur_droite)
🌲 Activité n° 21 : Arbres binaires et POO : fonction taille
Implémenter l’algorithme de la fonction taille et tester l’arbre précédent.
Voici l’algorithme correspondant à la fonction taille :
TAILLE(T) :
si T est vide:
renvoyer 0
sinon :
renvoyer 1 + TAILLE(T du sous-arbre gauche)+TAILLE(T du sous-arbre droit)
fin si
❇️ Solution :
def taille(T):
if T is None:
return 0
else:
return 1 + taille(T.g) + taille(T.d)
🌲 Activité n° 22 : Arbres binaires et POO : méthode taille2
Implémenter l’algorithme de la méthode taille2 et tester l’arbre précédent.
❇️ Solution :
def taille2(self):
"""
Méthode calculant le nombre total de nœuds de l'arbre.
"""
if self is None or self.estVide(): # Vérifie si l'arbre est vide
return 0
else:
taille_gauche = self.g.taille2() if self.g else 0
taille_droite = self.d.taille2() if self.d else 0
return 1 + taille_gauche + taille_droite
🧠 Capytale : arbre_binaire_POO_v2
3.7. ❤️ 3ème implémentation de la structure ARBRE BINAIRE avec la POO avec 2 classes ❤️
⚓︎
🌲 Activité n° 23 : Arbres binaires et POO : Méthode de Huffman simplifiée
Implémenter la structure ARBRE avec deux classes :
class Noeud:
def __init__(self, valeur , g = None, d = None):
"""
Initialise un nœud de l'arbre binaire.
valeur : contient la donnée du nœud
g : référence au sous-arbre gauche
d : référence au sous-arbre droit
"""
pass
class Arbre:
def __init__(self, noeud=None):
"""
Initialise un arbre binaire avec un nœud racine.
"""
pass
def estVide(self):
"""
Vérifie si l'arbre est vide.
"""
pass
def get_valeur(self):
"""
Retourne la valeur du nœud racine de l'arbre.
"""
pass
def get_gauche(self):
"""
Retourne le sous-arbre gauche.
"""
pass
def get_droit(self):
"""
Retourne le sous-arbre droit.
"""
pass
❇️ Solution :
class Noeud:
def __init__(self, valeur , g = None, d = None):
self.valeur = valeur
self.g = g
self.d = d
class Arbre:
def __init__(self, noeud=None):
self.noeud = noeud
def estVide(self):
return self.noeud is None
def get_valeur(self):
return self.noeud.valeur
def get_gauche(self):
"""
Retourne le sous-arbre gauche.
"""
if self.noeud:
return Arbre(self.noeud.g)
return None
#version 2 return self.noeud.g mais
# Vous accédez directement au sous-noeud gauche ou droit, sans
# le "remettre dans un objet Arbre". Cela brise un peu l'encapsulation
# de la structure : vous obtenez un objet Noeud brut, pas un Arbre,
# donc vous ne pouvez pas enchaîner les méthodes d'Arbre dessus.
def get_droit(self):
"""
Retourne le sous-arbre droit.
"""
if self.noeud:
return Arbre(self.noeud.d)
return None
# meme remarque que précédement
🧠 On peut noter que pour faire l’appel d’un attribut d’une autre classe, par exemple valeur, il faut remonter au constructeur de la classe Arbre. Ainsi on notera self.noeud.valeur dans la classe Arbre.
📝 Activité n°24 : Construire deux arbres binaires
Soit l’arbre suivant :
On veut construire cet arbre à l'aide de la classe Arbre. Le problème est que les attributs g et d ne font plus partie de cette classe et on ne peut plus y accéder. Il faut donc rajouter une méthode qui sera un mutateur (setter).
Implanter les deux arbres :
- le premier que l'on appellera arbre (le petit)
- le deuxième sera noté T (le grand arbre ci-dessus)
On note que les constructeurs de la classe Nœud sont protégés et que pour pouvoir y accéder on utilise un setter.
❇️ Solution :
E = Noeud('E')
D = Noeud('D')
C = Noeud('C')
B = Noeud('B', D, E)
A = Noeud('A', B, C)
arbre = Arbre(A)
# Création de l’arbre T
G = Noeud('G')
F = Noeud('F',None, G)
E = Noeud('E', F, None)
D = Noeud('D')
C = Noeud('C')
# Nœud intermédiaire
B = Noeud('B', D, E)
# Racine
A = Noeud('A', B, C)
T = Arbre(A)
Activité n° 25 : Affichage des arbres
Ajouter les méthodes pour afficher les arbres Il est possible d'afficher un arbre binaire dans la console Python, pour cela, nous allons utiliser deux méthodes.
Ajouter la méthode suivante à la classe Noeud :
def __repr__(self):
return str(self.valeur) + str(self.g).replace("None", ".") + str(self.d).replace("None", ".")
Ajouter la méthode suivante à la classe Arbre :
def __str__(self):
return str(self.noeud)
Tester ensuite avec les arbres précédents.
❇️ Solution :
✅ À insérer dans les classes :
class Noeud:
...
def __repr__(self):
return str(self.valeur) + str(self.g).replace("None", ".") + str(self.d).replace("None", ".")
class Arbre:
...
def __str__(self):
return str(self.noeud)
✅ Test :
print(arbre)
print(T)
Activité n° 26 : Fonction hauteur
Implémenter la fonction hauteur Voici l’algorithme correspondant à la fonction hauteur :
HAUTEUR(T) :
si T est vide :
renvoyer 0
sinon :
renvoyer 1 + max(HAUTEUR(T du sous-arbre gauche), HAUTEUR(T du sous-arbre droit))
❇️ Solution :
def hauteur(arbre):
"""
Fonction récursive qui calcule la hauteur d'un arbre binaire.
"""
if arbre is None or arbre.estVide() : # Si l'arbre est vide, la hauteur est 0
return 0
else:
return 1 + max(hauteur(arbre.get_gauche()) if arbre.get_gauche() else 0, hauteur(arbre.get_droit()) if arbre.get_droit() else 0)
✅ Test :
print(hauteur(arbre)) # devrait afficher 3
print(hauteur(T)) # devrait afficher 5
🔎 La fonction max() permet de renvoyer la plus grande valeur des deux valeurs passées en paramètre.
➤ Par exemple : max(5, 6) renvoie 6.
Tester avec les 2 arbres précédents.
📝 Activité n° 27 : Méthode hauteur2
Implémenter maintenant la même fonctionnalité, mais en méthode de la classe Arbre.
Tester avec les deux arbres précédents.
❇️ Solution :
class Arbre:
...
def hauteur2(self):
if self.noeud is None:
return 0
else:
hauteur_gauche = self.get_gauche().hauteur2() if self.get_gauche() else 0
hauteur_droite = self.get_droit().hauteur2() if self.get_droit() else 0
return 1 + max(hauteur_gauche, hauteur_droite)
✅ Test :
print(arbre.hauteur2()) # 3
print(T.hauteur2()) # 5
📝 Activité n° 28 : Fonction taille
Implémenter la fonction taille" Voici l’algorithme de la fonction taille :
TAILLE(T) :
si T est vide :
renvoyer 0
sinon :
renvoyer 1 + TAILLE(T.gauche) + TAILLE(T.droit)
Tester avec les deux arbres précédents.
❇️ Solution :
def taille(T):
if T.noeud is None:
return 0
return 1 + taille(Arbre(T.noeud.g)) + taille(Arbre(T.noeud.d))
✅ Test :
print(taille(arbre)) # 5
print(taille(T)) # 7
📝 Activité n° 29 : Méthode taille2
Implémenter maintenant une méthode taille2() dans la classe Arbre qui réalise le même calcul que la fonction précédente.
Tester avec les deux arbres précédents.
❇️ Solution :
class Arbre:
...
def taille2(self):
if self.noeud is None:
return 0
else:
taille_gauche = self.get_gauche().taille2() if self.get_gauche() else 0
taille_droite = self.get_droit().taille2() if self.get_droit() else 0
return 1 + taille_gauche + taille_droite
✅ Test :
print(arbre.taille2()) # 5
print(T.taille2()) # 7
🧠 Capytale : arbre_binaire_dictionnaire
3.8. ❤️ Un autre code de représentation ❤️
⚓︎
💡 Parfois, on souhaite représenter un arbre binaire autrement qu’avec une classe. Ici, on va utiliser un dictionnaire Python pour coder les liens entre les nœuds.
➡️ Exemple de codage :
A = {
'r' : ['a','b'], 'a' : ['c','d'], 'b' : ['e','f'],
'c' : ['','h'], 'd' : ['i', 'j'], 'e' : ['k',''], 'f' : ['',''],
'h' : ['',''], 'i': ['',''], 'j' : ['m',''], 'k' : ['',''], 'm' : ['','']
}
🖼️ Voici l’arbre correspondant :
📝 Activité n° 29bis : Arbres binaires avec un dictionnaire
🎯 Objectif : Implémenter deux fonctions :
hauteur(arbre, racine): calcule la hauteur de l’arbre (en nombre de niveaux)taille(arbre, racine): calcule la taille (nombre total de nœuds)
💡 Rappel :
- La hauteur correspond au plus grand nombre de noeuds entre la racine et une feuille.
- La taille correspond au nombre total de nœuds de l’arbre.
❇️ Solution :
def hauteur(arbre, racine):
"""
Calcule la hauteur d'un arbre représenté sous forme de dictionnaire.
"""
if racine == "": # Cas d'un nœud vide
return 0
gauche, droit = arbre[racine] # Récupération des enfants
return 1 + max(hauteur(arbre, gauche), hauteur(arbre, droit))
# Calcul de la hauteur et de la taille de l'arbre
print(hauteur(A, 'r')) # Devrait afficher 5
4. 👣 Le parcours en profondeur des arbres binaires
⚓︎
4.1. Les algorithmes
⚓︎
4.1.1. Le parcours préfixe (préordre)
⚓︎
👣 Ordre du parcours :
- Visite du nœud
- Parcours de la branche gauche
- Parcours de la branche droite
4.1.2. Le parcours infixe (in-ordre)
⚓︎
👣 Ordre du parcours :
- Parcours de la branche gauche
- Visite du nœud
- Parcours de la branche droite
4.1.3. Le parcours suffixe (postordre)
⚓︎
👣 Ordre du parcours :
- Parcours de la branche gauche
- Parcours de la branche droite
- Visite du nœud
🧠 Activité n° 30 : Arbre binaire et parcours en profondeur
Donner les trois parcours des sommets de l’arbre suivant :
📤 Solution
-
Parcours en préfixe (préordre) : ➤ r, a, c, h, d, i, j, l, b, e, k, f
-
Parcours en infixe (in-ordre) : ➤ h, c, a, i, d, l, j, r, k, e, b, f
-
Parcours en suffixe (postordre) : ➤ h, c, i, l, j, d, a, k, e, f, b, r
🧠 Activité n° 31 : Arbre binaire et parcours en profondeur
Voici 3 algorithmes récursifs.
Pour chacun d’eux, indique s’il correspond à un parcours préfixe, infixe, ou suffixe :
📤 Solution
- Premier algorithme : Suffixe (postordre)
- Deuxième algorithme : Préfixe (préordre)
- Troisième algorithme : Infixe (in-ordre)
🧠 Capytale : arbre_binaire_tuple_parcours
📦 4.2. Implémentation des parcours en profondeur avec les tuples
⚓︎
🧠 Activité n° 32 : Arbre binaire et parcours en profondeur :
🧠 Principe : Chaque nœud de l’arbre est représenté par un tuple de la forme (valeur, gauche, droite). On va construire l’arbre puis programmer les parcours récursifs.
Fonction parcours(arbre)
Données : arbre binaire
Si l’arbre n’est pas vide alors
parcours(sous-arbre gauche)
Afficher : la racine de l’arbre
parcours(sous-arbre droit)
Ajouter le programme principal suivant :
def noeud(e, g=None, d=None):
return e, g, d
def parcours_infixe(T):
pass
if __name__ == '__main__':
######début de la construction de l'arbre binaire###########
h = noeud('h')
c = noeud('c', None, h)
l = noeud('l')
i = noeud('i')
j = noeud('j', l)
d = noeud('d', i, j)
a = noeud('a', c, d)
k = noeud('k')
e = noeud('e', k)
f = noeud('f')
b = noeud('b', e, f)
arbre = noeud('r', a, b)
######fin de la construction de l'arbre binaire###########
📤 Solution
def noeud(e, g=None, d=None):
return e, g, d
def parcours_infixe(T):
if not T:
return None
else:
parcours_infixe(T[1])
print(T[0], end=' ')
parcours_infixe(T[2])
Implémenter le parcours infixe parcours_infixe2(arbre) sous forme de fonction de telle sorte que l’on obtienne :
>>> parcours_infixe2(arbre)
['c', 'h', 'a', 'i', 'd', 'l', 'j', 'r', 'k', 'e', 'b', 'f']
📤 Solution
def parcours_infixe2(T):
if not T:
return []
else:
return parcours_infixe2(T[1])+[T[0]]+parcours_infixe2(T[2])
print(parcours_infixe2(arbre))
Implémenter les autres parcours en profondeur.
📤 Solution
def parcours_prefixe(T):
if not T:
return []
else:
return [T[0]]+parcours_prefixe(T[1])+parcours_prefixe(T[2])
print(parcours_prefixe(arbre))
def parcours_suffixe(T):
if not T:
return []
else:
return parcours_suffixe(T[1])+parcours_suffixe(T[2])+[T[0]]
print(parcours_suffixe(arbre))
🧠 Capytale : arbre_binaire_POO_v1_parcours
📦 4.3. Implémentation des parcours en profondeur par les méthodes
⚓︎
🧠 Activité n° 33 : Arbre binaire et parcours en profondeur :
Fonction parcours(arbre)
Données : arbre binaire
Si l’arbre n’est pas vide alors
parcours(sous-arbre gauche)
Afficher : la racine de l’arbre
parcours(sous-arbre droit)
Ajouter le programme principal suivant :
class Noeud:
def __init__(self, valeur = None, g = None, d = None):
self.valeur = valeur
self.g = g
self.d= d
def estVide(self):
return self.valeur is None
def parcours_infixe(self):
pass
if __name__ == '__main__':
######début de la construction de l'arbre binaire###########
h = Noeud('h')
c = Noeud('c', None, h)
l = Noeud('l')
i = Noeud('i')
j = Noeud('j', l)
d = Noeud('d', i, j)
a = Noeud('a', c, d)
k = Noeud('k')
e = Noeud('e', k)
f = Noeud('f')
b = Noeud('b', e, f)
arbre = Noeud('r', a, b)
######fin de la construction de l'arbre binaire###########
Implémenter le parcours infixe sous forme de méthode, puis les autres parcours.
Vérifier que l’on obtient bien les parcours de l’activité précédente.
📤 Solution
class Noeud:
def __init__(self, valeur = None, g = None, d = None):
self.valeur = valeur
self.g = g
self.d= d
def estVide(self):
return self.valeur is None
def parcours_infixe(self):
if self.g:
self.g.parcours_infixe()
print(self.valeur, end=' ')
if self.d:
self.d.parcours_infixe()
def parcours_infixe2(self):
self.g.parcours_infixe2() if self.g else []
print(self.valeur, end=' ')
self.d.parcours_infixe2() if self.d else []
def parcours_infixe3(self):
gauche = self.g.parcours_infixe3() if self.g else []
droite = self.d.parcours_infixe3() if self.d else []
return gauche + [self.valeur] + droite
if __name__ == '__main__':
######début de la construction de l'arbre binaire###########
h = Noeud('h')
c = Noeud('c', None, h)
l = Noeud('l')
i = Noeud('i')
j = Noeud('j', l)
d = Noeud('d', i, j)
a = Noeud('a', c, d)
k = Noeud('k')
e = Noeud('e', k)
f = Noeud('f')
b = Noeud('b', e, f)
arbre = Noeud('r', a, b)
######fin de la construction de l'arbre binaire###########
Implémenter les parcours sous forme de fonction
📤 Solution
def parcours_infixe2(T):
if not T:
return None
else:
parcours_infixe2(T.g)
print(T.valeur, end=' ')
parcours_infixe2(T.d)
print(parcours_infixe2(arbre))
🧠 Capytale : activite_arbre_binaire_POO_v2
4.4. Implémentation des parcours en profondeur par une fonction
⚓︎
🧠 Activité n° 34 : Arbre binaire et parcours en profondeur :
Ajouter le programme principal suivant :
class Noeud:
def __init__(self, valeur, g=None, d=None):
self.valeur = valeur # Stocke la valeur du nœud
self.g = g # Stocke le sous-arbre gauche
self.d = d # Stocke le sous-arbre droit
class Arbre:
def __init__(self, noeud=None):
self.noeud = noeud # Stocke le nœud racine de l'arbre
def estVide(self):
return self.noeud is None
def get_valeur(self):
if self.noeud:
return self.noeud.valeur
def get_gauche(self):
if self.noeud:
return Arbre(self.noeud.g)
def get_droit(self):
if self.noeud:
return Arbre(self.noeud.d)
if __name__ == '__main__':
######début de la construction de l'arbre binaire###########
h = Noeud('h')
c = Noeud('c', None, h)
l = Noeud('l')
i = Noeud('i')
j = Noeud('j', l)
d = Noeud('d', i, j)
a = Noeud('a', c, d)
k = Noeud('k')
e = Noeud('e', k)
f = Noeud('f')
b = Noeud('b', e, f)
r = Noeud('r', a, b)
arbre = Arbre(r)
######fin de la construction de l'arbre binaire###########
Implémenter les 3 fonctions qui permettent de parcourir l'arbre précédent en profondeur
📤 Solution
def parcours_infixe(T):
if not T:
return None
else:
parcours_infixe(T.get_gauche())
print(T.get_valeur(), end=' ')
parcours_infixe(T.get_droit())
print(parcours_infixe(arbre))
Vérifier que l’on obtient bien les parcours de l’activité précédente.
Implémenter les 3 Méthodes par exemple parcours_infixe2() qui permettent de parcourir l'arbre précédent en profondeur
📤 Solution
def parcours_infixe2(self):
if self.get_gauche():
self.get_gauche().parcours_infixe2()
print(self.get_valeur(), end=' ')
if self.get_droit():
self.get_droit().parcours_infixe2()
def parcours_infixe3(self):
gauche = self.get_gauche().parcours_infixe3() if self.get_gauche() else []
droite = self.get_droit().parcours_infixe3() if self.get_droit() else []
return gauche + [self.get_valeur()] + droite
Vérifier que l’on obtient bien les parcours
🌳 5. Parcours en largeur d’un arbre binaire
⚓︎
👀 Le parcours en largeur consiste à explorer niveau par niveau un arbre binaire, en partant de la racine, puis en visitant successivement les fils gauche et droit, puis les enfants du nœud suivant, etc.
📊 Visualisation du parcours en largeur :
🧠 Principe de fonctionnement :
Le parcours repose sur l’utilisation d’une file (queue), selon la logique suivante :
- 🎯 On enfile l’arbre racine.
-
🔁 Tant que la file n’est pas vide :
-
On défile pour extraire le nœud en tête.
- On traite la valeur de ce nœud (visite).
- Si le fils gauche existe ➜ on l’enfile.
- Si le fils droit existe ➜ on l’enfile.
⚙️ Algorithme (schéma) :
📝 Remarque : → Au lieu d’afficher chaque élément lors de la visite, on peut les ajouter dans une liste, puis retourner cette liste complète à la fin du traitement.
🧠 Activité n° 35 : Arbre binaire et parcours en largeur
✔️ Utilise l’algorithme précédent pour vérifier que l’on obtient bien le parcours :
➤ r a b c d e f h i j k m
✅ Solution
Le parcours en largeur donné par l'algorithme doit retourner la liste suivante :
['r', 'a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm"]
🧠 Capytale : fichier arbre_binaire_tuple_parcours
📝 Activité n° 36 : Implémentation en programmation fonctionnelle (avec tuples)
📚 Structure de la file à utiliser :
from collections import deque
def file_vide():
pass
def enfiler(file, element):
pass
def est_vide(file):
pass
def defiler(file):
pass
✅ Solution
from collections import deque
def file_vide():
return deque()
def enfiler(file, element):
file.append(element)
def est_vide(file):
return len(file)==0
def defiler(file):
if not est_vide(file):
return file.popleft()
🧠 Activité n° 36bis : Arbre binaire et parcours en largeur (tuples)
Implémente la fonction de parcours en largeur en utilisant la file ci-dessus.
Vérifie que le résultat obtenu est bien conforme à celui attendu (voir activité précédente).
✅ Solution
def parcours_largeur(T):
f = file_vide()
enfiler(f, T)
while not est_vide(f):
tmp = defiler(f)
print(tmp[0], end=' ')
if tmp[1]:
enfiler(f, tmp[1])
if tmp[2]:
enfiler(f, tmp[2])
def parcours_largeur2(T):
f = file_vide()
enfiler(f, T)
s=[]
while not est_vide(f):
tmp = defiler(f)
s.append(tmp[0])
if tmp[1]:
enfiler(f, tmp[1])
if tmp[2]:
enfiler(f, tmp[2])
return s
La fonction doit retourner : ['r', 'a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l']
🧠 Capytale : fichier arbre_binaire_POO_v1_parcours
📝 Activité n° 37 : Implémentation en POO v1 (méthodes simples)
implémente le parcours en largeur sous forme de fonction extérieure utilisant la file.
📚 Structure de la file à utiliser :
from collections import deque
def file_vide():
pass
def enfiler(file, element):
pass
def est_vide(file):
pass
def defiler(file):
pass
✅ Solution
from collections import deque
def file_vide():
return deque()
def enfiler(file, element):
file.append(element)
def est_vide(file):
return len(file)==0
def defiler(file):
if not est_vide(file):
return file.popleft()
🧠 Activité n° 37bis : Arbre binaire et parcours en largeur (POO v1)
Implémente la fonction de parcours en largeur (fonction classique, pas méthode) .
✅ Solution
def parcours_largeur(T):
f = file_vide()
enfiler(f, T)
while not est_vide(f):
tmp = defiler(f)
print(tmp.valeur, end=' ')
if tmp.g:
enfiler(f, tmp.g)
if tmp.d:
enfiler(f, tmp.d)
print(parcours_largeur(arbre))
Comme précédemment, on doit obtenir la liste :
['r', 'a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm']
🧠 Capytale : fichier arbre_binaire_POO_v2_parcours
📝 Activité n° 38 : Implémentation en POO v2 (interface Arbre)
implémente à nouveau le parcours en largeur à partir de l’interface Arbre définie précédemment.
📚 Structure de la file à utiliser :
from collections import deque
def file_vide():
pass
def enfiler(file, element):
pass
def est_vide(file):
pass
def defiler(file):
pass
✅ Solution
from collections import deque
def file_vide():
return deque()
def enfiler(file, element):
file.append(element)
def est_vide(file):
return len(file)==0
def defiler(file):
if not est_vide(file):
return file.popleft()
🧠 Activité n° 38bis : Arbre binaire et parcours en largeur (POO v2)
Implémente la fonction de parcours en largeur, en utilisant la structure d’arbre objet avec interface.
✅ Solution
def parcours_largeur(T):
f = file_vide()
enfiler(f, T)
while not est_vide(f):
tmp = defiler(f)
print(tmp.noeud.valeur, end=' ')
if tmp.noeud.g is not None:
enfiler(f, Arbre(tmp.noeud.g))
if tmp.noeud.d is not None:
enfiler(f, Arbre(tmp.noeud.d))
print(parcours_largeur(arbre))
['r', 'a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k']
🧮 6. Une application de l’arbre binaire : notation polonaise inversée (RPN)
⚓︎
🧠 L’usage d’une pile est naturel lors de l’évaluation postfixée (suffixe) d’une expression algébrique.
Prenons l’exemple :
(1 + 2) × (3 − 4 / (5²))
Cette expression peut être représentée par un arbre binaire, où :
- Les nœuds internes sont des opérateurs (comme
+,-,*, etc.) - Les feuilles sont des nombres.
🌳 Représentation arborescente
🧭 Parcours postfixe
🔄 Le parcours postfixe (suffixe) d’un arbre consiste à :
- Lire d’abord le sous-arbre gauche.
- Puis le sous-arbre droit.
- Enfin, effectuer l’opération (au nœud).
📌 Pour notre expression, on obtient :
🧱 Traduction en tableau :
On encode ce parcours sous forme de liste Python :
[1, 2, '+', 3, 4, 5, 2, '**', '/', '-', '*']
✅ Cette forme évite totalement l’usage des parenthèses !
🖩 Les calculatrices HP et la notation RPN
💡 Les calculatrices HP ont historiquement utilisé cette notation, appelée RPN (Reverse Polish Notation), car les machines de l’époque ne pouvaient pas facilement analyser les parenthèses.
➡️ L’utilisateur entre les nombres dans une pile puis les opérations qui s'appliquent aux éléments du sommet.
📺 Voici une simulation du fonctionnement :
📝 Activité n° 39 : Implémentation de la RPN en Python
📌 Nous allons écrire une fonction qui évalue une expression en notation postfixée, à l’aide d’une pile.
def opere_bin(op, a, b):
"""renvoie le résultat de l'opérateur binaire op entre a et b"""
if op == '+': return a + b
if op == '-': return a - b
if op == '*': return a * b
if op == '/': return a / b
if op == '**': return a ** b
def evalue_rpn(expr):
"""évaluation postfixe de l'expression expr sous forme d'un tableau"""
pile = []
operateurs = ['+', '-', '*', '/', '**']
for elem in expr:
if elem not in operateurs:
pile.append(elem)
else:
assert pile != [], "expression mal formée"
b = pile.pop()
assert pile != [], "expression mal formée"
a = pile.pop()
pile.append(opere_bin(elem, a, b))
resultat = pile.pop()
assert pile == [], "expression mal formée"
return resultat
Python
🧪 Activité n° 39 – Test de la fonction RPN
Teste l’implémentation précédente avec la liste :
[1, 2, '+', 3, 4, 5, 2, '**', '/', '-', '*']
Que renvoie le programme ?
✅ Solution
Le calcul se fait étape par étape dans une pile : - 1 + 2 = 3 - 5 ** 2 = 25 - 4 / 25 = 0.16 - 3 - 0.16 ≈ 2.84 - 3 * 2.84 ≈ 8.52
✅ La fonction renvoie donc environ 8.52
🧠 7. Exercices
⚓︎
Exercice n°1 : Ordre préfixe**
On considère l’arbre suivant :
On parcourt cet arbre en profondeur avec un ordre préfixe.
-
Quel est le résultat de l'opération obtenue si l'on tient compte des priorités opératoires, c'est-à-dire du fait que la multiplication et la division sont prioritaires sur l'addition et la soustraction?
-
Implémenter cet arbre avec la méthode de Huffman (avec les deux classe) créer une méthode qui permette d’afficher l’arbre et retrouver le résultat de la question précédente à l'aide d’une méthode qui parcourt l’arbre en profondeur (avec ordre préfixe). La méthode aura pour prototype : parcoursprofondeur(self, file = [] ) -> list.
Et l’algorithme du parcours en profondeur est :
Exercice n°2 : autre définition de hauteur**
On considère l’arbre binaire complet suivant :
Dans cet exercice, on utilisera la convention suivante : la hauteur d’un arbre binaire ne comportant qu’un nœud est 1.
Quel serait le tableau (liste de Python) associé à cet arbre et quelle en serait sa hauteur ?
Attention : pas tableau de tableaux… !!
Exercice n°3 : Dessiner des arbres**
Dessinez chacun des arbres ci-dessous. Donner pour chaque arbre, sa taille, sa hauteur et son nombre de feuilles. Δ représente l’arbre vide. On rappelle que la hauteur d’un arbre est définie comme la profondeur maximale des nœuds de l’arbre.
a. (1, ∆, ∆)
b. (2, (4, Δ, (1, (5, Δ, (3, Δ, (2, Δ, Δ))), Δ)), Δ)
c. (3, (6, Δ, (2, Δ, Δ)), (1, (5, Δ, Δ), (4, Δ, Δ)))
d. (4, (3, (6, ∆, ∆), (1, ∆, ∆)), (5, (7, ∆, ∆), (2, ∆, ∆)))
Exercice n°4 : méthode d’Eytzinger**
La méthode d’Eytzinger consiste à stocker un arbre dans une liste unique dans laquelle le fils gauche d’un nœud i est rangé dans la case 2i+1 et son fils droit dans la case 2i+2.
1. Représenter l’arbre défini par la liste [5, 2, 6, 1, 4, Δ, 7].
2. Quelle liste représente cet arbre ?
Exercice n°5 : encadrements**
1. La hauteur d’un arbre binaire est égale à 4.
a. Encadrer son nombre de feuilles.
b. Encadrer sa taille.
2. Mêmes questions avec un arbre de hauteur h.
3. Quelle peut être la hauteur d’un arbre binaire de taille 10 ? de taille 100 ? de taille t ?
Exercice n°6 : parcours**
On affiche les sommets de l’arbre de l’exercice 5 en suivant un parcours en profondeur. Dans quel ordre vont-ils s’afficher :
a. Avec un parcours infixe ?
b. Avec un parcours préfixe ?
c. Avec un parcours suffixe ?
Exercice n°7 : parcours infixe**
Construire cinq arbres différents de taille 3, dont les nœuds contiennent les valeurs a, b, c pour lesquels le parcours infixe affiche à chaque fois a – b – c dans cet ordre.
Exercice n°8 : compléter des arbres**
- Recopier et compléter l’arbre ci-dessous pour que son parcours suffixe affiche dans l’ordre les lettres
I N G E N I E U R.
- Construire de même un arbre dont le parcours infixe affiche G A U F F R E.
- Construire un arbre dont le parcours préfixe affiche É P E R V I E R.
Exercice n°9 : le compte est bon**
On utilise des arbres pour représenter des expressions arithmétiques, par exemple pour programmer un solveur du jeu « le compte est bon ».
Donner l’affichage produit par chacun des trois parcours en profondeur.
Quel parcours renvoie un affichage de l’expression sous sa forme habituelle, en rajoutant si besoin des parenthèses ?
Les deux autres affichages correspondent à la notation polonaise et à la notation polonaise inversée. Ces notations permettent de représenter des expressions arithmétiques sans parenthèses.
🚧 8. Projets
⚓︎
Projet n°1 : arbre binaire :**
=> CAPYTALE Le code vous sera donné par votre enseignant
Commençons par étudier les arbres binaires, en utilisant une définition récursive : un arbre binaire est
- soit un arbre vide (que l’on codera par None en Python)
- soit un nœud ayant une étiquette, et deux arbres qu’on appelle enfant gauche et enfant droit.
On choisit d’implémenter de tels arbres binaires à l’aide de la classe suivante, où on utilise des valeurs par défaut dans le constructeur pour les deux enfants :
class BinaryTree:
def __init__(self, label : str, left_child=None, right_child=None):
self.__label = str(label)
self.__left = left_child # None ou un arbre de la classe BinaryTree
self.__right = right_child # None ou un arbre de la classe BinaryTree
1. Sur Thonny : Créer un fichier Python binaryTree.py.
2. Utiliser cette classe pour stocker les arbres t1, t2 et t3 suivants :
| t1 | t2 | t3 |
|---|---|---|
 |
 |
 |
3. Ajouter une méthode publique is_leaf() testant si l’arbre est une feuille dont le prototype est is_leaf(self) -> bool.
4. La question du parcours de l’ensemble des nœuds d’un arbre est cruciale, en particulier pour l’affichage. Rajouter la méthode __repr__ d’affichage de l’ensemble des informations stockées dans l’arbre qui associe par exemple à l’arbre t3 ci-dessus la chaîne : <3,<4,<>,<2>>,<7,<6>,<5,<1>,<0>>>>.
def is_leaf(self):
""" fonction testant si l'arbre est une feuille"""
return not self.__left and not self.__right
def __repr__(self):
if self.is_leaf():
return "<" + str(self.__label) + ">"
left = "<>" if self.__left is None else self.__left.__repr__()
right = "<>" if self.__right is None else self.__right.__repr__()
return "<{0},{1},{2}>".format(self.__label, left, right)
Tester la méthode précédente avec l’arbre t3.
5. Valider les tests unitaires suivants, pour les arbres t1 et t3 donnés respectivement ci-dessus :
str(t1) == "<3,<4>,<7>>"
str(t3) == "<3,<4,<>,<2>>,<7,<6>,<5,<1>,<0>>>>"
7. Valider les tests unitaires suivants, pour les arbres t1, t2 et t3 donnés respectivement ci-dessus.
t1.height() == 1
t2.height() == 2
t3.height() == 3
9. Valider le test unitaire suivant, pour l’arbre t3.
t3.prefix_traversal() == ['3', '4', '2', '7', '6', '5', '1', '0']
11. Valider le test unitaire suivant, pour l’arbre t3.
t3.infix_traversal() == ['4', '2', '3', '6', '7', '1', '5', '0']
13. Valider le test unitaire suivant, pour l’arbre t3.
t3.postfix_traversal() == ['2', '4', '6', '1', '0', '5', '7', '3']
15. Valider le test unitaire suivant, pour l’arbre t3.
t3.width_traversal() == ['3', '4', '7', '2', '6', '5', '1', '0']
Projet n°2 : Notation RPN :**
=> CAPYTALE Le code vous sera donné par votre enseignant
Le parcours en profondeur infixe permet de modéliser des expressions arithmétiques au prix de l’absence de parenthèses (voir cours).
On peut cependant se passer de parenthèses en changeant l’ordre d’apparition des éléments de l’expression arithmétique. On parle alors de notation polonaise inversée, qui correspond en fait à un parcours postfixe (ou suffixe) de l’arbre binaire : on imprime l’étiquette du nœud après avoir imprimé l’enfant gauche puis l’enfant droit.
1. Sur Thonny : Créer un fichier Python rpn.py.
2. Sur Thonny : On importera le fichier binaryTree de l’exercice précédent.
Aide si le fichier est sur le bureau:
import sys
sys.path.append("C:\\Documents and Settings\\Administrateur\\Bureau")
from mon_module_qui_est_sur_le_bureau import *
# ou import mon_module_qui_est_sur_le_bureau
ou on recopiera le code du fichier de l'exercice précédent.
3. Créer une classe RPN avec :
-
un constructeur __init__() initialisant l’attribut privé pile qui est initialisée avec la chaîne du parcours postfixe de l’arbre binaire passée en paramètre au constructeur. Le prototype de la méthode est __init__(self, expression : object).
-
une méthode spéciale __repr__() qui affiche les étiquettes séparées par des espaces pour améliorer la lisibilité : par exemple, l’expression arithmétique (5+4)×(3−(2+1)) s’affichera sous la forme “5 4 + 3 2 1 + - ×”.
Astuce : on pourra utiliser la méthode strip().
Voici l’arbre qui permet d’implémenter l’expression arithmétique : (5+4)×(3−(2+1)).
4. Créer l’arbre qui implémentera l’expression arithmétique (5+4)×(3−(2+1)).
5. Vérifier que l’on obtient bien ['5', '4', '+', '3', '2', '1', '+', '-', 'x'].
Les calculatrices Hewlett-Packard proposaient à leurs utilisateurs d’entrer les expressions arithmétiques à calculer à l’aide de la notation polonaise inversée.