16 - Parcours en largeur
Après les parcours en profondeur (prefixe, infixe et suffixe), nous allons aujourd'hui voir comment explorer un arbre en partant de la racine et en explorant chaque niveau, profondeur par profondeur.
Logiciel nécessaire pour l'activité : -
Prérequis :
- Données : Arbre et Arbre Binaire
- Algos : Parcours d'Arbres
- Algos : Algorithmes des Arbres Binaires
Evaluation ✎ :
Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)
1 - Principe du parcours en largeur
Ce parcours consiste à d'abord explorer le niveau 1 (qui ne contient que la racine). Puis le niveau 2...
L'ordre de lecture des noeuds donne donc Alice - Bob - Clara - Didier - Eleonore...
2 - Algorithme de parcours en largeur
En Français
L'algorithme consiste à :
- Enfiler l'arbre dans une file
- Tant que la file n'est pas vide
- Défiler le prochain arbre
- Explorer la racine de l'arbre
- Enfiler les enfants gauche et droite de cet arbre dans la file si ce ne sont pas des arbres vides.
En version algorithme
Algorithme du parcours en largeur
Objectif : explorer les noeuds de l'arbre niveau par niveau.
ENTREE : arbre, l'arbre qu'on veut explorer
SORTIE : Vide (sur cet exemple), ou une réponse correspondant à la séquence des noeuds rencontrés.
La fonction explorer est à définir. Ici, on affichera juste la clé ou l'étiquette du noeud.
arbre doit contenir l'Arbre Binaire à explorer
SI NON estArbreVide(arbre)
f ← nouvelleFile()
enfiler(arbre, f)
TANT QUE NON estFileVide(f)
étape 1 : on extrait le prochain AB et on affiche sa racine
arbre_en_cours ← defiler(f)
explorer(racine(arbre_en_cours))
étape 2 : on voit si on rajoute le sous-arbre gauche dans la File
g ← gauche(arbre_en_cours)
SI NON estArbreVide(g)
enfiler(g, f)
Fin Si
étape 3 : on voit si on rajoute le sous-arbre droite dans la File
d ← droite(arbre_en_cours)
SI NON estArbreVide(d)
enfiler(d, f)
Fin Si
Fin Tant Que
Fin Si
Renvoyer VIDE (∅)
01° Appliquer l'algorithme à la main sur l'Arbre ci-dessous.
Ecrire le contenu de la File à chaque changement et signaler lorsqu'on devrait afficher un résultat.
Vous devriez aboutir à l'affichage A-B-C-D.
...CORRECTION...
On enfile l'arbre aa.
Contenu de la File : aa
On démarre le TANT QUE.
On défile et on travaille donc avec l'arbre aa.
Contenu de la File : VIDE
On affiche la clé de la racine : A.
On enfile le sous-arbre droite ab de l'arbre aa.
Contenu de la File : ab
Deuxième tour de TANT QUE.
On défile et on travaille donc avec l'arbre ab.
Contenu de la File : vide
On affiche la clé de la racine : B.
On enfile le sous-arbre gauche ac de l'arbre ab.
Contenu de la File : ac
On enfile le sous-arbre droite ad de l'arbre ab.
Contenu de la File (v1) : (avant) ac ← ad (arrière)
Contenu de la File (v2 ): (arrière) ad → ac (avant)
Troisième tour de TANT QUE.
On défile et on travaille donc avec l'arbre ac.
Contenu de la File : ad
On affiche la clé de la racine : C.
Aucun enfilement car les deux-sous arbres sont vides.
Quatrième tour de TANT QUE.
On défile et on travaille donc avec l'arbre ad.
Contenu de la File : vide
On affiche la clé de la racine : D.
Aucun enfilement car les deux-sous arbres sont vides.
Fin du TANT QUE car la File est vide.
02° Même question en ne fournissant que les états successifs de la File.
Début de la rédaction :
Contenu de la File : vide
On enfile aa : aa
On défile (A) et on enfile ac puis ae : (avant) ac ← ae (arrière)
...CORRECTION...
Contenu de la File : vide
On enfile aa : aa
On défile (A) et on enfile ac puis ae : (avant) ac ← ae (arrière)
On défile (C) et on enfile ag puis ab : (avant) ae ← ag ← ab (arrière)
On défile (D) et on enfile ad puis af : (avant) ag ← ab ← ad ← af(arrière)
On défile (G) et on enfile ah : (avant) ab ← ad ← af ← ah (arrière)
Il suffit de défiler car il ne s'agit que de feuilles.
On aura donc B - D - F - H.
3 - Implémentation et programmation en Python
Nous avions utilisé le module arbre_binaire_ifa, nous allons simplement rajouter le module file_ifa et importer ces fonctions d'interface permettant de gérer une File.
03° Créer la structure ci-dessous en utilisant les codes fournis pour les fichiers arbre_binaire_ifa.py et file_ifa.py.
📁 algoParcoursLargeur
📄 arbre_binaire_ifa.py
📄 file_ifa.py
...arbre_binaire_ifa.py...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149 | |
...file_ifa.py...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127 | |
04° Utiliser le fichier programme_parcours.py suivant. Il importe les deux ensembles de fonctions d'Interface (les primitives des Files et des Arbres Binaires).
Deux questions :
- à quoi sert la ligne 18 ? Regarder notamment la ligne 45.
- représenter l'arbre construit par le programme de test.
📁 algoParcoursLargeur
📄 arbre_binaire_ifa.py
📄 file_ifa.py
📄 programme_parcours.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96 | |
...CORRECTION...
La ligne 18 permet d'importer la fonction d'interface taille qui permet d'obtenir le nombre d'éléments dans la file. Comme il existe déjà une fonction taille dans notre programme (elle donne la taille de l'arbre binaire), on change le nom de la fonction importée.
Pour l'Arbre Binaire, il suffit de regarder ci-dessous.
Voici notre Arbre Binaire de test :
05° Utiliser la fonction native help pour aller retrouver la documentation (notamment le prototype pour savoir quoi envoyer).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | |
Par exemple :
>>> help(enfiler)
Help on function enfiler in module file_ifa:
enfiler(x: file_ifa.Elt, f: file_ifa.File) -> None
On insére la nouvelle valeur à l'arrière
06° Compléter le code de la fonction parcours_largeur pour qu'elle parvienne à implémenter l'algorithme proposé.
arbre doit contenir l'Arbre Binaire à explorer
SI NON estArbreVide(arbre)
f ← nouvelleFile()
enfiler(arbre, f)
TANT QUE NON estFileVide(f)
étape 1 : on extrait le prochain AB et on affiche sa racine
arbre_en_cours ← defiler(f)
explorer(racine(arbre_en_cours))
étape 2 : on voit si on rajoute le sous-arbre gauche dans la File
g ← gauche(arbre_en_cours)
SI NON estArbreVide(g)
enfiler(g, f)
Fin Si
étape 3 : on voit si on rajoute le sous-arbre droite dans la File
d ← droite(arbre_en_cours)
SI NON estArbreVide(d)
enfiler(d, f)
Fin Si
Fin Tant Que
Fin Si
Renvoyer VIDE (∅)
Vous devriez parvenir à explorer les noeuds dans l'ordre suivant :
>>> parcours_largeur(aa)
A
B
C
D
E
F
G
H
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | |
4 - Version récursive
Nous pouvons réaliser une version récursive utilisant également une File qu'on transmettra à chaque appel. On lance donc un appel à une première fonction parcours_largeur_2(). On lui transmet l'arbre sur lequel on doit travailler.
Cette fonction va alors créer une file et y placer un unique élément : l'arbre reçu.
On lance alors le premier appel à la fonction récursive exploration_suivante() qui doit recevoir la file.
1
2
3
4
5
6
7
8
9
10 | |
08° Réaliser la fonction récursive exploration_suivante() pour qu'elle réagisse de cette façon :
- Condition d'arrêt : la file est vide.
- Cas de base : on ne renvoie rien (et donc on sort de cet appel)
- Sinon, cas récursif : il s'agit du code interne au TANT QUE de l'algorithme purement itératif. Le TANT QUE est donc remplacé par un appel récursif à la fonction.
étape 1 : on extrait le prochain AB et on affiche sa racine
arbre_en_cours ← defiler(f)
explorer(racine(arbre_en_cours))
étape 2 : on voit si on rajoute le sous-arbre gauche dans la File
g ← gauche(arbre_en_cours)
SI NON estArbreVide(g)
enfiler(g, f)
Fin Si
étape 3 : on voit si on rajoute le sous-arbre droite dans la File
d ← droite(arbre_en_cours)
SI NON estArbreVide(d)
enfiler(d, f)
Fin Si
exploration_suivante(f)
On prendra toujours une fonction explorer() qui ne fait qu'afficher dans la console la clé de la racine de l'arbre en cours d'exploration.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | |
5 - FAQ
Rien pour le moment
Activité publiée le 15 12 2020
Dernière modification : 30 01 2021
Auteur : ows. h.