NSI Terminale

Implémentation en Python des algorithmes sur le parcours des arbres binaires

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.
ATTENTION: Il nous faut utiliser la fonction hauteur définie dans le premier TP


Ci-dessous algorithme correspondant :
	
	VARIABLE
	T : arbre
	x : noeud

	DEBUT
	PARCOURS-LARGEUR-REC(T) :
	  Pour  n = 1 à Hauteur(T)
		AFFICHE-NIVEAU(T, n)
		
	AFFICHE-NIVEAU(T, niveau)
	  x ← T.racine
	  si niveau = 1 :
		affiche x.clé
	  sinon
		AFFICHE-NIVEAU(x.gauche, niveau - 1)
		AFFICHE-NIVEAU(x.droit, niveau - 1)
	  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, F, C, D, G, H, E, I, J