En terminale

• Introduction
• Calculer la taille et la hauteur
• Parcours en largeur
• Parcours en profondeur
• Arbres de recherche
• Exercices

Dans cette partie nous allons donner de nombreux algorithmes. Il seront souvent récursifs. Les algorithmes récursifs sont très puissants mais sont très exigeants, tant dans l'écriture de l'algorithme que dans celle du programme. Débugger un programme récursif est un vrai casse tête, il vaut mieux pouvoir faire confiance à son algorithme !

Pour pouvoir coder ces algorithmes, il va falloir au préalabe arriver à coder un arbre et à en extraire un sous arbre. Dans la suite, on suppose que l'on code les arbres récursivement à partir de noeuds liées les uns aux autres par la relation père/fils. Ainsi, lorsque l'on va calculer la taille d'un arbre, je vais plutôt noter taille(noeud_choisi) plutôt que taille(arbre) qui selon moi apporte une confusion pour la suite vu que notre objet est en fait un noeud.

La taille d'un arbre est le nombre de noeuds de l'arbre. L'idée est simple. La taille d'un arbre en partant de la racine est de 1 (pour la racine) plus la taille du sous arbre gauche et celle du sous arbre droit. Le sous arbre gauche a une racine...on recommence le raisonnement, on est en pleine construction d'un raisonnement récursif.

Voici l'algorithme

