Algorithmes et structures de données génériques

Parcours d’un arbre binaire

Un algorithme de parcours d’arbre est un procédé permettant d’accéder à chaque nœud de l’arbre. Un certain traitement est effectué pour chaque nœud (test, écriture, comptage, etc.), mais le parcours est indépendant de cette action et commun à des algorithmes qui peuvent effectuer des traitements très divers comme rechercher les enfants de Gontran, compter la descendance de Julie, compter le nombre de garçons, ajouter un fils à Paul, etc. On distingue deux catégories de parcours d’arbres : les parcours en profondeur et les parcours en largeur. Dans le parcours en profondeur, on explore branche par branche alors que dans le parcours en largeur on explore niveau par niveau.

Les différentes méthodes de parcours en profondeur d’un arbre

Il y a 6 types de parcours possibles (P : père, SAG : sous-arbre gauche, SAD : sousarbre droit). Nous ne considérons dans la suite de ce chapitre que les parcours gauche-droite. Les parcours droite-gauche s’en déduisent facilement par symétrie.Ces parcours sont appelés parcours en profondeur car on explore une branche de l’arbre le plus profond possible avant de revenir en arrière pour essayer un autre chemin.Dans un parcours d’arbre gauche-droite, un nœud est visité trois fois : • lors de la première rencontre du nœud, avant de parcourir le sous-arbre gauche. • après parcours du sous-arbre gauche, avant de parcourir le sous-arbre droit. • après examens des sous-arbres gauche et droit.L’action à effectuer sur le nœud peut se faire lors de la visite (a), (b) ou (c).

Parcours sur l’arbre binaire de l’arbre généalogique

Parcours préfixé Le premier type de parcours est appelé parcours préfixé. Il faut traiter le nœud lors de la première visite, puis explorer le sous-arbre gauche (en appliquant la même méthode) avant d’explorer le sous-arbre droit. Sur la Figure 58, Jonatan est traité avant son SAG (Pauline Sonia Paul) et avant son SAD (Gontran Antonine). La procédure se schématise comme suit : • traitement de la racine • traitement du sous-arbre gauche • traitement du sous-arbre droit Sur l’exemple, cela conduit au parcours de la Figure 65. Pour chaque nœud, on trouve le nom du nœud concerné, les éléments du SAG, puis les éléments du SAD.
Parcours infixé Dans un parcours infixé, le nœud est traité lors de la deuxième visite, après avoir traité le sous-arbre gauche, mais avant de traiter le sous-arbre droit. La Figure 66 indique l’ordre de traitement des nœuds de l’arbre généalogique. Un nœud se trouve entre son SAG et son SAD. Jonatan par exemple se trouve entre son SAG (Pauline Sonia Paul) et son SAD (Antonine Gontran). La procédure se schématise comme suit : • traitement du sous-arbre gauche • traitement de la racine • traitement du sous-arbre droit
Parcours postfixé En parcours postfixé, le nœud est traité lors de la troisième visite, après avoir traité le SAG et le SAD. La Figure 67 indique par exemple que Jonatan est traité après son SAG (Paul Sonia Pauline) et après son SAD (Antonine Gontran). La procédure à suivre est donnée ci-dessous : • traitement du sous-arbre gauche • traitement du sous-arbre droit • traitement de la racine
Parcours sur l’arbre binaire de l’expression arithmétique Sur l’arbre binaire de l’expression arithmétique, les parcours correspondent à une écriture préfixée, infixée ou postfixée de cette expression.
Parcours préfixé L’opérateur est traité avant ses opérandes
Parcours infixé L’opérateur se trouve entre ses deux opérandes.
L’expression infixée est ambiguë et peut être interprétée comme : a + (b * c) – d – e ou (a + b) * (c – d) – e Il faut utiliser des parenthèses pour lever l’ambiguïté. C’est la notation habituelle d’une expression arithmétique dans les langages de programmation. En l’absence de parenthèses, des priorités entre opérateurs permettent aux compilateurs de choisir une des interprétations possibles.
Parcours postfixé L’opérateur se trouve après ses opérandes.

Les algorithmes de parcours d’arbre binaire

Les fonctions de parcours découlent directement des algorithmes vus sur les exemples précédents. Le simple changement de la place de l’ordre d’écriture conduit à un traitement préfixé, infixé ou postfixé. La fonction toString(), passée en paramètre de prefixe() fournit une chaîne de caractères spécifiques de l’objet traité. Cette chaîne est imprimée lors du printf. La fonction toString() est dépendante de l’application et passée en paramètre lors de la création de l’arbre. Par défaut, les objets référencés dans chaque nœud sont des chaînes de caractères.
Algorithme de parcours préfixé // toString fournit la chaîne de caractères à écrire pour un objet donné static void prefixe (Noeud* racine, char* (*toString) (Objet*)) { if (racine != NULL) { printf (« %s « , toString (racine->reference)); prefixe (racine->gauche, toString); prefixe (racine->droite, toString); } }// parcours préfixé de l’arbre void prefixe (Arbre* arbre) { prefixe (arbre->racine, arbre->toString); }
Le déroulement de l’algorithme récursif prefixe() sur la Figure 62 où les pointeurs ont été remplacés pour l’explication par des adresses de 0 à 8 est schématisé sur la Figure 71. Les adresses des nœuds en allocation dynamique sont normalement quelconques et dispersées en mémoire. L’appel prefixe() avec le nœud racine 0 entraîne un appel récursif qui consiste à traiter le SAG, d’où un appel à prefixe() avec pour nouvelle racine 1 qui à son tour déclenche une cascade d’appels récursifs. Plus tard, on fera un appel à prefixe() avec un pointeur sur SAD en 8. Le déroulement de l’exécution de l’algorithme est schématisé ligne par ligne, de haut en bas, et de gauche à droite.