Le but est d'implémenter en Python les algorithmes sur le parcours des arbres binaires précédemment étudiés.
On utilisera la construction faite dans le TP précédent.
Les Parcours en profondeur
Pour cela nous allons utiliser une deuxième vidéo.
Activité 1
Programmez la fonction "parcours_infixe" qui prend un arbre binaire T en paramètre et qui permet d'obtenir le parcours infixe de l'arbre T
Ci-dessous algorithme correspondant :
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-INFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-INFIXE(x.gauche)
affiche x.clé
PARCOURS-INFIXE(x.droit)
fin si
FIN
Testez votre fonction en utilisant l'arbre : schéma "Arbre 1" (Voir le TP préxédent) et sur l'arbre de la vidéo.
...CORRECTION...
En applicant la fonction, l' "Arbre 1" doit être parcouru dans l'ordre suivant : C, E, B, D, A, I, G, F, H, J
Acrivité 2
Programmez la fonction "parcours_prefixe" qui prend un arbre binaire T en paramètre et qui permet d'obtenir le parcours préfixe de l'arbre T.
Ci-dessous algorithme correspondant :
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-PREFIXE(T) :
si T ≠ NIL :
x ← T.racine
affiche x.clé
PARCOURS-PREFIXE(x.gauche)
PARCOURS-PREFIXE(x.droit)
fin si
FIN
Testez votre fonction en utilisant l'arbre : schéma "Arbre 1" (Voir le TP préxédent) et sur l'arbre de la vidéo.
...CORRECTION...
En applicant la fonction, l' "Arbre 1" doit être parcouru dans l'ordre suivant : A, B, C, E, D, F, G, I, H, J
Activité 3
Programmez la fonction "parcours_suffixe" qui prend un arbre binaire T en paramètre et qui permet d'obtenir le parcours suffixe de l'arbre T. Ci-dessous algorithme correspondant :
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-SUFFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-SUFFIXE(x.gauche)
PARCOURS-SUFFIXE(x.droit)
affiche x.clé
fin si
FIN
Testez votre fonction en utilisant l'arbre : schéma "Arbre 1" (Voir le TP préxédent) et sur l'arbre de la vidéo.
...CORRECTION...
En applicant la fonction, l' "Arbre 1" doit être parcouru dans l'ordre suivant : E, C, D, B, I, G, J, H, F, A
Le Parcours en largeur
Pour cela nous allons utiliser une troisième vidéo.
Activité 4
ON UTILISE ICI UNE PROGRAMMATION ITTERATIVE
Il est important de bien noter l'utilisation d'une file (FIFO) pour cet algorithme de parcours en largeur.
Programmez la fonction "parcours_largeur" qui prend un arbre binaire T en paramètre et qui permet d'obtenir le parcours en largeur de l'arbre T. Ci-dessous algorithme correspondant :
VARIABLE
T : arbre
Tg : arbre
Td : arbre
x : noeud
f : file (initialement vide)
DEBUT
PARCOURS-LARGEUR(T) :
enfiler(T.racine, f) //on place la racine dans la file
tant que f non vide :
x ← defiler(f)
affiche x.clé
si x.gauche ≠ NIL :
Tg ← x.gauche
enfiler(Tg.racine, f)
fin si
si x.droit ≠ NIL :
Td ← x.droite
enfiler(Td.racine, f)
fin si
fin tant que
FIN
Testez votre fonction en utilisant l'arbre : schéma "Arbre 1" (Voir le TP préxédent) et sur l'arbre de la vidéo.
...CORRECTION...
En applicant la fonction, l' "Arbre 1" doit être parcouru dans l'ordre suivant : A, B, F, C, D, G, H, E, I, J
Activité 5
ON UTILISE ICI UNE PROGRAMMATION RECURSIVE
Programmez la fonction "parcours_largeur_rec" qui prend un arbre binaire T en paramètre et qui permet d'obtenir le parcours en largeur de l'arbre T. Ci-dessous algorithme correspondant :
Testez votre fonction en utilisant l'arbre : schéma "Arbre 1" (Voir le TP préxédent) et sur l'arbre de la vidéo.
...CORRECTION...
En applicant la fonction, l' "Arbre 1" doit être parcouru dans l'ordre suivant : A, B, F, C, D, G, H, E, I, J
Auteur : Andjekel - source : David Roche et Cédric Gerland