Lycée > Terminale > NSI > Parcourir un arbre binaire

Parcourir un arbre binaire

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

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.

Points clés

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.

Pour bien comprendre

Comprendre la structure hiérarchique et le vocabulaire des arbres binaires
Étudier et implémenter un arbre binaire
Utiliser la récursivité en Python

1. Parcourir un arbre binaire en profondeur

a. Principe

Parcourir un arbre binaire, c’est lire toutes les étiquettes de ses nœuds. Chaque parcours définit l’ordre de lecture des étiquettes.

Le parcours en profondeur d’un arbre binaire non vide consiste à le parcourir récursivement : on parcourt son sous-arbre gauche, puis son sous-arbre droit, sa racine pouvant être traitée au début, entre les deux parcours ou à la fin.

On définit ainsi trois parcours en profondeur.

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.

Exemples
On considère l’arbre binaire de l’expression algébrique a + 3.

Les parcours en profondeur de cet arbre sont les suivants.

Parcours préfixe	Parcours infixe	Parcours postfixe
+ a 3	a + 3	a 3 +

Donc, si on considère l’arbre binaire de l’expression algébrique 2(a + 3).

Les parcours en profondeur de cet arbre sont les suivants.

Parcours préfixe	Parcours infixe	Parcours postfixe
× 2 + a 3	2 × a + 3	2 a 3 + ×

b. Algorithmes

Parcours préfixe

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.

Parcours infixe

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.

Parcours postfixe

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.

c. Programmation

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.

Fonction prefixe(arbre)

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.

Fonction infixe(arbre)

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.

Fonction postfixe(arbre)

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.

Exemple
On considère l’arbre binaire suivant.

Voici les fonctions précédentes testées avec cet arbre.

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].

2. Parcourir un arbre binaire en largeur

a. Principe

Le parcours en largeur d’un arbre binaire non vide consiste à le parcourir par niveaux.

Exemple
On considère l’arbre binaire de l’expression algébrique 2(a + 3).

Cet arbre a trois niveaux :

Niveau 0 : ×
Niveau 1 : 2 +
Niveau 2 : a 3

Le parcours en largeur de cet arbre est donc : × 2 + a 3

b. Algorithme

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 de sous-arbre n’est pas vide, alors	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

c. Programmation

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.