Parcours (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
- l'article sur les arbres en NSI de Sébastien Hoarau
- le cours de mon collègue Pierre Duclosson
- le cours de Gilles Lassus
- le cours de Franck Chambon
🔖 Synthèse de ce qu'il faut retenir pour le bac
Parcours d'un arbre binaire⚓︎
Point de cours 9
Un parcours d'un arbre binaire est un algorithme qui visite chaque noeud de l'arbre et lui applique un certain traitement (affichage, récupération de la valeur de l'élément stocké, de la profondeur ...). Le parcours peut traverser plusieurs fois un noeud mais le traitement est appliqué une seule fois pour chaque noeud.
Pour un arbre binaire on distingue deux principaux algorithmes de parcours :
- le parcours en profondeur
- le parcours en largeur
⏱️ Complexité
Si le nombre de fois où un algorithme de parcours traverse un noeud est borné, et si la complexité de traitement d'un noeud l'est aussi, alors un algorithme de parcours d'arbre binaire a une complexité temporelle linéaire par rapport à la taille de l'arbre. C'est le cas des algorithmes de parcours en profondeur et de parcours en largeur.
Parcours en profondeur d'un arbre binaire⚓︎
Point de cours 10
Le parcours en profondeur d'un arbre binaire part de la racine et se dirige préférentiellement vers les feuilles en explorant les branches jusqu'au bout avant de remonter vers les noeuds déjà visités pour parcourir d'autres descendants. On visite les enfants d'un noeud avant ses frères.
L'acronyme anglais pour désigner le parcours en profondeur est DFS pour Depth First Search.
Exemple de parcours en profondeur d'un arbre binaire
Le parcours en profondeur exploite directement la nature récursive d'un arbre binaire, il est donc naturel de l'implémenter récursivement.
Le parcours en profondeur peut passer jusqu'à trois fois par un même noeud : découverte, remontée depuis le sous-arbre/fils gauche et remontée depuis le sous-arbre/fils droit. On distingue donc trois types de parcours en profondeur selon la position du traitement appliqué à l'élément stocké dans le noeud par rapport à l'exploration des sous-arbres/fils (gauche puis droite).
Parcours en profondeur préfixe, infixe ou suffixe/postfixe
Dans le parcours en profondeur préfixe, on traite l'élément stocké dans le noeud avant de parcourir les sous-arbres.
def parcours_prefixe(arbre):
if arbre is None: # cas de l'arbre vide
return
traitement(arbre.racine) # on traite le noeud racine
parcours_prefixe(arbre.gauche) # on parcourt récursivement le fils gauche
parcours_prefixe(arbre.droit) # on parcourt récursivement le fils droit
Pour l'arbre binaire donné en exemple, avec un parcours préfixe, l'ordre de traitement des éléments stockés serait :
A - L - O - R - G - I - T - M - E - H
Dans le parcours en profondeur infixe, on taite l'élément stocké dans le noeud entre le parcours du sous-arbre/fils gauche et le parcours du sous-arbre/fils droit.
def parcours_infixe(arbre):
if arbre is None: # cas de l'arbre vide
return
parcours_infixe(arbre.gauche) # on parcourt récursivement le fils gauche
traitement(arbre.racine) # on traite le noeud racine
parcours_infixe(arbre.droit) # on parcourt récursivement le fils droit
Pour l'arbre binaire donné en exemple, avec un parcours infixe, l'ordre de traitement des éléments stockés serait :
O - L - R - A - G - M - T - E - I - H
Dans le parcours en profondeur suffixe appelé aussi parcours en profondeur postfixe, on taite l'élément stocké dans le noeud après le parcours du sous-arbre/fils gauche et le parcours du sous-arbre/fils droit.
def parcours_postfixe(arbre):
if arbre is None: # cas de l'arbre vide
return
parcours_postfixe(arbre.gauche) # on parcourt récursivement le fils gauche
parcours_postfixe(arbre.droit) # on parcourt récursivement le fils droit
traitement(arbre.racine) # on traite le noeud racine
Pour l'arbre binaire donné en exemple, avec un parcours postfixe, l'ordre de traitement des éléments stockés serait :
O - R - L - M - E - T - H - I - G - A
Exercice 7 : parcours et mesures
💻 Saisir ses réponses sur Capytale
On rappelle les fonctions de mesure d'arbre binaire taille et hauteur
définies dans la section précédente
| Fonction | Signature | Description |
|---|---|---|
taille |
taille(arbre) |
Renvoie le nombre de noeuds dans l'arbre |
hauteur |
hauteur(arbre) |
Renvoie le nombre de noeuds sur le chemin le plus long entre la racine et une feuille de l'arbre |
Pour réaliser ces fonctions de mesure il suffit de parcourir l'arbre donc on peut les implémenter avec un parcours en profondeur.
On considère qu'un arbre binaire non vide est implémenté par un objet de la classe Noeud et qu'un arbre vide est représenté par None.
class Noeud:
"""Noeud pour arbre binaire"""
def __init__(self, g, e, d):
self.gauche = g # lien vers fils gauche g éventuellement vide (None)
self.element = e # élément e stocké dans le noeud
self.droit = d # lien vers fils droit d éventuellement vide (None)
Question 1
Implémentez la fonction taille de façon récursive.
def taille(arbre):
"""Renvoie la taille de l'arbre a"""
if arbre is None:
return 0
return 1 + taille(arbre.gauche) + taille(arbre.droit)
Question 2
Implémentez la fonction hauteur de façon récursive.
def hauteur(arbre):
"""Renvoie la hauteur de l'arbre"""
if arbre is None:
return 0
return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))
Question 3
Implémentez une fonction somme(arbre) de façon récursive qui renvoie la somme de tous les éléments contenus dans les noeuds de l'arbre passé en paramètre. Pour simplifier on va considérer que la somme des éléments de l'arbre vide est nulle.
def somme(arbre):
"""Renvoie la somme des valeurs entières stockées dans les noeuds de l'arbre a"""
if arbre is None:
return 0
return arbre.element + somme(arbre.gauche) + somme(arbre.droit)
Exercice 8 : arbre de calcul
💻 Saisir ses réponses sur Capytale
On considère l'arbre binaire représentant l'expression arithmétique \(((3\times(4 - 5)) + (5 \times (12 + 7)))\) :
Question 1
Dans la console ci-dessous, on donne une implémentation de cet arbre binaire en Python et on lui applique une fonction de parcours en profondeur infixe qui capture dans un tableau dynamique Python trace l'ordre de traitement des noeuds.
- Exécutez la console et constatez que l'écriture de la trace ne correspond pas au calcul représenté par l'arbre selon les règles de priorité des opérations arithmétiques.
- Complétez la fonction
parcours_infixepour qu'elle capture danstracedes parenthèses permettant d'obtenir une écriture conforme au calcul.
def parcours_infixe_parenthese(arbre, trace):
if arbre is None:
return
trace.append('(')
parcours_infixe_parenthese(arbre.gauche, trace)
trace.append(str(arbre.element))
parcours_infixe_parenthese(arbre.droit, trace)
trace.append(')')
Question 2
- Donnez l'ordre de traitement des éléments de l'arbre par un parcours en profondeur préfixe. Écrire dans la console une fonction
parcours_prefixequi capture dans un tableau dynamique Pythontracel'ordre de traitement des noeuds avec un parcours préfixe. - Même question pour un parcours postfixe.
Pour un parcours préfixe l'ordre de traitement des éléments contenus dans l'arbre est :
+ * 3 - 4 5 * 5 + 12 7
Pour un parcours postfixe l'ordre de traitement des éléments contenus dans l'arbre est :
3 4 5 - * 5 12 7 + * +
Implémentations des parcours :
def parcours_prefixe(arbre, trace):
if arbre is None:
return
trace.append(str(arbre.element))
parcours_prefixe(arbre.gauche, trace)
parcours_prefixe(arbre.droit, trace)
def parcours_postfixe(arbre, trace):
if arbre is None:
return
parcours_postfixe(arbre.gauche, trace)
parcours_postfixe(arbre.droit, trace)
trace.append(str(arbre.element))
Parcours en largeur d'un arbre binaire⚓︎
Point de cours 11
Le parcours en largeur d'un arbre binaire visite les noeuds selon leur ordre de profondeur par rapport à la racine : en partant de la racine on épuise d'abord tous les noeuds d'un même niveau avant de passer au niveau suivant. On visite donc d'abord les frères ou cousins d'un noeud avant de passer à ses descendants. En général on explore un niveau de "gauche à droite".
L'acronyme anglais pour désigner le parcours en largeur est BFS pour Breadth First Search.
Exemple de parcours en largeur d'un arbre binaire
Dans le parcours en largeur, on ne passe qu'une seule fois par un noeud donc on traite l'élément stocké dans le noeud dès qu'on le visite. Ainsi l'ordre de traitement par le parcours en largeur des éléments stockés dans l'arbre binaire ci-dessus sera :
A - L - G - O - R - I - T - H - M - E
Implémentation du parcours en largeur
Pour l'implémentation, on n'utilise pas la récursivité car le parcours en largeur n'explore pas d'abord les fils/sous-arbres. On va utiliser une file (structure FIFO) pour stocker les noeuds en attente ce qui permet de les traiter par profondeur/distance croissante par rapport à la racine.
On commence par enfiler l'arbre (s'il est non vide), puis tant que la file n'est pas vide :
- on défile l'arbre en tête de file ;
- on traite l'élément stocké dans le noeud racine puis on enfile les fils/sous-arbres (gauche puis droite) s'ils existent.
def parcours_largeur(arbre):
f = creer_file()
if arbre is not None:
enfiler(f, arbre)
while not file_vide(f):
a = defiler(f)
traitement(a.racine)
if a.gauche is not None:
enfiler(f, a.gauche)
if a.droit is not None:
enfiler(f, a.droit)
Exercice 9
💻 Saisir ses réponses sur Capytale
On considère l'arbre binaire ci-dessous :
Question 1
Énumérez l'ordre de traitement des éléments contenus dans les noeuds par un algorithme de parcours en largeur.
B R E A D T H
Traduction : LARGEUR
Question 2
On donne une classe File implémentée avec une deque.
Complétez le code de la fonction parcours_largeur.
# Tests (insensible à la casse)(Ctrl+I)
from collections import deque
class File:
def __init__(self):
self.contenu = deque([])
def file_vide(self):
return len(self.contenu) == 0
def defiler(self):
assert not self.file_vide(), "File Vide"
return self.contenu.popleft()
def enfiler(self, elt):
self.contenu.append(elt)
class Noeud2:
"""
Noeud pour arbre binaire
On redéfinit une classe Noeud2 pour ne pas avoir de conflit
avec la classe Noeud de l'exercice 8
"""
def __init__(self, g, e, d):
self.gauche = g # lien vers fils gauche g éventuellement vide (None)
self.element = e # élément e stocké dans le noeud
self.droit = d # lien vers fils droit d éventuellement vide (None)
def parcours_largeur(arbre):
f = File()
if arbre is not None:
f.enfiler(arbre)
while not f.file_vide():
a = f.defiler()
print(a.element)
if a.gauche is not None:
f.enfiler(a.gauche)
if a.droit is not None:
f.enfiler(a.droit)
# construction de l'arbre binaire
a = Noeud2(Noeud2(None, 'R', Noeud2(None, 'A', None)), 'B', Noeud2(Noeud2(None, 'D', None), 'E', Noeud2(Noeud2(None, 'H', None), 'T', None)))
# Tests(insensible à la casse)(Ctrl+I)