fonction taille(noeud_depart):
	si noeud_depart est vide alors
		retourner 0
	sinon
		taille_gauche reçoit taille(sous_arbre_gauche(noeud_depart)
		taille_droite reçoit taille(sous_arbre_droit(noeud_depart)
		retourner(1+taille_gauche+taille_droite)

Pour chercher la hauteur d'un arbre, une méthode est de dire que la hauteur d'un arbre est 1 plus le maximum entre la hauteur du sous arbre gauche et le droit.

fonction hauteur(noeud_depart):
	si noeud_depart est vide alors
		retourner -1
	sinon
		hauteur_gauche reçoit hauteur(sous_arebe_gauche(noeud_depart)
		hauteur_droite reçoit hauteur(sous_arebe_droite(noeud_depart)
		retourner(1+max(hauteur_gauche,hauteur_droite))

Le parcours en largeur (BFS Breadth First Search ) d'un arbre est le plus simple. On balaye les noeuds d'un même niveau, avant de passer au niveau suivant. Ici on ne fera pas appel à la récursivité.

Il va falloir visiter les noeuds d'un même niveau et se souvenir qu'ensuite on va descendre voir chacun de leurs enfants qui deviendront eux même un souvenir...

Pour garder en mémoire les noeuds visités dont on ira voir plus tard les enfants, on les places dans une liste. Mais attention, il ne faut pas prendre le dernier de la liste pour la lecture mais le premier. On est donc en présence d'une pile de type fifo (first in first out).

fonction parcours_largeur(noeud_depart)
	visite = créer pile fifo
	ajouter noeud_depart à visite
	tant que visite n'est pas vide
		noeud recoit le premier élément de visite
			(pop, l'élément est supprimé de la liste)
		afficher(noeud)  #ou toute autre acion
		pour tout les descendants de noeud
			ajouter descendant à visite

Il s'agit de l'idée inverse de la précédente. Tant que l'on peut déscendre, on déscend. Dès que l'on ne peut plus, on remonte au noeud parent, que l'on a donc forcément croisé. Il va donc falloir se souvenir des noeuds que l'on n'a pas affiché car on voulait descendre. Dès que l'on remonte à un noeud, on veut afficher ses descendants. On est donc remonté au noeud juste précédent, donc le dernier dont on voulait se souvenir. On est donc en présence d'une pile de type LIFO (last in first of). En changeant la pile FIFO de l'algorihtme de parcours en largeur par une pile LIFO, on obtient l'algorithme de parcours en profondeur!

fonction parcours_profondeur(noeud_depart)
 	visite = créer pile lifo
 	ajouter noeud_depart à visite
 	tant que visite n'est pas vide
 		noeud recoit le dernier élément de visite
 			(pop, l'élément est supprimé de la liste)
 		afficher(noeud)  #ou toute autre acion
 		pour tout les descendants de noeud
 			ajouter descendant à visite
 

Il existe plusieurs type de parcours en profondeur. L'exemple ci-dessus correspond à un parcours préfixe. L'algorithme itératif précédent donne l'odre préfixe.

Dans le parcours prefixe, on lit la racine puis on parcourt récursivement son sous arbre gauche, puis son sous arbre droit.

Dans le parcours infixe, on parcourt récursivement son sous arbre gauche, on lit la racine, puis son sous arbre droit en lisant.

Dans le parcours sufixe, on parcourt récursivement son sous arbre gauche, puis son sous arbre droit en lisant, puis on lit la racine.

Ces parcours peuvent tous être codés en utilisant une fonction récursive. Selon, la méthode désirée, il suffira de changer la position de la ligne qui lit la racine du sous arbre traité (enlever les dièses sur la ligne désirée).

Affichage_XXXfixe(noeud_depart)
	si NON est_vide(noeud_depart):
		#Afficher valeur de noeud_depart  (pour préfixe)
		Affichage_XXXfixe(fils_gauche de noeud_depart)
		#Afficher valeur de noeud_depart  (pour infixe)
		Affichage_XXXfixe(fils_droit de noeud_depart)
		#Afficher valeur de noeud_depart  (pour sufixe)
 

Un arbre binaire de recherche ABR, est arbre pour lequel chaque noeud a une valeur clé que l'on peut ordonner (des nombres le plus souvent). Pour tous les noeuds de l'arbre, la clé de tous les noeuds du sous arbre gauche doivent être inférieure à sa clé et la clé de tous les noeuds du sous arbre droit lui sont supérieures.

Voici des exemples, attention, il ne suffit pas que tous les fils gauches soient infèreurs à leur père...

Du fait que cet arbre est ordonné, on peut aller plus vite qu'un parcours en largeur ou profondeur pour retrouver un noeud. A partir d'un noeud, si la clé cherchée est supérieure à la valeur du noeud, cela veut dire qu'il faut chercher à droite, sinon à gauche. Encore une fois on a un raisonnement récursif.

fonction chercher_clé(clé, noeud_depart):
	si noeud_depart est vide ou si clé = contenu du noeud_depart
		retourner noeud_depart
	si clé< contenu du noeud_depart:
		retourner (chercher_clé(clé, sous arbre à partir de fils Gauche du noeud_depart))
	retourner (chercher_clé(clé, sous arbre à partir fils Droit du noeud_depart))

Si votre arbre est construit recursivement, sous arbre à partir du fils droit du noeud est dans les faits fils gauche, puisque fils gauche aura lui même des fils etc...fils gauche est un sous arbre.

Pour insérer une clé dans un arbre, on peut facilement le faire en aménageant le parcours en largeur. Voici un algorithme récursif. L'idée est la suivante. Si la clé est plus grande que le noeud étudié, il faut partir vers la droite, si elle est egale c'est qu'il n'y a rien à faire (on renvoie l'abre initial), si elle est plus petite il faut partir à gauche et s'il n'y a pas de noeud c'est qu'il faut placer notre clé à cet endroit.

fonction inserer_clé(clé, noeud_visité)
	#on est arrivé à un emplacement vide où placer notre noeud
	si noeud_visité est vide:
		renvoyer un noeud de valeur clé et sans fils
	#on doit aller soir vers la droite soit vers la gauche pour descendre
	#la descente s'arrêtera lorsque le noeud visité sera vide
	si (clé < clé du noeud_visité)
		nouveau_noeud1 = inserer_clé(clé, fils gauche de noeud_visité)
		retourner (noeud ayant noeud_visité pour fils gauche, nouveau_noeud1 pour fils droit et la clé de noeud_visité pour clé)
	sinon si (clé > clé de noeud_visité)
		nouveau_noeud2 =inserer_clé(clé, a.filsD)
		retourner (noeud ayant noeud_visite pour fils gauche, nouveau_noeud2 pour fils droit et clé de noeud_visité pour clé)
	#si la clé n'est ni supérieure, ni inférieure,
	#elle est égale...donc elle est déjà dans l'arbre, on ne fait rien.
	retourner(noeud_visité)

1. blabla
2. blabla