Arbres - Parcours
I. Retour sur les structures de données abstraites.⚓︎
Quelles techniques avons-nous pour accéder aux éléments ?
1. Pour le type abstrait liste :
Solution
Renvoyer la tête de la liste
2. Pour le type abstrait file :
Solution
Défiler
3. Pour le type abstrait pile :
Solution
Dépiler
4. Pour le type abstrait dictionnaire :
Solution
Accès par clé
. Pour le type list de python :
Solution
Accès par index, ou par élément
II. Rappel : Les Arbre binaires⚓︎
Arbres binaires
- Un arbre binaire est une structure permettant de stocker une collection de données de même type.
- Ce n'est pas une structure linéaire.
- Le principal avantage des arbres par rapport aux listes est qu’ils permettent de ranger les données de telle sorte que les recherches soient plus efficaces.
- Pour accéder à un élément quelconque d’un arbre , il faut "descendre" dans l’arbre jusqu’à cet élément.
Arbre généalogique de Louis XIV
Comme nous l'avons déjà vu, certaines données ont naturellement une structure d'arbre binaire. C'est le cas d'un arbre généalogique ascendant (recherche du père et de la mère) .
Exemple pour Louis XIV :
graph TD
D(Henri IV)
E(Maria de Medicis)
F(Felipe III d'Espagne)
G(Margareta d'Autriche)
B(Louis XIII)
C(Anna d'Autriche)
A(Louis XIV)
D --- B
E --- B
F --- C
G --- C
B --- A
C --- A😊 De façon plus conforme à la théorie des arbres, nous aurions pu représenter cet arbre de la façon suivante, en plaçant la racine en haut :
graph TD
A(Louis XIV)
B(Louis XIII)
C(Anna d'Autriche)
D(Henri IV)
E(Maria de Medicis)
F(Felipe III d'Espagne)
G(Margareta d'Autriche)
A --- B
A --- C
B --- D
B --- E
C --- F
C --- GLes parcours
-
Un parcours en largeur nous permettra de parcourir successivement toutes les personnes d'une même génération.
-
Un parcours en profondeur nous permettra de parcourir l'arbre "par branche".
III. 🏃 Parcours en largeur des arbres⚓︎
BFS
- Ce parcours est parfois noté BFS pour Breadth-First Search
- Le parcours en largeur correspond à un parcours par niveau de noeuds de l'arbre. Un niveau est un ensemble de nœuds ou de feuilles situés à la même profondeur.
👉 C'est un parcours étage par étage (de haut en bas) et de gauche à droite.
Dans cet exemple, on obtient successivement : 3, 1, 4, 5, 2, 0.
👉 Pour étudier cet algorithme de parcours en largeur, nous allons utiliser une file.
Les files
Quel est le principe d'une file ?
Solution
En informatique, une file (queue en anglais ) est une structure de données basée sur le principe «Premier entré, premier sorti», en anglais FIFO (First In, First Out), ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés.
Le module queue de Python
Nous avons déjà vu plusieurs implémentations possibles des files, nous allons ici utiliser celle de Python : le module Queue
Extrait de la documentation en français de python sur le module Queue qui est une implémentation des files. (Documentation officielle)
Les objets Queue (Queue, LifoQueue ou PriorityQueue) fournissent les méthodes publiques décrites ci-dessous.
f = Queue()Créé une file vide nomméef.f.qsize()renvoie la taille de la filef.f.empty()renvoieTruesi la filefest vide,Falsesinonf.put(item)ajouteitemdans la fileff.get()défile (retire) et renvoie l'élément défilé de la filef.
D'après le cours de Gilles Lassus
Méthode
- On place l'arbre dans la file.
- Tant que la file n'est pas vide, on procède comme suit :
- On défile, donc on récupère l'arbre situé en haut de la file.
- Si cet arbre n'est pas vide :
- On garde son étiquette.
- On enfile son sous-arbre gauche, puis son sous-arbre droit.
À vous
Ecrire les états suivants de la file. Nous admettons ici qu'un arbre vide est None.
Solution
Classe Arbre simplifiée, sans encapsulation 
Exécuter le script suivant :
Créer l'arbre tests
Compléter le script suivant pour créer l'arbre de la figure ci-dessus
Solution
# arbre-test
a = Arbre(8)
a.left = Arbre(4)
a.right = Arbre(5)
a.left.left = Arbre(2)
a.left.right = Arbre(1)
a.right.right = Arbre(3)
À vous
Compléter le script suivant : la fonction parcours_BFS doit renvoyer la liste des noeuds obtenue par le parcours en largeur de l'arbre.
Solution
def parcours_BFS(arbre):
file = Queue()
file.put(arbre)
solution = []
while not file.empty():
a = file.get()
if a is not None :
solution.append(a.data)
file.put(a.left)
file.put(a.right)
return solution
Tester
Tester ci-dessous la fonction parcours_BFS pour l'arbre test créé au-dessus.
Solution
print(parcours_BFS(a))
✍ A noter ... et à mémoriser ... 🐘
f = File() # Création d'une file vide f.enfiler(arbre)
tant que f non vide : arbre_au_sommet = f.defiler() si arbre_au_sommet n'est pas vide On garde son étiquette f.enfiler(son sous-arbre gauche) f.enfiler(son sous-arbre droit) fin si fin tant que
IV. Les parcours en profondeur - Généralités⚓︎
Le principe
-
Dans le cas d'un parcours en profondeur, l'un des deux sous-arbres est complètement exploré avant que l'exploration du second ne commence.
-
On distingue trois types de parcours selon l'ordre dans lequel le sous-arbre de gauche, le sous-arbre droit et la racine sont explorés.
balade et contours
Pour parcourir un arbre en profondeur, on se "balade" autour de l'arbre de la façon suivante (en commençant toujours par la gauche) :
Les flèches numérotées en pointillé, qui sont représentées à côté des branches de l'arbre indiquent comment on se "balade" autour de l'arbre.
Ainsi on a les parcours successifs suivants:
- la flèche 1 indique que l'on va de r à a
- la flèche 2 indique que l'on va de a à c
- la flèche 3 indique que l'on va de c à h
- la flèche 4 indique que l'on va de h à c
etc.
👉 Nous avons donc la "balade" r, a, c, h, c, a, d, i, d, j, l, j, d, a, r, b, e, k, e, b, f, b, r , que l'on appelera le "contours";
Source : https://math.univ-lyon1.fr/irem/IMG/pdf/parcours_arbre_avec_solutions-2.pdf
Première définition des trois parcours
On définit trois parcours des sommets de l’arbre :
- L’ordre préfixe : on liste chaque sommet la première fois qu’on le rencontre dans la balade.
Chaque nœud est visité avant que ses deux fils le soient.
On part de la racine, on visite le fils gauche (et éventuellement le fils gauche de celui-ci, etc.) avant de remonter et de redescendre vers le fils droit.
Cela donne ici : r, a, c, h, d, i, j, l, b, e, k, f
- l’ordre suffixe (aussi appelé postfixe en anglais) : on liste chaque sommet la dernière fois qu’on le rencontre.
Chaque nœud est visité après que ses deux fils le soient.
On visite le fils gauche, puis le fils droit, puis la racine
Cela donne ici : h, c, i, l, j, d, a, k, e, f , b, r
- l’ordre infixe (plus compliqué!): chaque nœud est visité (listé) après son fils gauche mais avant son fils droit.
Si c'est une feuille il est donc listé (son fils gauche et son fils droit sont vides)
On visite le fils gauche, puis la racine, puis le fils droit
Cela donne ici : c, h, a, i ,d, l, j, r, k, e, b, f
😀 Ces trois parcours sont naturellement récursifs.
Deuxième définition des trois parcours
💡 On ajoute les fils fantômes manquants 😀
On peut ainsi considérer qu’on passe une fois à gauche de chaque nœud (en descendant), une fois en dessous de chaque nœud, une fois à droite de chaque nœud (en remontant).
ordres préfixe, suffixe, infixe
- Ordre préfixe : lorsque l'on passe à gauche des nœuds.
👉 Regarder cette vidéo : ordre préfixe
- Ordre suffixe : lorsque l'on passe à droite des nœuds.
👉 Regarder cette vidéo : ordre suffixe
- Ordre infixe : lorsque l'on passe sous les noeuds
👉 Regarder cette vidéo : ordre infixe
Exercice 1
Donner le rendu de chaque parcours :
- Parcours en largeur
- Parcours préfixe
- Parcours infixe
- Parcours postfixe
largeur : 1 2 3 4 5 6 7 8 9
préfixe : 1 2 4 5 7 8 3 6 9
infixe : 4 2 7 5 8 1 3 9 6
postfixe : 4 7 8 5 2 9 6 3 1
Exercice 2
Donner le rendu de chaque parcours :
- Parcours en largeur
- Parcours préfixe
- Parcours infixe
- Parcours postfixe
largeur : 9 8 7 6 2 5 1 4 3
préfixe : 9 8 6 2 1 7 5 4 3
infixe : 6 8 1 2 9 7 4 5 3
postfixe : 6 1 2 8 4 3 5 7 9
Exercice débranché : Expérimentons ces trois parcours dans le cas concret d'un labyrinthe
Voici un labyrinthe :
Les cercles vides sont des nœuds sans intersection, les cercles pleins sont des culs de sac, les carrés sont des intersections, l'entrée et la sortie sont marquées par un cercle plein dans un cercle vide.
Ce labyrinthe est parfait : chaque cellule est reliée à toutes les autres et, ce, de manière unique
Contrairement au labyrinthe étudié dans le cours sur les graphe, celui-ci peut donc être représenté par un arbre (il n'y a pas de cycle)
a. Faire la représentation de ce labyrinthe avec un arbre (sur feuille).
- Pour nommer un nœud, il a été choisi de donner en premier le numéro de la colonne, et en deuxième le numéro de la ligne. Le nœud d'entrée est donc le (0,4) et celui de sortie le (5,4).
- On part du nœud (0,4) qui sera la racine de cet arbre. Lorsqu'il n'y a qu'un fils, on convient de le placer obligatoirement à gauche, et lorsqu'il y a une intersection, placez bien entendu à gauche le nœud quand on va vers la gauche et à droite quand on va à droite.
- 👉 Pour simplifier, on notera 04 à la place (0, 4), 14 à la place de (1, 4) etc...
Dessin à faire sur votre feuille
b. Quelle est la hauteur de l'arbre ?
Solution
Réponse : 12
c. Quelle est la profondeur du nœud (5,4) ? Qu'est-ce que cette profondeur représente dans notre problème ?
Solution
Réponse : 9
C'est la longueur du plus court chemin vers la sortie.
d. Différents parcours en profondeur de cet arbre
💁🏻
📌Appelez votre professeur pour qu'il vous donne une version papier à compléter. Vous devez réaliser les trois parcours en profondeur vus (préfixe, suffixe et infixe) sur cet arbre.
Pour une question de mise en page quand il n'y a qu'un seul fils la flèche est dessinée verticale (et non vers la gauche)
Vous pouvez aussi télécharger ce document ici : 🌐 Arbres à compléter
Correction du parcours préfixe
Correction du parcours suffixe
Correction du parcours infixe
📌Quel est le parcours qui donne le chemin le plus court pour trouver la sortie?
Solution
Réponse : parcours suffixe
📌Aurions-nous pu trouver un chemin plus rapide?
Solution
Réponse : il suffit de faire (0,4), (1,4), (2,4), (3,4), (4,4), (4,3), (4,2), (5,2), (5,3), (5,4)
Remarque
🌵 La structure d'arbre n'est pas adaptée à la recherche de chemins, ou du plus court chemin. Nous verrons plus tard comment résoudre ce problème avec des parcours de graphe.
V. Implémentation des parcours en profondeur⚓︎
Une classe Arbre
Il faut absolument exécuter ce code pour pouvoir travailler ensuite.
1. Le parcours préfixe⚓︎
On donne le pseudo-code suivant :
fonction parcours_prefixe(arbre) :
si arbre is not None :
affiche arbre.valeur
parcours_prefixe(arbre.gauche)
parcours_prefixe(arbre.droit)
A vous de jouer 1
Compléter le code suivant, et le tester pour arbre1 (arbre ci-dessous)
Vérifier à la main que le résultat est bien correct.
flowchart TD
a(A)
b(B)
c(C)
d(D)
e(E)
f(F)
g( )
h( )
i(G)
a --- b
a --- c
b --- d
b --- e
c --- f
c --- g
d --- h
d --- i
linkStyle 5 stroke-width:0px;
linkStyle 6 stroke-width:0px;
style g opacity:0;
style h opacity:0;Solution
# version simple avec print (renvoie None)
def parcours_prefixe(arbre) :
if arbre is not None :
print(arbre.valeur)
parcours_prefixe(arbre.gauche)
parcours_prefixe(arbre.droit)
# création de l'arbre :
arbre1 = Arbre("A")
arbre1.ajout_gauche("B")
arbre1.ajout_droit("C")
arbre1.gauche.ajout_gauche("D")
arbre1.gauche.ajout_droit("E")
arbre1.gauche.gauche.ajout_droit("G")
arbre1.droit.ajout_gauche("F")
# parcours
parcours_prefixe(arbre1)
A vous de jouer 2
Au lieu de simplement afficher les nœuds visités, nous allons en constituer la liste.
Compléter :
Retenir
préfixe : RGD (racine, sous-arbre gauche, sous-arbre droit)
Racine en 1er
Parcours préfixe
fonction parcours_prefixe(arbre):
si arbre is not None :
affiche arbre.valeur
parcours_prefixe(arbre.gauche)
parcours_prefixe(arbre.droit)
👉 ou si on doit renvoyer une liste :
fonction parcours_prefixe(arbre):
si arbre is None :
renvoyer une liste vide
sinon :
renvoyer [arbre.valeur] + parcours_prefixe(arbre.gauche) + parcours_prefixe(arbre.droit)
2. Le parcours suffixe⚓︎
On donne le pseudo-code suivant :
fonction parcours_suffixe(arbre) :
si arbre is not None :
parcours_suffixe(arbre.gauche)
parcours_suffixe(arbre.droit)
affiche arbre.valeur
A vous de jouer 3
Compléter le code suivant, et le tester pour arbre1 (arbre ci-dessous)
Vérifier à la main que le résultat est bien correct.
flowchart TD
a(A)
b(B)
c(C)
d(D)
e(E)
f(F)
g( )
h( )
i(G)
a --- b
a --- c
b --- d
b --- e
c --- f
c --- g
d --- h
d --- i
linkStyle 5 stroke-width:0px;
linkStyle 6 stroke-width:0px;
style g opacity:0;
style h opacity:0;Solution
def parcours_suffixe(arbre):
if arbre is not None:
parcours_suffixe(arbre.gauche)
parcours_suffixe(arbre.droit)
print(arbre.valeur)
A vous de jouer 4
Au lieu de simplement afficher les nœuds visités, nous allons en constituer la liste.
Compléter :
Retenir
suffixe : GDR (sous-arbre gauche, sous-arbre droit, racine)
Racine en dernier
Parcours suffixe
fonction parcours_suffixe(arbre) :
si arbre is not None :
parcours_suffixe(arbre.gauche)
parcours_suffixe(arbre.droit)
affiche arbre.valeur
👉 ou si on doit renvoyer une liste :
fonction parcours_suffixe(arbre) :
si arbre is None :
renvoyer une liste vide
sinon :
renvoyer parcours_suffixe(arbre.gauche) + parcours_suffixe(arbre.droit) + [arbre.valeur]
3. Le parcours infixe⚓︎
On donne le pseudo-code suivant :
fonction parcours_infixe(arbre) :
si arbre is not None :
parcours_infixe(arbre.gauche)
affiche arbre.valeur
parcours_infixe(arbre.droit)
A vous de jouer 5
Compléter le code suivant, et le tester pour arbre1 (arbre ci-dessous)
Vérifier à la main que le résultat est bien correct.
flowchart TD
a(A)
b(B)
c(C)
d(D)
e(E)
f(F)
g( )
h( )
i(G)
a --- b
a --- c
b --- d
b --- e
c --- f
c --- g
d --- h
d --- i
linkStyle 5 stroke-width:0px;
linkStyle 6 stroke-width:0px;
style g opacity:0;
style h opacity:0;Solution
def parcours_infixe(arbre):
if arbre is not None:
parcours_infixe(arbre.gauche)
print(arbre.valeur)
parcours_infixe(arbre.droit)
A vous de jouer 6
Au lieu de simplement afficher les nœuds visités, nous allons en constituer la liste.
Compléter :
Retenir
infixe : GRD (sous-arbre gauche, racine, sous-arbre droit)
Racine au milieu
Parcours infixe
fonction parcours_infixe(arbre) :
si arbre is not None :
parcours_infixe(arbre.gauche)
affiche arbre.valeur
parcours_infixe(arbre.droit)
👉 ou si on doit renvoyer une liste :
fonction parcours_infixe(arbre) :
si arbre is None :
renvoyer une liste vide
sinon :
renvoyer parcours_infixe(arbre.gauche) + [arbre.valeur] + parcours_infixe(arbre.droit)
4. Quel parcours choisir ?⚓︎
Retenir
Nous avons vu que le parcours en largeur était pertinent pour avoir des renseignements plutôt par niveau, utile par exemple si on veut connaître les personnes d'une même génération.
Le parcours préfixe, parcourt l'arbre en profondeur plutôt de manière descendante, et le suffixe plutôt de manière ascendante.
Quel est l'intérêt du parcours infixe ?
Nous allons voir cela dans le paragraphe suivant. 😀
5. Parcours infixe sur un arbre binaire de recherche.⚓︎
Exemple
Le tri du bijoutier (d'après un sujet de l'APMEP)
Considérons le problème du bijoutier voulant trier par grosseur un tas de diamants :
pour faire cette opération il se sert d’un tamis ce qui lui permet de séparer le tas initial
en deux, et il recommence avec de nouveaux tamis pour chaque tas. On le comprend
facilement l’efficacité du tri est fonction des trames des tamis utilisés.
Nous allons utiliser une idée similaire pour créer un arbre binaire, et pour construire les
algorithmes permettant de le parcourir.
Mieux qu’un grand discours montrons la construction de l’arbre correspondant aux données 7, 3, 1, 8, 6.
Nous allons placer le premier élément 7 à la racine d'un arbre.
Principe du tamis : pour n'importe quel noeud, tous les noeuds se trouvant dans son sous-arbre gauche ont une valeur inférieure, et tous ceux se trouvant dans le sous arbre droit ont une valeur supérieure. Le sous arbre gauche correspond à ce qui est passé dans les trous du tamis, et le sous-arbre droit à ce qui est resté dans le tamis.
- 3 < 7 donc 3 est fils gauche de 7
- 1 < 3 donc 1 est fils gauche de 3
- 8 > 7 donc 8 est fils droit de 7. (on ne peut pas mettre 8 comme fils droit de 3, car sinon 8 serait dans le sous-arbre gauche de 7, ce qui est impossible car ce sous-arbre ne doit contenir que des nombres inférieurs à 7).
- 6 > 3 et 6 < 7 donc 6 est fils droit de 3.
On obtient l'arbre suivant :
Nous venons de créer un arbre binaire de recherche
Nous reviendrons plus tard en détail sur cette structure de données.
A vous de jouer 7
Reprenons cet exemple et implémentons le avec la classe Arbre du début.
Compléter ci-dessous. Que constatez-vous ?
Solution
# Compléter ci-dessous
abr = Arbre(7)
abr.ajout_gauche(3)
abr.gauche.ajout_gauche(1)
abr.gauche.ajout_droit(6)
abr.ajout_droit(8)
😃
🐘 A retenir
Le parcours infixe sur un arbre binaire de recherche trie les noeuds de cet arbre.
👉 C'est un des très grands intérêts des arbres binaires de recherche, et du parcours infixe.
VI. TP final⚓︎
⌛ Avant de commencer
Vous devez travailler sur Basthon
Télécharger dans le même dossier :
-
🌐 Fichier
module_tree_2021.py: "Clic droit", puis "Enregistrer la cible du lien sous" -
🌐 TD
parcours_arbre_labyrinthe_parfait_sujet_2023.ipynb: "Clic droit", puis "Enregistrer la cible du lien sous"
😀 La correction est arrivée ...
Télécharger dans le même dossier :
-
🌐 Fichier
module_tree_2021.py: "Clic droit", puis "Enregistrer la cible du lien sous" -
🌐 Correction du TD
parcours_arbre_labyrinthe_parfait_corr_2023_v2.ipynb: "Clic droit", puis "Enregistrer la cible du lien sous"
VII. ✍ Bilan⚓︎
Parcours en largeur
aVoir <- fileVide
enfiler la racine
vus = listeVide (si on doit renvoyer le parcours)
tant que aVoir non vide :
a <- defiler()
visiter a (ajout dans une liste vus, ou affichage)
si a.filsG not None:
enfiler a.filsG
si a.filsD not None:
enfiler a.filsD
Parcours préfixe
def prefixe(arbre) :
if arbre is None :
return []
else :
return [arbre.valeur] + prefixe(arbre.filsG) + prefixe(arbre.filsD)
Parcours suffixe
def suffixe(arbre) :
if arbre is None :
return []
else :
return suffixe(arbre.filsG) + suffixe(arbre.filsD) + [arbre.valeur]
Parcours infixe
def infixe(arbre) :
if arbre is None :
return []
else :
return infixe(arbre.filsG)] + [arbre.valeur] + infixe(arbre.filsD)
VIII. Vidéos pour approfondir⚓︎
Parcours préfixe
Parcours suffixe
😉 Le parcours suffixe se fait de façon analogue.
Parcours infixe
🌳 Crédits⚓︎
Jean-Louis Thirot , Mireille Coilhac, Valérie Mousseaux, Gilles Lassus