Bonjour à toutes et à tous ! 🤩 Aujourd’hui, on va explorer un sujet super cool et très utile en informatique : les arbres binaires et l’arborescence ! Accrochez-vous, ça va être clair, amusant et vous allez voir que c’est partout autour de nous !
🏉 Le tournoi de rugby : une histoire d’arbres !
Imaginez que vous êtes l’organisateur d’un grand tournoi de rugby. Au début, tout est simple : 4 poules de 4 équipes, et les 2 meilleures de chaque poule se qualifient pour les quarts de finale. Jusque-là, tout va bien ! Mais quand il faut expliquer aux spectateurs comment on passe des quarts aux demies, et des demies à la finale, c’est la panique générale ! 🤯
Voici les équipes qualifiées :
- Poule 1 : 1er Eq1 ; 2e Eq8
- Poule 2 : 1er Eq2 ; 2e Eq7
- Poule 3 : 1er Eq3 ; 2e Eq6
- Poule 4 : 1er Eq4 ; 2e Eq5
Les quarts de finale sont :
- Quart 1 : Eq1 contre Eq5
- Quart 2 : Eq2 contre Eq6
- Quart 3 : Eq3 contre Eq7
- Quart 4 : Eq4 contre Eq8
Et les demi-finales :
- Demi-finale 1 : Vainqueur Quart 1 contre Vainqueur Quart 3
- Demi-finale 2 : Vainqueur Quart 2 contre Vainqueur Quart 4
C’est là que les choses se compliquent ! Pour un spectateur lambda, c’est un vrai casse-tête de suivre tout ça. Et si on utilisait un graphique ? Un truc simple qui montre qui joue contre qui, et comment on arrive à la finale ?
S’ouvre dans une nouvelle fenêtre
Licensed by Google
Bingo ! Ce type de graphique, c’est ce qu’on appelle une structure en arbre ! Ça simplifie énormément la compréhension des liens hiérarchiques. Les spectateurs peuvent facilement visualiser le chemin vers la gloire ! 🏆
🌳 Mais qu’est-ce qu’un arbre en informatique ?
Vous avez déjà croisé des arbres sans le savoir ! Pensez à un arbre généalogique : vous êtes un « fils » de vos parents, qui sont eux-mêmes les « fils » de leurs parents, et ainsi de suite. C’est une structure hiérarchique parfaite !
S’ouvre dans une nouvelle fenêtre
Licensed by Google
Lovely family tree with decorative flowers
Un autre exemple que vous avez vu l’année dernière : les systèmes de fichiers de votre ordinateur (comme sur Linux ou macOS). Vous avez un dossier principal (la « racine »), et à l’intérieur, d’autres dossiers et fichiers. Certains sont plus « profonds » que d’autres. On ne peut pas représenter cette hiérarchie juste avec une simple liste de noms !
Les arbres sont des structures de données super puissantes et très utilisées en informatique parce qu’elles permettent d’organiser des informations de manière hiérarchique. Ça veut dire qu’il y a des relations de « parent-enfant » ou de « supérieur-inférieur » entre les données. Parfois, il y a une notion de temps (comme pour le tournoi : les quarts avant les demies), mais ce n’est pas toujours le cas (le système de fichiers n’a pas de dimension temporelle).
🌲 Les arbres binaires : la version VIP des arbres !
Dans le grand monde des arbres, il y a une catégorie très spéciale et très populaire : les arbres binaires. Notre arbre de tournoi de rugby est un arbre binaire, et l’arbre « père, mère… » aussi. Par contre, le système de fichiers n’en est pas un.
Alors, quelle est la règle d’or d’un arbre binaire ? C’est simple : chaque élément (appelé « nœud ») peut avoir au maximum DEUX branches qui partent de lui. Pas plus ! Dans notre système de fichiers, la racine a beaucoup plus que deux branches qui partent d’elle, donc ce n’est pas un arbre binaire.
Dans la suite, on va se concentrer uniquement sur ces stars : les arbres binaires !
🗣️ Le dico de l’arbre binaire : du vocabulaire à connaître !
Pour ne pas se perdre, voici un petit glossaire des termes clés quand on parle d’arbres binaires. Regardons cet arbre ensemble :
- Nœud : C’est un élément de l’arbre. Pensez à chaque bulle dans notre schéma (A, B, C, D, etc.) comme un nœud. C’est l’unité de base de notre arbre.
- Racine : C’est le tout premier nœud de l’arbre, celui par où tout commence. C’est un peu le « chef » de l’arbre ! Dans notre exemple, c’est le nœud A.
- Fils : Si un nœud a des éléments qui partent de lui, ce sont ses « fils ». Par exemple, les nœuds E et D sont les fils du nœud B.
- Père : Le contraire de fils ! Le nœud B est le père des nœuds E et D. Chaque nœud (sauf la racine) a un seul père.
- Feuille : Un nœud qui n’a aucun fils. C’est la fin du chemin pour ce nœud ! Dans notre exemple, D, H, N, O, J, K, L, P et Q sont des feuilles. Ils n’ont personne « en dessous » d’eux.
- Sous-arbre : À partir d’un nœud (qui n’est pas une feuille), on peut imaginer un « mini-arbre » formé par ce nœud et tous ses descendants. Dans un arbre binaire, on parle de sous-arbre gauche et de sous-arbre droit. Par exemple, à partir de C, le sous-arbre gauche contient F, J et K, et le sous-arbre droit contient G, L, M, P et Q.
- Arête : C’est le trait qui relie deux nœuds. C’est le « chemin » entre eux.
- Taille d’un arbre : C’est tout simplement le nombre total de nœuds qu’il contient. Comptez-les tous !
- Profondeur d’un nœud : C’est la distance entre la racine et ce nœud. On compte le nombre de nœuds sur le chemin.
- Attention : Parfois, la racine est à la profondeur 1, parfois à 0. C’est une convention ! Dans ce cours, on va dire que la profondeur de la racine est 1. Donc, si la racine est à 1, un nœud juste en dessous (ses fils) sera à 2, et ainsi de suite.
- Exemples (avec racine à profondeur 1) : profondeur de B = 2 ; profondeur de I = 4 ; profondeur de P = 5.
- Hauteur d’un arbre : C’est la plus grande profondeur parmi tous les nœuds de l’arbre. En gros, c’est la profondeur de la feuille la plus « basse » de l’arbre.
- Avec notre convention (racine à profondeur 1), la hauteur de notre arbre est 5 (car P est à la profondeur 5).
🔄 Les arbres sont des structures récursives !
C’est un point super important : les arbres sont comme des poupées russes ! Un nœud, avec ses sous-arbres gauche et droit, peut être vu comme un arbre en lui-même. Et ces sous-arbres sont eux-mêmes des arbres, et ainsi de suite jusqu’aux feuilles. Cette idée de « structure qui contient des structures du même type » est la base de la récursivité, un concept clé en informatique.
🎨 Des arbres de toutes les formes !
On peut avoir des arbres de même taille qui ont des formes très différentes. Regardez ces deux exemples :
- L’arbre 1 est dit « filiforme » (ou dégénéré). Il ressemble à une longue chaîne. C’est un peu le « serpent » des arbres !
- L’arbre 2 est dit « complet« . Tous ses nœuds, sauf les feuilles, ont deux fils, et toutes les feuilles sont à la même profondeur. C’est un peu le « buisson » bien taillé ! 🌳
On dit que l’arbre 1 est déséquilibré et l’arbre 2 est équilibré. L’équilibre est important pour l’efficacité de certains algorithmes, comme on le verra.
Quelques maths pour les pros ! 🤓
- Pour un arbre filiforme de taille n, sa hauteur h est n−1 (si on considère que la racine est à profondeur 0).
- Pour un arbre complet de taille n, sa hauteur h est lfloorlog_2(n)rfloor (la partie entière de log_2(n)). Pour l’arbre 2 (taille 7), log_2(7)approx2.8, donc sa hauteur est 2.
- Pour n’importe quel arbre binaire de taille n et de hauteur h, on a toujours : lfloorlog_2(n)rfloorlehlen−1.
🧑💻 Arbres binaires en Python : on va les construire !
Python ne propose pas d’arbres binaires « prêts à l’emploi », mais pas de panique ! Plus tard dans l’année, nous allons apprendre à les implémenter nous-mêmes en utilisant la programmation orientée objet. C’est un excellent moyen de comprendre comment ça marche « sous le capot » ! 🛠️
🚀 Les algorithmes sur les arbres binaires : L’aventure continue !
Maintenant que nous maîtrisons le vocabulaire, il est temps de passer à l’action ! Comment manipuler ces arbres ? On va découvrir des algorithmes super utiles.
Chaque nœud d’un arbre binaire a :
- Une clé (ou valeur) : c’est l’information qu’il contient.
- Un sous-arbre gauche : le « mini-arbre » de gauche.
- Un sous-arbre droit : le « mini-arbre » de droite.
Regardons cet arbre :
- Pour le nœud A (la racine) :
- Son sous-arbre gauche contient B, C, D, E.
- Son sous-arbre droit contient F, G, H, I, J.
- Pour le nœud B :
- Son sous-arbre gauche contient C, E.
- Son sous-arbre droit contient D.
- Un arbre (ou un sous-arbre) vide est représenté par NIL (du latin nihil, qui veut dire « rien »). Si on prend le nœud G :
- Son sous-arbre gauche contient I.
- Son sous-arbre droit est vide (NIL).
Retenez bien : un sous-arbre, même s’il n’a qu’un seul nœud ou qu’il est vide, est toujours considéré comme un arbre !
En général, pour un arbre T et un nœud x :
T.racine
: c’est le nœud racine de l’arbre T.x.gauche
: c’est le sous-arbre gauche du nœud x.x.droit
: c’est le sous-arbre droit du nœud x.x.clé
: c’est la valeur stockée dans le nœud x.
Et si un nœud x est une feuille, alors x.gauche
et x.droit
sont des arbres vides (NIL).
📏 Calculer la hauteur d’un arbre : l’algorithme magique !
On se souvient de la hauteur ? C’est la profondeur maximale ! Comment la calculer de manière automatique ? Voici un algorithme récursif :
VARIABLE
T : arbre
x : noeud
DEBUT
HAUTEUR(T) :
si T ≠ NIL : // Si l'arbre n'est pas vide
x ← T.racine // On prend le noeud racine
// La hauteur est 1 (pour le noeud actuel) + le max des hauteurs de ses sous-arbres
renvoyer 1 + max(HAUTEUR(x.gauche), HAUTEUR(x.droit))
sinon : // Si l'arbre est vide
renvoyer 0
fin si
FIN
À faire vous-même 1 Prenez l’arbre ci-dessus et essayez d’appliquer cet algorithme « à la main » ! C’est un super exercice pour comprendre la récursivité en action. N’hésitez pas à dessiner les étapes sur un brouillon. Si vous êtes bloqués, c’est normal, la récursivité peut être un peu tricky au début ! 😉
🔢 Calculer la taille d’un arbre : compter les nœuds !
On veut maintenant savoir combien de nœuds il y a dans un arbre. C’est très similaire au calcul de la hauteur !
VARIABLE
T : arbre
x : noeud
DEBUT
TAILLE(T) :
si T ≠ NIL : // Si l'arbre n'est pas vide
x ← T.racine // On prend le noeud racine
// La taille est 1 (pour le noeud actuel) + la taille du sous-arbre gauche + la taille du sous-arbre droit
renvoyer 1 + TAILLE(x.gauche) + TAILLE(x.droit)
sinon : // Si l'arbre est vide
renvoyer 0
fin si
FIN
À faire vous-même 2 Appliquez cet algorithme sur l’arbre ci-dessus. Vous devriez le trouver un peu plus simple que le précédent !
🚶 Parcourir un arbre : faire le tour du propriétaire !
Parcourir un arbre, ça veut dire visiter tous ses nœuds, mais dans un ordre bien précis. Il existe plusieurs façons de faire ce « tour du propriétaire ». On va en explorer quelques-unes.
Parcours infixe (ou en « ordre central »)
Cet algorithme visite d’abord le sous-arbre gauche, puis le nœud actuel, puis le sous-arbre droit. C’est comme une visite guidée équilibrée !
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-INFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-INFIXE(x.gauche) // Visite le sous-arbre gauche
affiche x.clé // Affiche la clé du noeud actuel
PARCOURS-INFIXE(x.droit) // Visite le sous-arbre droit
fin si
FIN
À faire vous-même 3 Vérifiez qu’en appliquant cet algorithme sur l’arbre ci-dessus, l’ordre d’affichage est bien : C, E, B, D, A, I, G, F, H, J.
Parcours préfixe (ou en « ordre de profondeur »)
Ici, on visite d’abord le nœud actuel, puis le sous-arbre gauche, puis le sous-arbre droit. On « affiche » avant d’explorer !
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-PREFIXE(T) :
si T ≠ NIL :
x ← T.racine
affiche x.clé // Affiche la clé du noeud actuel
PARCOURS-PREFIXE(x.gauche) // Visite le sous-arbre gauche
PARCOURS-PREFIXE(x.droit) // Visite le sous-arbre droit
fin si
FIN
À faire vous-même 4 Vérifiez qu’en appliquant cet algorithme sur l’arbre ci-dessus, l’ordre d’affichage est bien : A, B, C, E, D, F, G, I, H, J.
Parcours suffixe (ou en « ordre postfixe »)
Pour ce parcours, on visite d’abord le sous-arbre gauche, puis le sous-arbre droit, et enfin le nœud actuel. On « affiche » à la fin de l’exploration !
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-SUFFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-SUFFIXE(x.gauche) // Visite le sous-arbre gauche
PARCOURS-SUFFIXE(x.droit) // Visite le sous-arbre droit
affiche x.clé // Affiche la clé du noeud actuel
fin si
FIN
À faire vous-même 5 Vérifiez qu’en appliquant cet algorithme sur l’arbre ci-dessus, l’ordre d’affichage est bien : E, C, D, B, I, G, J, H, F, A.
Parcourir un arbre en largeur d’abord
Contrairement aux parcours précédents (qui explorent en profondeur), celui-ci explore niveau par niveau, de gauche à droite. Il utilise une structure de données que vous connaissez : la file (FIFO) !
VARIABLE
T : arbre
Tg : arbre
Td : arbre
x : noeud
f : file (initialement vide)
DEBUT
PARCOURS-LARGEUR(T) :
enfiler(T.racine, f) // On place la racine dans la file
tant que f non vide :
x ← defiler(f) // On retire le premier élément de la file
affiche x.clé // On l'affiche
si x.gauche ≠ NIL :
Tg ← x.gauche
enfiler(Tg.racine, f) // On ajoute le fils gauche à la file
fin si
si x.droit ≠ NIL :
Td ← x.droit
enfiler(Td.racine, f) // On ajoute le fils droit à la file
fin si
fin tant que
FIN
À faire vous-même 6 Vérifiez qu’en appliquant cet algorithme sur l’arbre ci-dessus, l’ordre d’affichage est bien : A, B, F, C, D, G, H, E, I, J.
Pourquoi parle-t-on de parcours en largeur ? Parce qu’on explore tous les nœuds d’un même niveau (ou « largeur ») avant de passer au niveau suivant. Pensez à une inondation qui se répand !
🕵️ Arbre binaire de recherche : le détective des données !
Un arbre binaire de recherche (ABR) est un type particulier d’arbre binaire, très très utile ! C’est comme un arbre binaire qui a le sens de l’ordre. Pour qu’un arbre soit un ABR, il faut trois choses :
- C’est un arbre binaire (logique !).
- Les clés des nœuds doivent pouvoir être ordonnées (on peut les comparer : « plus petit que », « plus grand que »). Imaginez des nombres ou des mots dans l’ordre alphabétique.
- La règle d’or : pour n’importe quel nœud x :
- Si un nœud y est dans son sous-arbre gauche, alors
y.clé
doit être inférieure ou égale àx.clé
. - Si un nœud y est dans son sous-arbre droit, alors
x.clé
doit être inférieure ou égale ày.clé
.
- Si un nœud y est dans son sous-arbre gauche, alors
À faire vous-même 7 Vérifiez que l’arbre ci-dessus est bien un arbre binaire de recherche. Prenez quelques nœuds au hasard et vérifiez la règle !
À faire vous-même 8 Appliquez l’algorithme de parcours infixe (qu’on a vu plus haut) sur l’arbre binaire de recherche ci-dessus. Que remarquez-vous sur l’ordre des clés affichées ? Indice : c’est magique ! ✨
🔍 Recherche d’une clé dans un ABR : plus rapide que l’éclair !
Grâce à la propriété d’ordre des ABR, on peut chercher une clé très efficacement ! C’est un peu comme la recherche dichotomique que vous avez étudiée l’année dernière, mais pour les arbres !
Voici l’algorithme de recherche (version récursive) :
VARIABLE
T : arbre
x : noeud
k : entier // La clé que l'on cherche
DEBUT
ARBRE-RECHERCHE(T,k) :
si T == NIL : // Si l'arbre est vide, la clé n'y est pas
renvoyer faux
fin si
x ← T.racine // On prend le noeud racine
si k == x.clé : // Si la clé est celle du noeud actuel, on l'a trouvée !
renvoyer vrai
fin si
si k < x.clé : // Si la clé recherchée est plus petite, on va à gauche
renvoyer ARBRE-RECHERCHE(x.gauche,k)
sinon : // Sinon (si elle est plus grande), on va à droite
renvoyer ARBRE-RECHERCHE(x.droit,k)
fin si
FIN
À faire vous-même 9 Étudiez attentivement cet algorithme. Il est un peu le couteau suisse des ABR !
À faire vous-même 10 Appliquez l’algorithme ARBRE-RECHERCHE
sur l’arbre ci-dessus. On va chercher la clé k = 13
. Tracez le chemin !
À faire vous-même 11 Appliquez l’algorithme ARBRE-RECHERCHE
sur l’arbre ci-dessus. On va chercher la clé k = 16
. Que se passe-t-il ?
L’efficacité de la recherche
- Si l’ABR est équilibré (comme notre « buisson » !), la recherche est super rapide : sa complexité est en O(log_2(n)). C’est comme la dichotomie !
- Si l’ABR est filiforme (comme notre « serpent » !), la recherche est moins rapide : sa complexité est en O(n). C’est comme une recherche linéaire dans une liste.
Un O(log_2(n)) est beaucoup plus efficace qu’un O(n) pour les grandes quantités de données ! C’est pourquoi on essaie souvent d’avoir des ABR équilibrés.
Version itérative de la recherche
On peut aussi faire la recherche sans récursion, avec une boucle tant que
:
VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE_ITE(T,k) :
x ← T.racine
tant que T ≠ NIL et k ≠ x.clé : // Tant que l'arbre n'est pas vide ET qu'on n'a pas trouvé la clé
x ← T.racine // IMPORTANT : on doit mettre à jour x AVANT de modifier T
si k < x.clé :
T ← x.gauche // On se déplace vers le sous-arbre gauche
sinon :
T ← x.droit // On se déplace vers le sous-arbre droit
fin si
fin tant que
si k == x.clé : // Si on est sorti de la boucle parce qu'on a trouvé la clé
renvoyer vrai
sinon : // Sinon, c'est qu'on est tombé sur un NIL, la clé n'est pas là
renvoyer faux
fin si
FIN
À faire vous-même 12 Étudiez cet algorithme. Comment se compare-t-il à la version récursive ?
➕ Insertion d’une clé dans un ABR : ajouter une branche !
On peut aussi ajouter de nouveaux nœuds à un ABR, tout en respectant ses règles strictes !
VARIABLE
T : arbre
x : noeud
y : noeud // Le nouveau noeud à insérer
DEBUT
ARBRE-INSERTION(T,y) :
x ← T.racine // On commence par la racine
tant que T ≠ NIL : // On parcourt l'arbre jusqu'à trouver l'endroit où insérer
x ← T.racine // IMPORTANT : on doit mettre à jour x AVANT de modifier T
si y.clé < x.clé :
T ← x.gauche // Si la clé à insérer est plus petite, on va à gauche
sinon :
T ← x.droit // Sinon, on va à droite
fin si
fin tant que
// On est sorti de la boucle, T est NIL. x est le parent potentiel du nouveau noeud.
si y.clé < x.clé : // Si la clé à insérer est plus petite que celle du parent
insérer y à gauche de x // On l'insère comme fils gauche
sinon : // Sinon (si elle est plus grande)
insérer y à droite de x // On l'insère comme fils droit
fin si
FIN
À faire vous-même 13 Étudiez attentivement cet algorithme. Il montre comment maintenir l’ordre d’un ABR lors d’une insertion.
À faire vous-même 14 Appliquez l’algorithme ARBRE-INSERTION
sur l’arbre ci-dessus. On va insérer un nouveau nœud avec la clé y.clé = 16
. Où va-t-il se placer ?
Voilà, vous avez maintenant toutes les bases pour comprendre les arbres binaires et l’arborescence ! C’est une structure fondamentale en informatique, qui sert à organiser des données de manière efficace. Des tournois de rugby aux fichiers de votre ordinateur, les arbres sont partout !
💾 XML et JSON : les langages secrets du web (et des données) !
Vous avez vu comment les arbres nous aident à organiser des données de manière hiérarchique. Eh bien, dans le monde réel de l’informatique, il y a des formats super populaires qui utilisent cette idée pour échanger des données entre différentes applications, ou pour stocker des informations. Ce sont le XML et le JSON ! Ils sont un peu comme les « langages secrets » que les ordinateurs utilisent pour se parler et se comprendre.
Imaginez que vous êtes un chef et que vous voulez envoyer la recette de votre plat le plus incroyable à un ami. Vous ne pouvez pas juste lui envoyer une image, il a besoin des ingrédients, des quantités, des étapes… Bref, des données structurées ! XML et JSON sont ces « formats de recette » super précis.
📝 XML : l’ancêtre bavard des balises
Le XML (pour eXtensible Markup Language) est un peu le grand-père des formats d’échange de données. Il est né pour être très précis, très formel, et on le reconnaît tout de suite à ses balises !
Pensez aux balises HTML que vous avez peut-être déjà vues (<p>
, <h1>
, <img>
). XML, c’est le même principe, mais vous pouvez inventer vos propres balises ! C’est ce qui le rend « extensible ».
Voici à quoi ressemble notre recette de grand chef en XML :
XML
<recette>
<nom>Gâteau au chocolat super gourmand</nom>
<temps_preparation unite="minutes">15</temps_preparation>
<temps_cuisson unite="minutes">30</tempssson>
<ingredients>
<ingredient>
<nom>Chocolat noir</nom>
<quantite unite="grammes">200</quantite>
</ingredient>
<ingredient>
<nom>Farine</nom>
<quantite unite="grammes">100</quantite>
</ingredient>
<ingredient>
<nom>Oeufs</nom>
<quantite unite="unités">4</quantite>
</ingredient>
</ingredients>
<etapes>
<etape numero="1">Faire fondre le chocolat.</etape>
<etape numero="2">Mélanger les œufs et la farine.</etape>
<etape numero="3">Incorporer le chocolat fondu.</etape>
</etapes>
</recette>
Ce qu’il faut retenir du XML :
- Hiérarchique comme un arbre : Chaque balise (
<recette>
,<ingredients>
,<ingredient>
) peut contenir d’autres balises, créant une structure en arbre ! C’est comme les nœuds et les sous-arbres que nous avons vus. - Balises de début et de fin : Pour chaque élément, vous avez une balise d’ouverture (
<nom>
) et une balise de fermeture (</nom>
). C’est ce qui le rend verbeux (il y a beaucoup de caractères). - Attributs : On peut ajouter des informations directement sur les balises (comme
unite="minutes"
pourtemps_preparation
). - Lisible par l’humain : Même si c’est un peu long, on comprend ce que ça veut dire.
- Strict : Il y a des règles très précises à respecter pour que le XML soit « bien formé » (par exemple, pas de balise oubliée).
Le XML est encore très utilisé, surtout dans les systèmes d’entreprise où la validation des données est primordiale.
🚀 JSON : le petit nouveau léger et agile
Le JSON (pour JavaScript Object Notation) est arrivé plus tard et a gagné en popularité grâce à sa simplicité et sa légèreté. Il est devenu le chouchou du web et des applications mobiles pour échanger des données. Il est inspiré de la façon dont les objets sont structurés en JavaScript, mais il est universel.
Reprenons notre recette, cette fois en JSON :
JSON
{
"nom": "Gâteau au chocolat super gourmand",
"temps_preparation": {
"valeur": 15,
"unite": "minutes"
},
"temps_cuisson": {
"valeur": 30,
"unite": "minutes"
},
"ingredients": [
{
"nom": "Chocolat noir",
"quantite": {
"valeur": 200,
"unite": "grammes"
}
},
{
"nom": "Farine",
"quantite": {
"valeur": 100,
"unite": "grammes"
}
},
{
"nom": "Oeufs",
"quantite": {
"valeur": 4,
"unite": "unités"
}
}
],
"etapes": [
"Faire fondre le chocolat.",
"Mélanger les œufs et la farine.",
"Incorporer le chocolat fondu."
]
}
Ce qu’il faut retenir du JSON :
- Deux structures de base :
- Objets : des paires « clé-valeur » entourées d’accolades
{}
. Les clés sont des chaînes de caractères (entre guillemets) et les valeurs peuvent être des nombres, des chaînes de caractères, des booléens,null
, d’autres objets ou des tableaux. C’est l’équivalent des nœuds avec des attributs en XML. - Tableaux (ou listes) : des collections de valeurs ordonnées, entourées de crochets
[]
. C’est l’équivalent d’une liste d’éléments similaires (comme nos ingrédients ou nos étapes).
- Objets : des paires « clé-valeur » entourées d’accolades
- Moins verbeux que le XML : Moins de caractères à écrire, ce qui est pratique pour la vitesse de transmission des données.
- Très populaire : C’est le format le plus courant pour les API web (Application Programming Interface), c’est-à-dire quand des applications communiquent entre elles sur Internet.
- Facile à analyser (parser) : Les langages de programmation (comme Python !) ont des outils intégrés qui rendent très facile la lecture et l’écriture de JSON.
Le JSON, avec sa simplicité et sa légèreté, est devenu le roi de l’échange de données sur le web.
🆚 XML vs JSON : qui gagne le match ?
Ce n’est pas vraiment une compétition, ils ont tous les deux leurs points forts !
Caractéristique | XML | JSON |
Philosophie | Langage de balisage extensible | Notation d’objets pour JavaScript (mais universel) |
Syntaxe | Balises <element> et </element> | {} pour objets, [] pour tableaux |
Lisibilité | Très lisible, mais verbeux | Très lisible, plus concis |
Taille des fichiers | Généralement plus grands | Généralement plus petits |
Utilisation typique | Configuration, documents complexes, SOAP | API web, applications mobiles, NoSQL |
Modèle de données | Arbre hiérarchique | Paires clé-valeur et tableaux |
Exporter vers Sheets
En gros, les deux formats permettent de représenter des données structurées sous forme hiérarchique, exactement comme un arbre ! Le choix entre l’un ou l’autre dépend souvent du contexte et des exigences du projet. Pour la NSI, il est important de connaître les deux car ils illustrent parfaitement l’importance de l’arborescence dans l’organisation des données.
Et voilà, vous êtes maintenant incollables sur les formats XML et JSON, et vous comprenez mieux leur lien avec les arbres
Les défis des arbres binaires et des données structurées !
Exercice 1 : Les Arbres Bâtisseurs 🌳
Le défi : Dessiner toutes les formes possibles d’arbres binaires pour un nombre donné de nœuds. C’est comme être un architecte d’arbres !
Prérequis :
- Comprendre la définition d’un arbre binaire (chaque nœud a au maximum deux fils).
- Savoir ce qu’est un nœud.
Consignes : Dessine tous les arbres binaires différents qui ont :
- 3 nœuds
- 4 nœuds
Indice : La forme compte ! Deux arbres sont différents si leur structure n’est pas la même, même si les nœuds n’ont pas de noms spécifiques.
Solution :
- Pour 3 nœuds (il y en a 5) :
- Le « peigne » à gauche : Nœud central, un fils gauche, et ce fils gauche a un autre fils gauche.
- Le « peigne » à droite : Nœud central, un fils droit, et ce fils droit a un autre fils droit.
- La « branche » gauche et droite : Nœud central, un fils gauche, et ce fils gauche a un fils droit.
- La « branche » droite et gauche : Nœud central, un fils droit, et ce fils droit a un fils gauche.
- L’arbre « complet » (ou presque) : Nœud central, un fils gauche, un fils droit.
- Pour 4 nœuds (il y en a 14) : C’est un peu plus complexe ! Les 5 formes de 3 nœuds peuvent être étendues de diverses manières. Pensez aux variations en ajoutant le quatrième nœud comme fils gauche ou droit d’une feuille existante, ou en transformant une feuille en nœud interne.
Exercice 2 : La Pyramide de Catalan 🔢
Le défi : Sans les dessiner tous, deviner combien d’arbres binaires différents on peut construire avec 5 nœuds. C’est un peu comme une énigme mathématique !
Prérequis :
- Aucun prérequis spécifique en dehors de la logique. C’est un exercice de reconnaissance de suite !
Informations données :
- 0 nœud : 1 arbre (l’arbre vide)
- 1 nœud : 1 arbre
- 2 nœuds : 2 arbres
- 3 nœuds : 5 arbres
- 4 nœuds : 14 arbres
Consignes : Calcule le nombre d’arbres binaires différents contenant 5 nœuds.
Solution : Cette suite est célèbre en mathématiques ! Il s’agit des nombres de Catalan. Pour trouver le nombre d’arbres binaires distincts avec n nœuds, on utilise la formule C_n=frac1n+1binom2nn.
- Pour n=0, C_0=frac11binom00=1times1=1
- Pour n=1, C_1=frac12binom21=frac12times2=1
- Pour n=2, C_2=frac13binom42=frac13times6=2
- Pour n=3, C_3=frac14binom63=frac14times20=5
- Pour n=4, C_4=frac15binom84=frac15times70=14
Pour n=5, on calcule : C_5=frac15+1binom2times55=frac16binom105
binom105=frac105(10−5)=frac1055=frac10times9times8times7times65times4times3times2times1=frac30240120=252
C_5=frac16times252=42
Il y a donc 42 arbres binaires différents contenant 5 nœuds !
Exercice 3 : L’Imprimeur d’Arbres Fous 🤯
Le défi : Écrire un algorithme qui affiche un arbre binaire d’une manière très spécifique, en utilisant des parenthèses. C’est comme traduire l’arbre en un langage mathématique !
Prérequis :
- Comprendre le concept de récursivité.
- Savoir ce qu’est un nœud, un sous-arbre gauche et un sous-arbre droit.
- Connaître la notion d’arbre vide (NIL).
Consignes : Écris une fonction affiche(T)
(où T
est l’arbre) qui respecte ces règles :
- Si l’arbre est vide, n’affiche rien.
- Si c’est un nœud, affiche :
(
suivi de son sous-arbre gauche (appel récursif), puis sa valeur, puis son sous-arbre droit (appel récursif), et enfin)
.
Exemple d’affichage attendu : Pour un arbre où ‘A’ est la racine, ‘B’ est son fils gauche, ‘C’ est le fils droit de ‘B’, et ‘D’ est le fils droit de ‘A’, on doit obtenir : ((B(C))A(D))
.
Solution :
Ceci est un parcours infixe un peu spécial !
VARIABLE
T : arbre
x : noeud
DEBUT
AFFICHE(T) :
si T ≠ NIL :
x ← T.racine
affiche "("
AFFICHE(x.gauche) // Appel récursif pour le sous-arbre gauche
affiche x.clé // Affiche la valeur du noeud actuel
AFFICHE(x.droit) // Appel récursif pour le sous-arbre droit
affiche ")"
fin si
FIN
Testons avec l’exemple ((B(C))A(D))
:
AFFICHE(A)
:- Affiche
(
- Appel
AFFICHE(B)
:- Affiche
(
- Appel
AFFICHE(NIL)
: (rien affiché) - Affiche
B
- Appel
AFFICHE(C)
:- Affiche
(
- Appel
AFFICHE(NIL)
: (rien affiché) - Affiche
C
- Appel
AFFICHE(NIL)
: (rien affiché) - Affiche
)
- Affiche
- Affiche
)
- Affiche
- Affiche
A
- Appel
AFFICHE(D)
:- Affiche
(
- Appel
AFFICHE(NIL)
: (rien affiché) - Affiche
D
- Appel
AFFICHE(NIL)
: (rien affiché) - Affiche
)
- Affiche
- Affiche
)
- Affiche
Ce qui donne bien ((B(C))A(D))
. Mission accomplie !
Exercice 4 : L’Archéologue de l’Arbre 🕵️♀️
Le défi : À partir de la « recette » parenthésée de l’exercice précédent, retrouver la forme de l’arbre. C’est l’inverse du défi précédent !
Prérequis :
- Comprendre comment l’algorithme
affiche
fonctionne (Exercice 3). - Comprendre la structure d’un arbre binaire (nœuds, sous-arbres gauche/droit).
Consignes :
- Dessine l’arbre binaire qui produit la sortie
(1((2)3))
. - De manière générale, explique comment « reconstruire » un arbre à partir de cette notation parenthésée.
Solution :
- Dessin de l’arbre
(1((2)3))
:- On cherche la valeur centrale du niveau le plus haut : c’est le
1
. Le1
est la racine. - Ce qui est à gauche du
1
(entre la première parenthèse et1
) est le sous-arbre gauche. Ici, c’est((2)3)
. - Ce qui est à droite du
1
(entre1
et la dernière parenthèse) est le sous-arbre droit. Ici, c’est vide (il n’y a rien). - Maintenant, on se concentre sur le sous-arbre gauche
((2)3)
:- La valeur centrale est
3
. C’est donc la racine du sous-arbre gauche du1
. - Ce qui est à gauche du
3
(entre la parenthèse et3
) est le sous-arbre gauche de3
. C’est(2)
. - Ce qui est à droite du
3
(entre3
et la parenthèse) est le sous-arbre droit de3
. C’est vide.
- La valeur centrale est
- Enfin, on regarde
(2)
:- La valeur est
2
. C’est la racine du sous-arbre gauche de3
. - Ses sous-arbres gauche et droit sont vides.
- La valeur est
- Racine :
1
- Fils gauche de
1
:3
- Fils droit de
1
: vide - Fils gauche de
3
:2
- Fils droit de
3
: vide - Fils gauche de
2
: vide - Fils droit de
2
: vide
- On cherche la valeur centrale du niveau le plus haut : c’est le
- Comment retrouver l’arbre général ? Cette notation est le résultat d’un parcours infixe récursif. La clé est de trouver la racine du (sous-)arbre actuel.
- Chaque ensemble de parenthèses
(...)
représente un (sous-)arbre. - À l’intérieur de ces parenthèses, l’élément qui n’est PAS entre d’autres parenthèses (ou qui n’est pas un appel récursif) est la racine de ce (sous-)arbre.
- Tout ce qui précède cette racine est son sous-arbre gauche.
- Tout ce qui suit cette racine est son sous-arbre droit.
- On applique ce principe récursivement pour les sous-arbres gauche et droit jusqu’à ce qu’on arrive à des arbres vides (qui ne sont pas affichés). C’est comme déconstruire une expression mathématique, en identifiant l’opérateur principal en premier.
- Chaque ensemble de parenthèses
Exercice 5 : Les Arbres Jumelés 👯♀️
Le défi : Apprendre à Python comment comparer deux arbres binaires pour voir s’ils sont identiques. C’est comme enseigner à l’ordinateur à reconnaître des jumeaux !
Prérequis :
- Avoir une compréhension de la programmation orientée objet (POO) en Python (classes, objets, méthodes).
- Savoir ce qu’est la méthode spéciale
__eq__
en Python (pour la comparaison==
). - Comprendre la récursivité.
- Savoir ce qu’est un arbre vide (représenté ici par
None
ouNIL
).
Consignes : Ajoute une méthode __eq__
à une classe Noeud
(ou ArbreBinaire
) qui permet de tester l’égalité entre deux arbres binaires avec l’opérateur ==
. Attention, il y a un piège !
Le piège : Deux arbres sont égaux si et seulement si :
- Ils sont tous les deux vides.
- Ou ils ont la même valeur à leur racine, et leurs sous-arbres gauches sont égaux, ET leurs sous-arbres droits sont égaux. La récursivité est votre amie ici !
Solution (en Python) :
On imagine une classe Noeud
simple :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
# Méthode __eq__ à ajouter
def __eq__(self, autre_arbre):
# Cas 1 : Si les deux sont None (arbres vides), ils sont égaux
if self is None and autre_arbre is None:
return True
# Cas 2 : Si l'un est None et l'autre non, ils sont différents
if self is None or autre_arbre is None:
return False
# Cas 3 : Les deux ne sont pas None. On compare les clés et les sous-arbres.
# Attention : la comparaison récursive des sous-arbres !
# 'self.gauche == autre_arbre.gauche' va appeler récursivement __eq__
# 'self.droit == autre_arbre.droit' va appeler récursivement __eq__
return (self.cle == autre_arbre.cle and
self.gauche == autre_arbre.gauche and
self.droit == autre_arbre.droit)
# Une méthode pour la représentation pour rendre l'affichage plus clair
def __repr__(self):
return f"Noeud({self.cle})"
Explication du piège et de la solution : Le piège classique est de ne pas gérer correctement les cas où un ou les deux arbres sont vides (None
). La solution élégante utilise la récursivité et gère les cas None
au début. Lorsque self.gauche == autre_arbre.gauche
est évalué, Python appelle automatiquement la méthode __eq__
sur ces sous-arbres, même s’ils sont None
(ce qui est géré par les premières conditions).
Exemples :
Python
# Créons quelques arbres
arbre1 = Noeud(10, Noeud(5), Noeud(15))
arbre2 = Noeud(10, Noeud(5), Noeud(15)) # Identique à arbre1
arbre3 = Noeud(10, Noeud(5), Noeud(20)) # Différent (clé droite)
arbre4 = Noeud(10, Noeud(5)) # Différent (pas de fils droit)
print(arbre1 == arbre2) # True
print(arbre1 == arbre3) # False
print(arbre1 == arbre4) # False
# Arbres vides
arbre_vide1 = None
arbre_vide2 = None
print(arbre_vide1 == arbre_vide2) # True (car les deux sont None)
# Arbre vide vs non vide
print(arbre1 == arbre_vide1) # False
Exercice 6 : L’Arbre Parfait du Constructeur 📐
Le défi : Construire un arbre binaire « parfait » d’une certaine hauteur. Un arbre parfait est un arbre binaire où tous les nœuds (sauf les feuilles) ont exactement deux fils, et toutes les feuilles sont à la même profondeur. C’est le « Carré de l’Arbre » !
Prérequis :
- Comprendre la définition d’un arbre binaire parfait.
- Maîtriser la récursivité.
- Savoir comment créer un nœud d’arbre (comme avec la classe
Noeud
de l’exercice 5).
Consignes : Écris une fonction parfait(h)
qui prend un entier h
(hauteur, ge0) et renvoie un arbre binaire parfait de cette hauteur.
- Hauteur 0 : un arbre vide (
None
). - Hauteur 1 : un seul nœud (la racine).
- Hauteur 2 : une racine, deux fils (gauche et droit).
- Etc.
Solution (en Python) :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
def __repr__(self):
# Pour visualiser l'arbre facilement (peut être amélioré)
return f"({self.gauche.__repr__() if self.gauche else 'NIL'}) {self.cle} ({self.droit.__repr__() if self.droit else 'NIL'})"
def parfait(h):
if h == 0:
return None # Un arbre de hauteur 0 est un arbre vide
else:
# La clé peut être n'importe quoi, on peut utiliser h pour l'exemple
# On construit un noeud, dont les fils sont des arbres parfaits de hauteur h-1
return Noeud(f'Niveau{h}', parfait(h-1), parfait(h-1))
# Exemples :
# print(parfait(0)) # None
# print(parfait(1)) # (NIL) Niveau1 (NIL)
# print(parfait(2)) # ((NIL) Niveau1 (NIL)) Niveau2 ((NIL) Niveau1 (NIL))
# print(parfait(3)) # (((NIL) Niveau1 (NIL)) Niveau2 ((NIL) Niveau1 (NIL))) Niveau3 (((NIL) Niveau1 (NIL)) Niveau2 ((NIL) Niveau1 (NIL)))
Explication : L’idée clé est que pour construire un arbre parfait de hauteur h
, on crée une racine, et ses deux fils doivent être des arbres parfaits de hauteur h-1
. C’est la définition même de la récursivité appliquée à la structure. Le cas de base est h=0
, où l’arbre est vide.
Exercice 7 : Le Peigne Gauche du Coiffeur 💇♂️
Le défi : Construire un arbre binaire « peigne gauche » d’une certaine hauteur. C’est l’opposé de l’arbre complet ! Chaque nœud n’a qu’un fils gauche, et son fils droit est toujours vide.
Prérequis :
- Comprendre la définition d’un arbre filiforme (ici, spécifiquement un « peigne gauche »).
- Maîtriser la récursivité.
- Savoir comment créer un nœud d’arbre (classe
Noeud
).
Consignes : Écris une fonction peigne_gauche(h)
qui prend un entier h
(hauteur, ge0) et renvoie un peigne gauche de cette hauteur.
Solution (en Python) :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
def __repr__(self):
return f"({self.gauche.__repr__() if self.gauche else 'NIL'}) {self.cle} ({self.droit.__repr__() if self.droit else 'NIL'})"
def peigne_gauche(h):
if h == 0:
return None # Un peigne de hauteur 0 est un arbre vide
else:
# La racine a un fils gauche qui est un peigne gauche de hauteur h-1
# et un fils droit vide (None)
return Noeud(f'Niveau{h}', peigne_gauche(h-1), None)
# Exemples :
# print(peigne_gauche(0)) # None
# print(peigne_gauche(1)) # (NIL) Niveau1 (NIL)
# print(peigne_gauche(2)) # ((NIL) Niveau1 (NIL)) Niveau2 (NIL)
# print(peigne_gauche(3)) # (((NIL) Niveau1 (NIL)) Niveau2 (NIL)) Niveau3 (NIL)
Explication : Le principe est similaire à parfait(h)
. Pour un peigne gauche de hauteur h
, la racine a un fils gauche qui est un peigne gauche de hauteur h-1
, et son fils droit est toujours None
. Le cas de base est h=0
pour l’arbre vide.
Exercice 8 : L’Inspecteur de Peignes 🔎
Le défi : Vérifier si un arbre donné est bien un « peigne gauche ». C’est l’inverse du défi précédent, un vrai travail d’inspecteur !
Prérequis :
- Comprendre la définition d’un peigne gauche.
- Maîtriser la récursivité.
- Savoir manipuler les arbres (classe
Noeud
, vérification deNone
pour les fils).
Consignes : Écris une fonction est_peigne_gauche(T)
qui renvoie True
si l’arbre T
est un peigne gauche, et False
sinon.
Solution (en Python) :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
def est_peigne_gauche(T):
if T is None:
return True # Un arbre vide est considéré comme un peigne gauche (hauteur 0)
# Si le fils droit n'est PAS vide, ce n'est pas un peigne gauche
if T.droit is not None:
return False
# Si le fils droit EST vide, on vérifie récursivement le sous-arbre gauche
# Si le fils gauche est aussi None, c'est une feuille qui n'a pas de fils droit,
# donc c'est OK pour un peigne.
return est_peigne_gauche(T.gauche)
# Exemples :
# peigne_ok = peigne_gauche(3)
# print(est_peigne_gauche(peigne_ok)) # True
# arbre_non_peigne = Noeud('A', Noeud('B'), Noeud('C')) # A a un fils droit
# print(est_peigne_gauche(arbre_non_peigne)) # False
# arbre_non_peigne2 = Noeud('A', Noeud('B', droit=Noeud('C'))) # B a un fils droit
# print(est_peigne_gauche(arbre_non_peigne2)) # False
# print(est_peigne_gauche(None)) # True
Explication : La fonction est récursive.
- Cas de base : Si l’arbre est vide (
T is None
), c’est un peigne gauche (le plus petit des peignes). - Condition de non-peigne : Si le nœud actuel a un fils droit (
T.droit is not None
), ce n’est PAS un peigne gauche, donc on renvoieFalse
immédiatement. - Appel récursif : Si le fils droit est bien vide, on doit juste vérifier que le sous-arbre gauche est lui-même un peigne gauche. On appelle donc
est_peigne_gauche
surT.gauche
.
Exercice 9 : Le Tour de Passe-Passe Infixe 🧙♂️
Le défi : Construire différents arbres de même taille et avec les mêmes valeurs, mais qui donnent le même résultat lors d’un parcours infixe. C’est un peu de la magie des arbres !
Prérequis :
- Comprendre le parcours infixe (
PARCOURS-INFIXE
de la leçon). - Savoir dessiner un arbre binaire.
Consignes : Donne cinq arbres binaires différents de taille 3, contenant les valeurs 1, 2, et 3, et pour lesquels un parcours infixe affiche toujours :
1
2
3
dans cet ordre.
Solution :
Un parcours infixe affiche : sous-arbre gauche, racine, sous-arbre droit. Pour que l’affichage soit 1, 2, 3
, cela signifie que le 1
est soit la racine du sous-arbre gauche le plus à gauche, soit une feuille qui est le premier élément parcouru. Le 2
sera la racine d’un sous-arbre central, et le 3
sera le dernier élément.
Voici 5 arbres différents :
- Arbre filiforme à droite (avec 1,2,3) :
- Racine : 1
- Fils droit : 2
- Fils droit de 2 : 3
- Arbre « en V inversé » (2 en haut) :
- Racine : 2
- Fils gauche : 1
- Fils droit : 3
- Arbre « virgule inversée » (2 en haut, 3 fils droit de 1) :
- Racine : 2
- Fils gauche : 1
- Fils droit de 1 : 3
(X (Y (Z)))
: Peigne gauche (Racine, fg, fg-fg)(X (Y) (Z))
: Complet (Racine, fg, fd)( (X) Y (Z))
: Asymétrique gauche (Racine, fd, fg-fd)( (X (Y)) Z)
: Asymétrique droite (Racine, fg, fd-fg)( (X) Y)
: Peigne droit (Racine, fd, fd-fd)
- Arbre 1 (Peigne gauche) :
- Nœud
3
est la racine. - Nœud
2
est le fils gauche de3
. - Nœud
1
est le fils gauche de2
.
- Nœud
- Arbre 2 (Complet) :
- Nœud
2
est la racine. - Nœud
1
est le fils gauche de2
. - Nœud
3
est le fils droit de2
.
- Nœud
- Arbre 3 (Asymétrique gauche) :
- Nœud
3
est la racine. - Nœud
1
est le fils gauche de3
. - Nœud
2
est le fils droit de1
.
- Nœud
- Arbre 4 (Asymétrique droite) :
- Nœud
1
est la racine. - Nœud
3
est le fils droit de1
. - Nœud
2
est le fils gauche de3
.
- Nœud
- Arbre 5 (Peigne droit) :
- Nœud
1
est la racine. - Nœud
2
est le fils droit de1
. - Nœud
3
est le fils droit de2
.
- Nœud
1, 2, 3
lors d’un parcours infixe. C’est fascinant, non ?
Exercice 10 : La Salle des Mystères 🧐
Le défi : Comprendre pourquoi une bibliothèque (ici, une base de données de salles) contient un nombre si précis de salles. C’est une énigme de combinaison !
Prérequis :
- Comprendre le principe des combinaisons ou des permutations simples.
- Connaître les bases de l’alphabet.
Contexte : Une bibliothèque contient 17576 salles. Chaque salle est identifiée par un code unique.
Consignes : Pourquoi la bibliothèque donnée en exemple au début de ce chapitre contient-elle 17576 salles ?
Solution :
Ce nombre nous fait penser à quelque chose qui utilise l’alphabet !
- L’alphabet latin contient 26 lettres.
- Si chaque salle est identifiée par un code, et que ce code est composé de lettres (par exemple, « AAA », « AAB », « ABA », etc.), on peut facilement obtenir ce nombre.
26times26times26=263=17576
Cela signifie que chaque salle est probablement identifiée par un code de 3 lettres majuscules (ou minuscules, selon la convention) de l’alphabet latin. C’est une combinaison simple avec répétition.
- 1ère lettre : 26 choix (A-Z)
- 2ème lettre : 26 choix (A-Z)
- 3ème lettre : 26 choix (A-Z)
Total = 26times26times26=17576.
C’est une astuce courante pour générer des identifiants uniques dans de nombreux systèmes !
Exercice 11 : Les Architectes d’ABR 🏗️
Le défi : Dessiner tous les Arbres Binaires de Recherche (ABR) possibles avec seulement trois nœuds, et contenant les valeurs 1, 2, et 3.
Prérequis :
- Comprendre la définition d’un Arbre Binaire de Recherche (ABR) (les éléments plus petits à gauche, les plus grands à droite).
- Savoir dessiner un arbre binaire.
Consignes : Dessine tous les ABR possibles formés de trois nœuds et contenant les entiers 1, 2 et 3.
Solution :
Pour un ABR, la position des éléments dépend de leur valeur. Il n’y a pas autant de formes différentes que pour les arbres binaires « normaux » avec un même nombre de nœuds.
Les 5 formes d’arbres binaires avec 3 nœuds (de l’Exercice 1) peuvent être utilisées, mais avec les contraintes des ABR, seules certaines configurations sont valides pour les valeurs 1, 2, 3.
Voici les 5 ABR uniques avec les valeurs 1, 2, 3 :
- Racine = 1 (Peigne droit) :
- Racine : 1
- Fils droit : 2
- Fils droit de 2 : 3
- Racine = 2 (Arbre complet) :
- Racine : 2
- Fils gauche : 1
- Fils droit : 3
- Racine = 3 (Peigne gauche) :
- Racine : 3
- Fils gauche : 2
- Fils gauche de 2 : 1
- Racine = 1 (1 est la racine, 3 est son fils droit, 2 est le fils gauche de 3) :
- Racine : 1
- Fils droit : 3
- Fils gauche de 3 : 2
- Racine = 3 (3 est la racine, 1 est son fils gauche, 2 est le fils droit de 1) :
- Racine : 3
- Fils gauche : 1
- Fils droit de 1 : 2
Ce sont les 5 formes possibles. Remarquez que l’ordre des valeurs dans un ABR est la clé de sa structure.
Exercice 12 : Le Chasseur de Minimum 🎯
Le défi : Trouver le plus petit élément dans un Arbre Binaire de Recherche (ABR). C’est comme chercher la petite graine au fond du jardin !
Prérequis :
- Comprendre la définition d’un ABR (les éléments plus petits sont à gauche).
- Maîtriser la récursivité ou les boucles (itératif).
- Savoir gérer les arbres vides (
None
).
Consignes :
- Dans un ABR, où se trouve le plus petit élément ?
- Écris une fonction
minimum(a)
qui renvoie le plus petit élément de l’ABRa
. - Si l’arbre
a
est vide, la fonction renvoieNone
.
Solution (en Python) :
- Où se trouve le plus petit élément ? Dans un ABR, le plus petit élément se trouve toujours tout à gauche ! On part de la racine et on descend toujours par le sous-arbre gauche jusqu’à ce qu’on ne puisse plus aller à gauche (c’est-à-dire jusqu’à atteindre une feuille ou un nœud dont le fils gauche est
None
). - Fonction
minimum(a)
(version récursive) :Pythonclass Noeud: def __init__(self, cle, gauche=None, droit=None): self.cle = cle self.gauche = gauche self.droit = droit def minimum(a): if a is None: return None # Si l'arbre est vide, pas de minimum if a.gauche is None: return a.cle # Si pas de fils gauche, le noeud actuel est le plus petit else: return minimum(a.gauche) # Sinon, on cherche dans le sous-arbre gauche
- Fonction
minimum(a)
(version itérative – avec boucletant que
) :Pythondef minimum_iteratif(a): if a is None: return None courant = a while courant.gauche is not None: courant = courant.gauche return courant.cle
Les deux versions fonctionnent parfaitement. La version itérative est parfois préférée pour éviter la profondeur de récursion sur des arbres très déséquilibrés.
Exercice 13 : L’Ajouteur Intelligent d’ABR 🧠
Le défi : Modifier l’algorithme d’insertion dans un ABR pour qu’il n’ajoute pas un élément s’il est déjà présent. C’est comme un filtre anti-doublons !
Prérequis :
- Comprendre l’algorithme d’insertion dans un ABR (vu en cours).
- Savoir gérer les cas où la clé est déjà trouvée.
- Connaître la structure de la classe
Noeud
.
Consignes : Écris une variante du programme d’insertion d’une clé dans un ABR qui n’ajoute pas l’élément x
à l’arbre a
s’il est déjà dedans.
Solution (en Python) :
On se base sur l’algorithme d’insertion vu en cours :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
def __repr__(self):
return f"Noeud({self.cle})"
def ajoute_sans_doublon(arbre, nouvelle_cle):
# Cas 1 : L'arbre est vide, la nouvelle_cle devient la racine
if arbre is None:
return Noeud(nouvelle_cle)
courant = arbre # Pointeur pour parcourir l'arbre
parent = None # Pointeur pour retenir le parent du noeud où insérer
while courant is not None:
if nouvelle_cle == courant.cle:
# La clé existe déjà, on ne fait rien et on renvoie l'arbre inchangé
return arbre
parent = courant
if nouvelle_cle < courant.cle:
courant = courant.gauche
else: # nouvelle_cle > courant.cle
courant = courant.droit
# On a trouvé l'emplacement d'insertion (courant est None, parent est le bon noeud)
if nouvelle_cle < parent.cle:
parent.gauche = Noeud(nouvelle_cle)
else:
parent.droit = Noeud(nouvelle_cle)
return arbre # On renvoie la racine de l'arbre (qui n'a pas changé)
# Exemple d'utilisation :
# arbre_test = Noeud(10, Noeud(5), Noeud(15))
# print(arbre_test)
# ajoute_sans_doublon(arbre_test, 7) # Ajoute 7
# print(arbre_test)
# ajoute_sans_doublon(arbre_test, 5) # N'ajoute pas 5 (déjà présent)
# print(arbre_test)
Explication : L’algorithme de parcours est le même que pour la recherche. La différence est que si à un moment donné nouvelle_cle == courant.cle
, on sait que l’élément est déjà là, et on s’arrête sans rien ajouter. Si on arrive à courant is None
sans avoir trouvé la clé, alors on insère le nouveau nœud comme d’habitude.
Exercice 14 : Le Compteur Flexible d’ABR ⚖️
Le défi : Compter les occurrences d’une valeur dans un ABR, même si l’ABR n’a pas été construit « proprement » (c’est-à-dire que des doublons peuvent être à gauche ou à droite de la racine). On veut être malin et ne pas chercher là où on est sûr de ne rien trouver !
Prérequis :
- Comprendre la définition d’un ABR.
- Maîtriser la récursivité.
- Savoir parcourir un arbre et prendre des décisions basées sur les valeurs.
Contexte : Dans un ABR « normal », si une clé est égale à la racine, elle ne devrait pas apparaître dans les sous-arbres gauche ou droit (selon la convention stricte y.clé < x.clé
et x.clé < y.clé
). Mais ici, on suppose que les doublons peuvent être présents à gauche OU à droite (y.clé <= x.clé
et x.clé <= y.clé
). L’objectif est de ne pas chercher inutilement.
Consignes : Écris une fonction compte(x, a)
qui renvoie le nombre d’occurrences de x
dans l’ABR a
. On ne suppose pas que l’arbre a été construit à partir de la fonction ajoute
(où les doublons seraient gérés de manière unique), mais qu’il s’agit d’un ABR (donc l’ordre est respecté). Cependant, une valeur égale à la racine peut se trouver encore dans le sous-arbre gauche OU dans le sous-arbre droit. On s’attachera à ne pas descendre dans les sous-arbres dans lesquels on est certain que la valeur x
ne peut apparaître.
Solution (en Python) :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
def __repr__(self):
return f"Noeud({self.cle})"
def compte(x, a):
if a is None:
return 0 # Si l'arbre est vide, 0 occurrences
nb_occurrences = 0
if x == a.cle:
nb_occurrences = 1 # On a trouvé une occurrence à la racine
# Cas 1 : La clé recherchée est plus petite que la clé du noeud actuel
# On peut chercher dans le sous-arbre gauche. On ne cherche PAS à droite.
if x < a.cle:
nb_occurrences += compte(x, a.gauche)
# Cas 2 : La clé recherchée est plus grande que la clé du noeud actuel
# On peut chercher dans le sous-arbre droit. On ne cherche PAS à gauche.
elif x > a.cle:
nb_occurrences += compte(x, a.droit)
# Cas 3 : La clé recherchée est ÉGALE à la clé du noeud actuel
# C'est le cas "flexible" : la clé peut être présente dans les deux sous-arbres.
# On doit donc chercher dans les DEUX sous-arbres pour les doublons.
else: # x == a.cle
nb_occurrences += compte(x, a.gauche)
nb_occurrences += compte(x, a.droit)
return nb_occurrences
# Exemple d'utilisation :
# Construisons un ABR "non strict"
# 10
# / \
# 5 15
# / \ / \
# 5 7 15 20
arbre_flexible = Noeud(10,
Noeud(5, Noeud(5), Noeud(7)),
Noeud(15, Noeud(15), Noeud(20)))
print(f"Occurrences de 5 : {compte(5, arbre_flexible)}") # Devrait être 2
print(f"Occurrences de 10 : {compte(10, arbre_flexible)}") # Devrait être 1
print(f"Occurrences de 15 : {compte(15, arbre_flexible)}") # Devrait être 2
print(f"Occurrences de 20 : {compte(20, arbre_flexible)}") # Devrait être 1
print(f"Occurrences de 8 : {compte(8, arbre_flexible)}") # Devrait être 0
Explication : La logique de recherche est similaire à celle d’un ABR « normal », mais avec une condition supplémentaire pour les doublons :
- Si
x < a.cle
, on va seulement à gauche. - Si
x > a.cle
, on va seulement à droite. - MAIS, si
x == a.cle
, on incrémente le compteur, puis on continue à chercher dans les deux sous-arbres (a.gauche
eta.droit
). C’est là la subtilité ! Cela permet de trouver toutes les occurrences dex
, même si elles sont réparties de manière non standard (mais toujours « ABR-compatible ») dans l’arbre.
Exercice 15 : L’Ordonnateur d’Arbres 📋
Le défi : Extraire tous les éléments d’un ABR et les ranger dans un tableau trié. C’est comme vider une boîte triée dans un tiroir !
Prérequis :
- Comprendre le parcours infixe d’un arbre binaire.
- Comprendre les propriétés d’un ABR (le parcours infixe les retourne dans l’ordre croissant).
- Savoir manipuler des tableaux (listes en Python).
- Avoir une classe
ABR
ouNoeud
(avec une racine).
Consignes :
- Écris une fonction
remplir(a, t)
qui ajoute tous les éléments de l’arbrea
dans le tableaut
(en utilisantt.append(x)
) dans l’ordre infixe. - Ajoute ensuite une méthode
lister(self)
à la classeABR
(ouNoeud
pour simplifier) qui renvoie un nouveau tableau contenant tous les éléments de l’ABRself
par ordre croissant.
Solution (en Python) :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
def __repr__(self):
return f"Noeud({self.cle})"
# Méthode lister à ajouter à la classe Noeud pour l'exercice
def lister(self):
resultat = []
_remplir_infixe_recursif(self, resultat) # Appel à la fonction helper
return resultat
# Partie 1 : Fonction remplir
def remplir(a, t):
if a is not None:
remplir(a.gauche, t) # Parcourt le sous-arbre gauche
t.append(a.cle) # Ajoute la clé du noeud actuel
remplir(a.droit, t) # Parcourt le sous-arbre droit
# On peut aussi encapsuler remplir comme une fonction "privée" ou helper
# pour la méthode lister
def _remplir_infixe_recursif(noeud_courant, liste_resultat):
if noeud_courant is not None:
_remplir_infixe_recursif(noeud_courant.gauche, liste_resultat)
liste_resultat.append(noeud_courant.cle)
_remplir_infixe_recursif(noeud_courant.droit, liste_resultat)
# Exemple d'utilisation :
# 10
# / \
# 5 15
# / \ /
# 3 7 12
arbre_exemple = Noeud(10,
Noeud(5, Noeud(3), Noeud(7)),
Noeud(15, Noeud(12)))
tableau_vide = []
remplir(arbre_exemple, tableau_vide)
print(f"Tableau rempli avec remplir : {tableau_vide}") # Devrait afficher [3, 5, 7, 10, 12, 15]
# Utilisation de la méthode lister (si vous avez intégré la méthode à la classe Noeud)
print(f"Tableau rempli avec lister : {arbre_exemple.lister()}") # Devrait afficher [3, 5, 7, 10, 12, 15]
Explication :
- La fonction
remplir
(ou_remplir_infixe_recursif
) est une implémentation directe du parcours infixe. L’ordre infixe sur un ABR garantit que les éléments sont visités dans l’ordre croissant. - La méthode
lister
de la classeNoeud
(ouABR
si vous en avez une) initialise un tableau vide, appelle la fonctionremplir
(ou sa version_remplir_infixe_recursif
) pour le remplir, puis renvoie ce tableau. C’est une manière élégante d’intégrer cette fonctionnalité à l’objet arbre.
Exercice 16 : Le Triage d’Arbres Magique ✨
Le défi : Utiliser un ABR pour trier un tableau d’entiers. C’est comme une baguette magique qui range vos nombres !
Prérequis :
- Avoir la fonction d’insertion dans un ABR (Exercice 13 ou sa version simple).
- Avoir la méthode
lister
(Exercice 15). - Comprendre le concept de complexité algorithmique (O(n), O(log_2(n)), etc.).
Consignes :
- En utilisant les fonctions des exercices précédents (insertion dans un ABR et
lister
), écris une fonctiontrier(t)
qui reçoit en argument un tableau d’entiers et renvoie un tableau trié contenant les mêmes éléments. - Quelle est l’efficacité de ce tri ?
Solution (en Python) :
Python
# On réutilise les classes et fonctions précédentes ou on les suppose définies
# (Noeud, ajoute_sans_doublon, _remplir_infixe_recursif)
# Assurez-vous que ajoute_sans_doublon est disponible ou utilisez une version simple d'ajout
def ajoute_simple(arbre, nouvelle_cle):
if arbre is None:
return Noeud(nouvelle_cle)
courant = arbre
parent = None
while courant is not None:
parent = courant
if nouvelle_cle < courant.cle:
courant = courant.gauche
else:
courant = courant.droit
if nouvelle_cle < parent.cle:
parent.gauche = Noeud(nouvelle_cle)
else:
parent.droit = Noeud(nouvelle_cle)
return arbre
def trier(tableau_entiers):
# Étape 1 : Créer un ABR et y insérer tous les éléments du tableau
arbre_de_tri = None
for element in tableau_entiers:
# On utilise ajoute_simple pour éviter les doublons si nécessaire,
# ou ajoute_sans_doublon pour l'exercice 13
if arbre_de_tri is None: # Cas particulier pour la première insertion
arbre_de_tri = Noeud(element)
else:
ajoute_simple(arbre_de_tri, element) # ou ajoute_sans_doublon
# Étape 2 : Lister les éléments de l'ABR en ordre infixe pour obtenir le tableau trié
# On utilise la fonction _remplir_infixe_recursif (ou la méthode lister)
tableau_trie = []
_remplir_infixe_recursif(arbre_de_tri, tableau_trie)
return tableau_trie
# Exemple d'utilisation :
tableau_initial = [5, 3, 8, 1, 9, 2, 7, 4, 6]
tableau_trie = trier(tableau_initial)
print(f"Tableau initial : {tableau_initial}")
print(f"Tableau trié (méthode ABR) : {tableau_trie}") # Devrait afficher [1, 2, 3, 4, 5, 6, 7, 8, 9]
Efficacité de ce tri :
Ce tri est appelé le tri par arbre binaire. Son efficacité dépend de la forme de l’ABR construit :
- Construction de l’arbre : Pour insérer
n
éléments, chaque insertion prend en moyenne O(log_2(n)) (si l’arbre reste équilibré) ou O(n) dans le pire des cas (si l’arbre devient filiforme). Donc, la phase de construction prend en moyenne O(nlog_2(n)) et dans le pire des cas O(n2). - Parcours infixe : Pour parcourir tous les
n
éléments de l’arbre, c’est O(n).
Complexité totale :
- En moyenne : O(nlog_2(n)). C’est très efficace, comparable à des tris comme le Quicksort ou le Mergesort.
- Dans le pire des cas (quand l’arbre devient filiforme, par exemple si les nombres sont déjà triés ou presque triés) : O(n2). C’est beaucoup moins efficace, comparable à des tris comme le tri à bulles.
Pour garantir une bonne performance dans tous les cas, il faudrait utiliser des ABR auto-équilibrés (comme les arbres AVL ou Rouge-Noir), mais c’est une autre histoire pour plus tard ! 😉
Exercice 17 : L’Affichage Indenté de l’Explorateur 🗂️
Le défi : Afficher un arbre d’une manière qui ressemble à l’explorateur de fichiers de votre ordinateur, avec une indentation qui montre la profondeur de chaque nœud.
Prérequis :
- Comprendre le parcours préfixe (racine, gauche, droite).
- Maîtriser la récursivité.
- Savoir manipuler des chaînes de caractères (ajouter des espaces pour l’indentation).
Consignes : Écris une fonction affiche(a)
qui affiche une arborescence selon un parcours préfixe, avec un nœud par ligne et une marge proportionnelle à la profondeur du nœud.
- Indication : Écris une fonction récursive qui prend un paramètre supplémentaire : une chaîne de caractères (composée d’espaces) à afficher avant la valeur du nœud.
Exemple de sortie attendue :
A
B
C
D
E
F
G
H
(Les « tabulations » sont en fait des espaces, 2 ou 4 par niveau par exemple.)
Solution (en Python) :
Python
class Noeud:
def __init__(self, cle, gauche=None, droit=None):
self.cle = cle
self.gauche = gauche
self.droit = droit
def __repr__(self):
return str(self.cle)
def affiche_arborescence(arbre, indentation=""):
if arbre is not None:
print(f"{indentation}{arbre.cle}") # Affiche le noeud actuel avec l'indentation
# Appel récursif pour le sous-arbre gauche, augmente l'indentation
affiche_arborescence(arbre.gauche, indentation + " ") # Ajoutez 2 espaces par niveau
# Appel récursif pour le sous-arbre droit, augmente l'indentation
affiche_arborescence(arbre.droit, indentation + " ")
# Exemple d'utilisation avec l'arbre du cours :
# A
# / \
# B F
# / \ / \
# C D G H
# / /
# E I
# \
# J
arbre_test = Noeud('A',
Noeud('B',
Noeud('C', Noeud('E')),
Noeud('D')),
Noeud('F',
Noeud('G', Noeud('I', droit=Noeud('J'))),
Noeud('H')))
print("Affichage de l'arborescence :")
affiche_arborescence(arbre_test)
Explication : La fonction affiche_arborescence
est récursive et suit l’ordre du parcours préfixe :
- Elle gère le cas de base (arbre vide) en ne faisant rien.
- Pour un nœud non vide, elle affiche sa
cle
en la faisant précéder de laindentation
actuelle. - Puis elle s’appelle récursivement pour le sous-arbre gauche, en augmentant l’indentation (
indentation + " "
). - Enfin, elle s’appelle récursivement pour le sous-arbre droit, avec la même indentation augmentée.
Chaque niveau de profondeur ajoute des espaces, créant ainsi l’effet d’arborescence visuelle. C’est super pratique pour débugger ou visualiser la structure d’un arbre !
Exercice 18 : L’Explorateur de Fichiers Python 📂
Le défi : Écrire un programme Python qui explore les répertoires de votre ordinateur et les représente sous forme d’arbre binaire (enfin, une arborescence générale). C’est comme créer votre propre gestionnaire de fichiers !
Prérequis :
- Comprendre le concept d’arborescence pour les systèmes de fichiers.
- Maîtriser la récursivité.
- Savoir utiliser les fonctions du module
os
de Python (os.listdir
,os.path.join
,os.path.isdir
). - Avoir la fonction d’affichage indenté de l’exercice précédent (
affiche_arborescence
).
Contexte : Les répertoires de votre ordinateur sont déjà une structure d’arbre. On va la modéliser avec notre structure d’arbre personnalisée.
Consignes :
- Écris une fonction Python
repertoires(nom_repertoire)
qui prend un nom de répertoire et renvoie une arborescence (au sens de notre classeNoeud
ou une classeRepertoire
dédiée) décrivant la structure récursive de ses sous-répertoires. - Utilise les fonctions
os.listdir()
,os.path.join()
, etos.path.isdir()
. - Teste le résultat en l’affichant avec la fonction
affiche_arborescence
de l’exercice précédent.
Solution (en Python) :
Pour cet exercice, on va adapter notre classe Noeud
pour qu’elle puisse aussi représenter des répertoires. On pourrait aussi créer une classe Repertoire
spécifique.
Python
import os
class NoeudRepertoire:
def __init__(self, nom, enfants=None):
self.nom = nom
# Pour un répertoire, 'enfants' est une liste de NoeudRepertoire
# (et non pas gauche/droit car un répertoire peut avoir plus de 2 sous-répertoires)
self.enfants = enfants if enfants is not None else []
def __repr__(self):
return self.nom
def repertoires(chemin_initial):
# On va construire un noeud pour le répertoire actuel
racine_rep = NoeudRepertoire(os.path.basename(chemin_initial))
try:
# Liste tous les éléments (fichiers et dossiers) dans le répertoire
elements = os.listdir(chemin_initial)
except PermissionError:
# Gérer les erreurs de permission pour ne pas planter le programme
print(f"Permission refusée pour accéder à : {chemin_initial}")
return racine_rep # Retourne juste le noeud sans ses enfants
# On parcourt chaque élément trouvé
for element in elements:
chemin_complet_element = os.path.join(chemin_initial, element)
# Si l'élément est un répertoire, on l'ajoute récursivement
if os.path.isdir(chemin_complet_element):
sous_repertoire_modele = repertoires(chemin_complet_element)
racine_rep.enfants.append(sous_repertoire_modele)
return racine_rep
# Fonction d'affichage adaptée pour la nouvelle structure NoeudRepertoire
def affiche_arborescence_repertoire(arbre_rep, indentation=""):
if arbre_rep is not None:
print(f"{indentation}{arbre_rep.nom}")
for enfant in arbre_rep.enfants:
affiche_arborescence_repertoire(enfant, indentation + " ")
# --- Test du programme ---
# Choisissez un répertoire de test. Attention : plus il est grand, plus ça prendra de temps !
# Un petit répertoire de test est recommandé, par exemple un dossier que vous avez créé
# avec quelques sous-dossiers et fichiers.
repertoire_a_explorer = "./mon_dossier_test" # Remplacez par un chemin réel et pertinent !
# Créez un dossier de test simple si vous n'en avez pas
if not os.path.exists(repertoire_a_explorer):
os.makedirs(os.path.join(repertoire_a_explorer, "sous_dossier1"))
os.makedirs(os.path.join(repertoire_a_explorer, "sous_dossier2", "sous_sous_dossier"))
with open(os.path.join(repertoire_a_explorer, "fichier1.txt"), "w") as f:
f.write("test")
with open(os.path.join(repertoire_a_explorer, "sous_dossier1", "fichier2.py"), "w") as f:
f.write("print('hello')")
print(f"Dossier de test '{repertoire_a_explorer}' créé.")
print(f"\nExploration de l'arborescence à partir de : {repertoire_a_explorer}")
arbre_systeme = repertoires(repertoire_a_explorer)
affiche_arborescence_repertoire(arbre_systeme)
# Nettoyage du dossier de test (optionnel)
# import shutil
# shutil.rmtree(repertoire_a_explorer)
# print(f"\nDossier de test '{repertoire_a_explorer}' supprimé.")
Explication :
- Classe
NoeudRepertoire
: On adapte la classe de nœud. Au lieu degauche
etdroit
, un répertoire peut avoirenfants
(une liste), car un dossier peut contenir plus de deux sous-dossiers. - Fonction
repertoires
:- Elle crée un
NoeudRepertoire
pour le chemin actuel. - Elle utilise
os.listdir()
pour obtenir la liste de tout ce qui se trouve dans ce répertoire. - Pour chaque élément,
os.path.join()
construit le chemin complet. os.path.isdir()
vérifie si l’élément est un répertoire.- Si c’est un répertoire, la fonction s’appelle elle-même récursivement (
repertoires(chemin_complet_element)
) pour construire le sous-arbre de ce sous-répertoire, et l’ajoute à la listeenfants
du nœud actuel. - Si c’est un fichier, on l’ignore (car l’exercice ne demande que les répertoires).
- Un bloc
try-except PermissionError
est ajouté pour gérer les accès refusés, courants dans les systèmes de fichiers.
- Elle crée un
- Fonction
affiche_arborescence_repertoire
: Elle est similaire à l’exercice précédent, mais elle itère sur la listeenfants
plutôt que d’appelergauche
etdroit
.
C’est un exemple très concret de l’application des arbres pour modéliser des structures du monde réel !
Exercice 19 : Le Détective XML 🧐
Le défi : Vérifier si des petits extraits XML sont « bien formés », c’est-à-dire s’ils respectent les règles de base de la syntaxe XML.
Prérequis :
- Comprendre les bases du format XML (balises ouvrantes, balises fermantes, attributs).
- Savoir ce qu’est un document bien formé.
Consignes : Pour chacun des petits documents XML ci-dessous, dis s’il est bien formé. Si ce n’est pas le cas, indique l’erreur.
<a></a>
<a><b></b><b></b></a>
<a><b></B></a>
<a><b></a>
<a></a><a></a>
<a><b id="45" v=’45’></b></a>
<a><b id="45" id="48"></b></a>
<a><b id="45"></b><b id="45"></b></a>
Solution :
Un document XML est bien formé s’il respecte des règles syntaxiques de base :
- Il doit y avoir un unique élément racine.
- Chaque balise ouverte doit être fermée.
- Les balises doivent être correctement imbriquées (pas de chevauchement).
- Les noms de balises sont sensibles à la casse (
<b>
n’est pas la même chose que</B>
). - Les attributs doivent avoir des valeurs entre guillemets (
" "
ou' '
). - Les noms d’attributs doivent être uniques au sein d’une même balise.
Allons-y !
<a></a>
- Bien formé. Racine unique, balise ouverte et fermée correctement.
<a><b></b><b></b></a>
- Bien formé. Racine unique (
<a>
), balises imbriquées correctement.
- Bien formé. Racine unique (
<a><b></B></a>
- NON bien formé. Erreur : Sensibilité à la casse. La balise ouvrante est
<b>
mais la balise fermante est</B>
. Les majuscules/minuscules doivent correspondre.
- NON bien formé. Erreur : Sensibilité à la casse. La balise ouvrante est
<a><b></a>
- NON bien formé. Erreur : Imbrication incorrecte. La balise
<b>
est ouverte mais n’est pas fermée avant la fermeture de<a>
. L’ordre de fermeture doit être l’inverse de l’ordre d’ouverture.
- NON bien formé. Erreur : Imbrication incorrecte. La balise
<a></a><a></a>
- NON bien formé. Erreur : Multiples racines. Un document XML doit avoir un et un seul élément racine. Ici, il y a deux éléments
<a>
au niveau le plus haut.
- NON bien formé. Erreur : Multiples racines. Un document XML doit avoir un et un seul élément racine. Ici, il y a deux éléments
<a><b id="45" v=’45’></b></a>
- NON bien formé. Erreur : Les attributs doivent avoir leurs valeurs entre guillemets doubles
" "
ou guillemets simples' '
. Ici,v=’45’
utilise une apostrophe ouvrante (’
) et une apostrophe fermante (’
) qui ne sont pas les bons caractères ASCII pour les guillemets simples (qui sont''
). En général, les guillemets doubles sont préférés.
- NON bien formé. Erreur : Les attributs doivent avoir leurs valeurs entre guillemets doubles
<a><b id="45" id="48"></b></a>
- NON bien formé. Erreur : Attributs dupliqués. Un même élément (
<b>
) ne peut pas avoir deux attributs avec le même nom (id
).
- NON bien formé. Erreur : Attributs dupliqués. Un même élément (
<a><b id="45"></b><b id="45"></b></a>
- Bien formé. C’est un piège ! Même si les deux éléments
<b>
ont le mêmeid
, l’erreur 7 concernait des attributs dupliqués sur la même balise. Ici, ce sont deux balises<b>
différentes, chacune avec son propre attributid="45"
. C’est valide en XML bien formé (bien que cela puisse poser problème pour la validation avec un schéma DTD/XSD qui demande des IDs uniques, mais ce n’est pas la question ici).
- Bien formé. C’est un piège ! Même si les deux éléments
Exercice 20 : Le Compteur de Nœuds XML 📊
Le défi : Compter le nombre de nœuds (éléments) ayant un certain nom de balise dans un document XML.
Prérequis :
- Comprendre la structure d’un document XML comme un arbre.
- Maîtriser la récursivité.
- Savoir parcourir un arbre (même si la représentation DOM est interne à Python).
Contexte : Lorsque Python analyse un document XML, il le transforme en une structure d’objet appelée « DOM » (Document Object Model), qui est en fait une représentation en arbre ! Un nœud DOM peut avoir des « enfants » (d’autres nœuds DOM).
Consignes : Écris une fonction compte_balise(d, nom_balise)
qui prend en argument un nœud DOM d
et un nom de balise n
(ici, nom_balise
), et qui renvoie le nombre de nœuds (éléments) ayant ce nom dans le document.
Solution (en Python) :
On va simuler une structure DOM simple avec des dictionnaires pour les nœuds, car la manipulation réelle du DOM avec xml.etree.ElementTree
serait un peu lourde pour l’exercice. L’important est la logique récursive.
Python
# Simulation d'un noeud DOM simple
# Chaque noeud a un 'tag' (nom de balise) et une liste 'children' (ses enfants)
def creer_noeud_dom(tag, children=None):
return {"tag": tag, "children": children if children is not None else []}
def compte_balise(noeud_dom, nom_balise_recherche):
compteur = 0
# 1. Vérifier le noeud actuel
if noeud_dom["tag"] == nom_balise_recherche:
compteur += 1
# 2. Parcourir récursivement les enfants
for enfant in noeud_dom["children"]:
compteur += compte_balise(enfant, nom_balise_recherche) # Appel récursif
return compteur
# Exemple d'utilisation avec une structure XML simulée
# <racine>
# <enfant1>
# <sous_enfant>
# <enfant1/>
# </sous_enfant>
# </enfant1>
# <enfant2/>
# <enfant1/>
# </racine>
arbre_xml_simule = creer_noeud_dom("racine", [
creer_noeud_dom("enfant1", [
creer_noeud_dom("sous_enfant", [
creer_noeud_dom("enfant1")
])
]),
creer_noeud_dom("enfant2"),
creer_noeud_dom("enfant1")
])
print(f"Nombre d'éléments 'enfant1' : {compte_balise(arbre_xml_simule, 'enfant1')}") # Devrait être 2
print(f"Nombre d'éléments 'racine' : {compte_balise(arbre_xml_simule, 'racine')}") # Devrait être 1
print(f"Nombre d'éléments 'bidon' : {compte_balise(arbre_xml_simule, 'bidon')}") # Devrait être 0
Explication : La fonction compte_balise
est une fonction récursive qui fait un parcours en profondeur de l’arbre XML :
- Cas de base implicite : Si un nœud n’a pas d’enfants, la boucle
for
ne s’exécute pas, et la fonction renvoie le compteur pour ce seul nœud. - Traitement du nœud actuel : Elle vérifie si le
tag
(nom de balise) du nœudnoeud_dom
correspond aunom_balise_recherche
. Si oui, elle incrémente lecompteur
. - Appel récursif pour les enfants : Pour chaque enfant du nœud actuel, elle appelle récursivement
compte_balise
et ajoute le résultat aucompteur
.
Cette méthode permet de visiter tous les nœuds de l’arbre et de compter ceux qui correspondent au nom de balise recherché.
Exercice 21 : La Fabrique XML 🏭
Le défi : Générer un document XML avec une structure spécifique et le sauvegarder dans un fichier. C’est comme imprimer un arbre en XML !
Prérequis :
- Comprendre le format XML.
- Savoir manipuler des fichiers en Python (ouvrir, écrire, fermer).
- Utiliser la bibliothèque
xml.etree.ElementTree
de Python (pour la création d’éléments XML).
Consignes : Écris une fonction gen_doc(n)
qui prend un entier n
et génère un document XML de la forme : <a><b>0</b><b>1</b>...<b>n - 1</b></a>
Et sauve ce document dans un fichier docn.xml
.
Solution (en Python) :
Python
import xml.etree.ElementTree as ET
def gen_doc(n):
# Créer l'élément racine 'a'
root_a = ET.Element("a")
# Ajouter les éléments 'b' de 0 à n-1
for i in range(n):
element_b = ET.SubElement(root_a, "b") # Crée un sous-élément 'b' sous 'a'
element_b.text = str(i) # Définit le contenu textuel de 'b'
# Créer un objet ElementTree à partir de la racine
tree = ET.ElementTree(root_a)
# Construire le nom du fichier
nom_fichier = f"doc{n}.xml"
# Sauvegarder le document XML dans le fichier
try:
# pretty_print=True pour un affichage plus lisible dans le fichier
# encoding="utf-8" pour éviter les problèmes d'encodage
tree.write(nom_fichier, encoding="utf-8", xml_declaration=True, pretty_print=True)
print(f"Document XML sauvegardé dans {nom_fichier}")
except Exception as e:
print(f"Erreur lors de la sauvegarde du fichier : {e}")
# Exemples d'utilisation :
gen_doc(5) # Va créer doc5.xml
gen_doc(10) # Va créer doc10.xml
Contenu de doc5.xml
(exemple) :
XML
<?xml version='1.0' encoding='utf-8'?>
<a>
<b>0</b>
<b>1</b>
<b>2</b>
<b>3</b>
<b>4</b>
</a>
Explication :
import xml.etree.ElementTree as ET
: Importe la bibliothèque Python standard pour manipuler le XML. C’est pratique et intégré.ET.Element("a")
: Crée l’élément XML de plus haut niveau, la racine<a>
.for i in range(n)
: Une boucle pour créer lesn
éléments<b>
.ET.SubElement(root_a, "b")
: Crée un nouvel élément<b>
qui est un enfant deroot_a
.element_b.text = str(i)
: Donne le texte (la valeur numériquei
convertie en chaîne) à l’élément<b>
.ET.ElementTree(root_a)
: Crée un objet « arbre » XML à partir de l’élément racine.tree.write(nom_fichier, ...)
: Sauvegarde l’arbre XML dans le fichier spécifié. L’optionpretty_print=True
est très utile pour un affichage lisible.
Exercice 22 : Le Traducteur JSON 🗣️
Le défi : Lire un fichier JSON, interpréter son contenu pour déterminer un mode (« bonjour » ou « bonsoir ») et un nom, puis afficher un message personnalisé. C’est comme créer une petite application de salutations !
Prérequis :
- Comprendre les bases du format JSON (objets, paires clé-valeur, chaînes de caractères).
- Savoir manipuler des fichiers en Python (ouvrir, lire, fermer).
- Utiliser la bibliothèque
json
de Python (pour lire les fichiers JSON).
Consignes : Écris un programme hello_json.py
qui :
- Charge un fichier JSON
config.json
. - Ce fichier
config.json
contient un dictionnaire avec deux entrées :"mode"
: chaîne de caractères"bonjour"
ou"bonsoir"
"nom"
: un nom de personne (par exemple,"Toto"
)
- Le programme affiche ensuite « bonjour Toto » ou « bonsoir Toto » en fonction du mode.
Solution (en Python) :
D’abord, créons le fichier config.json
pour le test :
JSON
# config.json (copiez/collez ce contenu dans un fichier nommé config.json)
{
"mode": "bonjour",
"nom": "Alice"
}
Vous pouvez modifier « mode » à « bonsoir » ou « nom » à « Bob » pour tester.
Maintenant, le programme hello_json.py
:
Python
import json
import os
def hello_json():
nom_fichier_config = "config.json"
# Vérifier si le fichier config.json existe
if not os.path.exists(nom_fichier_config):
print(f"Erreur : Le fichier '{nom_fichier_config}' n'a pas été trouvé.")
print("Veuillez créer un fichier config.json avec le contenu suivant :")
print("""
{
"mode": "bonjour",
"nom": "Toto"
}
""")
return
try:
# Ouvrir et lire le fichier JSON
with open(nom_fichier_config, 'r', encoding='utf-8') as f:
data = json.load(f) # Convertit le contenu JSON en un dictionnaire Python
# Extraire les informations du dictionnaire
mode = data.get("mode") # Utilise .get() pour éviter une erreur si la clé n'existe pas
nom = data.get("nom")
# Vérifier si les clés nécessaires sont présentes
if mode is None or nom is None:
print("Erreur : Le fichier config.json doit contenir les clés 'mode' et 'nom'.")
return
# Afficher le message personnalisé
if mode == "bonjour":
print(f"Bonjour {nom} !")
elif mode == "bonsoir":
print(f"Bonsoir {nom} !")
else:
print(f"Mode inconnu dans config.json : '{mode}'. Je ne sais pas comment saluer {nom}.")
except json.JSONDecodeError as e:
print(f"Erreur de format JSON dans '{nom_fichier_config}' : {e}")
except Exception as e:
print(f"Une erreur inattendue est survenue : {e}")
# Appeler la fonction principale du programme
hello_json()
Explication :
import json
: Importe le modulejson
qui gère la conversion entre les chaînes JSON et les objets Python (dictionnaires, listes).with open(nom_fichier_config, 'r', encoding='utf-8') as f:
: Ouvre le fichierconfig.json
en mode lecture ('r'
). Lewith
garantit que le fichier est bien fermé après.encoding='utf-8'
est essentiel pour les caractères spéciaux.data = json.load(f)
: C’est la ligne magique ! Elle lit le contenu du fichier et le transforme en un dictionnaire Python.mode = data.get("mode")
etnom = data.get("nom")
: Accède aux valeurs associées aux clés"mode"
et"nom"
dans le dictionnaire Python. Utiliser.get()
est plus sûr quedata["mode"]
car cela renvoieNone
si la clé n’existe pas, évitant une erreur.- Les conditions
if/elif/else
: Affichent le message de salutation en fonction de la valeur demode
. try-except
: C’est important pour gérer les erreurs, par exemple si le fichier JSON est mal formé (json.JSONDecodeError
) ou s’il n’existe pas.
Ce programme montre bien la simplicité du JSON pour échanger des données structurées et la facilité avec laquelle Python peut les manipuler !