Parcourir un arbre binaire
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- Connaitre les parcours en profondeur préfixe, infixe et postfixe d’un arbre binaire.
- Connaitre le parcours en largeur d’un arbre binaire.
- Savoir coder les parcours d’un arbre binaire en Python.
- Le parcours en profondeur préfixe d’un arbre binaire consiste à parcourir sa racine, puis son sous-arbre gauche, puis son sous-arbre droit.
- Le parcours en profondeur infixe d’un arbre binaire consiste à parcourir son sous-arbre gauche, puis sa racine, puis son sous-arbre droit.
- Le parcours en profondeur postfixe d’un arbre binaire consiste à parcourir son sous-arbre gauche, puis son sous-arbre droit, puis sa racine.
- La parcours en largeur d’un arbre binaire consiste à le parcourir par niveau.
- Comprendre la structure hiérarchique et le vocabulaire des arbres binaires
- Étudier et implémenter un arbre binaire
- Utiliser la récursivité en Python
- Parcours préfixe : on traite la racine, puis le sous-arbre gauche, puis le sous-arbre droit.
- Parcours infixe : on traite le sous-arbre gauche, puis la racine, puis le sous-arbre droit.
- Parcours postfixe : on traite le sous-arbre gauche, puis le sous-arbre droit, puis la racine.
On considère l’arbre binaire de l’expression algébrique a + 3.
| Parcours préfixe | Parcours infixe | Parcours postfixe |
| + a 3 | a + 3 | a 3 + |
| Parcours préfixe | Parcours infixe | Parcours postfixe |
| × 2 + a 3 | 2 × a + 3 |
2 a 3 + × |
Voici un algorithme de la fonction récursive du parcours préfixe d’un arbre binaire a.
| Algorithme | Explication |
| Fonction prefixe(AB a): |
On définit la fonction prefixe qui prend pour
paramètre un arbre
binaire a
de type AB (arbre binaire). |
| Si est_vide(a) = Faux, alors | Si a n’est pas vide, |
|
traiter racine(a) prefixe(sag(a)) prefixe(sad(a)) |
on traite l’étiquette de la racine
de a, puis on fait le parcours préfixe du sous-arbre gauche de a, et enfin on fait le parcours préfixe du sous-arbre droit de a. |
| FinSi | Fin de l’instruction conditionnelle. |
racine(a) renvoie la racine de a.
Voici l’algorithme de la fonction récursive du parcours infixe d’un arbre binaire a.
| Algorithme | Explication |
| Fonction infixe(AB a): |
On définit la fonction infixe qui prend pour
paramètre un arbre
binaire a
de type AB (arbre binaire). |
| Si est_vide(a) = Faux, alors | Si a n’est pas vide, |
|
infixe(sag(a)) traiter racine(a) infixe(sad(a)) |
on fait le parcours infixe du sous-arbre gauche
de a, puis on traite l’étiquette de la racine de a, et enfin on fait le parcours infixe du sous-arbre droit de a. |
| FinSi | Fin de l’instruction conditionnelle. |
Voici l’algorithme de la fonction récursive du parcours postfixe d’un arbre binaire a.
| Algorithme | Explication |
| Fonction postfixe(AB a): |
On définit la fonction postfixe qui prend pour
paramètre un arbre
binaire a
de type AB (arbre binaire). |
| Si est_vide(a) = Faux, alors | Si a n’est pas vide, |
|
postfixe(sag(a)) postfixe(sad(a)) traiter racine(a) |
on fait le parcours postfixe du sous-arbre gauche
de a, puis on fait le parcours postfixe du sous-arbre droit de a, et enfin on traite l’étiquette de la racine de a. |
| FinSi | Fin de l’instruction conditionnelle. |
En Python, les fonctions prefixe(arbre), infixe(arbre) et postfixe(arbre) implémentent respectivement les parcours en profondeur préfixe, infixe et postfixe de l’arbre binaire arbre.
On choisit de retourner le parcours dans un tableau.
| Python | Explication |
| def prefixe(arbre): | On définit la fonction prefixe. |
| if arbre.est_vide(): | Si l’arbre est vide, |
| return [] | retourner le tableau vide []. |
| else: | Sinon |
|
return [arbre.etiquette] + prefixe(arbre.sag) + prefixe(arbre.sad) |
retourner le tableau constitué de la racine de l’arbre, puis du traitement préfixe du sous-arbre gauche, et enfin du traitement préfixe du sous-arbre droit. |
| Python | Explication |
| def infixe(arbre): | On définit la fonction infixe. |
| if arbre.est_vide(): | Si l’arbre est vide, |
| return [] | retourner le tableau vide []. |
| else: | Sinon |
|
return infixe(arbre.sag) + [arbre.etiquette] + infixe(arbre.sad) |
retourner le tableau constitué du traitement infixe du sous-arbre gauche, puis de la racine de l’arbre et enfin du traitement infixe du sous-arbre droit. |
| Python | Explication |
| def postfixe(arbre): | On définit la fonction postfixe. |
| if arbre.est_vide(): | Si l’arbre est vide, |
| return [] | retourner le tableau vide []. |
| else: | Sinon |
|
return postfixe(arbre.sag) + postfixe(arbre.sad) + [arbre.etiquette] |
retourner le tableau constitué du traitement infixe du sous-arbre gauche, puis de la racine de l’arbre et enfin du traitement infixe du sous-arbre droit. |
On considère l’arbre binaire suivant.
prefixe(a) renvoie [1, 2, 4, 5, 8, 9, 3, 6, 7], infixe(a) renvoie [4, 2, 8, 5, 9, 1, 6, 3, 7] et postfixe(a) renvoie [4, 8, 9, 5, 2, 6, 7, 3, 1].
On considère l’arbre binaire de l’expression algébrique 2(a + 3).
- Niveau 0 : ×
- Niveau 1 : 2 +
- Niveau 2 : a 3
Voici ci-dessous un algorithme de la fonction du parcours en largeur d’un arbre binaire.
| Algorithme | Explication |
| Fonction parcoursLargeur(AB a): | On définit la fonction parcoursLargeur qui prend pour paramètre un arbre binaire a de type AB (arbre binaire). |
| file ← [a] | On définit la file file qui contient l’arbre a. |
|
Tant que la file n’est pas vide |
Tant que file n’est pas vide. |
| sous-arbre ← défiler file | On défile file et on affecte l’arbre récupéré dans la variable sous-arbre. |
| traiter la racine de sous-arbre | On traite la racine de sous-arbre. |
|
Si le
sous-arbre gauche |
Si le sous-arbre gauche de sous-arbre n’est pas vide, alors |
|
Enfiler ce sous-arbre gauche dans file |
on l’enfile dans file. |
| FinSi | Fin de l’instruction conditionnelle. |
|
Si le
sous-arbre droit de sous-arbre n’est pas vide, alors |
Si le sous-arbre droit de sous-arbre n’est pas vide, alors |
|
Enfiler ce sous-arbre gauche dans file |
on l’enfile dans file. |
| FinSi | Fin de l’instruction conditionnelle. |
| Fin Tant que | Fin de la boucle tant que |
En Python, la fonction parcours_largeur(arbre) implémente le parcours en largeur de l’arbre binaire arbre.
On choisit de retourner le parcours dans un tableau.
| Python | Explication |
| def parcours_largeur(arbres): |
On définit la fonction parcours_largeur. |
|
file = [] file.append(arbre) parcours = [] |
On affecte à la variable file un tableau constitué de l’arbre. On affecte à la variable parcours un tableau vide. |
| while len(file) > 0: | Tant que la file n’est pas vide (longueur = 0), |
|
parcours.append(file[0].etiquette) sous_arbre = file.pop(0) |
on ajoute au parcours la première étiquette du premier élément de la file, on retire le premier élément de la file et on l’affecte à la variable sous_arbre. |
|
if not sous_arbre.sag.est_vide(): file.append(sous_arbre.sag) |
Si le sous-arbre gauche n’est pas vide, on l’ajoute à la file. |
|
if not
sous_arbre.sad.est_vide(): file.append(sous_arbre.sad) |
Si le sous-arbre droit n’est pas vide, on l’ajoute à la file. |
| return parcours | Retourner le tableau parcours. |
On considère à nouveau l’arbre binaire suivant.
Voici les fonctions précédentes testées avec cet arbre sur Python Tutor.
parcours_largeur(a) renvoie [1, 2, 3, 4, 5, 6, 7, 8, 9].Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Se déplacer dans un graphe
NSI
Utiliser la méthode « diviser pour régner »
NSI
Programmer de manière dynamique
NSI
Étudier la complexité mémorielle
NSI
Rechercher un motif dans un texte : l'algorithme de Boyer-Moore
NSI
Comprendre les requêtes HTTP et la réponse serveur
NSI
Comprendre la notion de réseau et de protocole
NSI
Comprendre les protocoles de la couche physique
NSI
Comprendre les protocoles de la couche liaison dans un réseau local
NSI
Comprendre les protocoles de la couche réseau
NSI
Comprendre les protocoles de la couche transport
NSI
Décrire des protocoles de récupération de paquets
NSI
Affecter une valeur, utiliser une séquence d'actions
NSI
Utiliser des structures conditionnelles
NSI
Utiliser des boucles
Fermer
Accédez gratuitement à
