Un parcours d'arbre est une façon d'ordonner les nœuds d'un arbre afin de les parcourir. On peut le voir comme une fonction qui à un arbre associe une liste de ses nœuds même si la liste n'est souvent pas explicitement construite par le parcours.
On distingue essentiellement deux types de parcours : le parcours en largeur et les parcours en profondeur. Parmi les parcours en profondeur, on distingue à nouveau le parcours préfixe, le parcours infixe et le parcours suffixe.
Le parcours en largeur consiste à parcourir l'arbre niveau par niveau. Les nœuds de niveau 0 sont sont d'abord parcourus puis les nœuds de niveau 1 et ainsi de suite. Dans chaque niveau, les nœuds sont parcourus de la gauche vers la droite. Le parcours en largeur de l'arbre ci-dessus parcours les nœuds dans l'ordre [0,1,8,2,4,9,13,3,5,6,10,14,15,7,11,12].
Le parcours en largeur se programme à l'aide d'une file (Fifo) de la manière suivante. Les méthodes ci-dessous sont écrite en pseudo-java afin d'en alléger la présentation. Une implémentation simpliste mais véritable de ces méthodes peut être consultée ici.
pl(Tree t) { Fifo fifo = new Fifo() // Création d'une file fifo.put(t.root) // Mise de la racine dans la file while(!fifo.empty()) { Node n = fifo.get(); // Nouveau noeud à traiter en tête de file traitement(n); // Traitement du noeud courant if (n.ls != nil) fifo.put(n.ls); // Ajout du fils gauche s'il existe if (n.rs != nil) fifo.put(n.rs); // Ajout du fils droit s'il existe } }
Les parcours en profondeur se définissent de manière récursive sur les arbres. Le parcours d'un arbre consiste à traiter la racine de l'arbre et à parcourir récursivement les sous-arbres gauche et droit de la racine. Les parcours préfixe, infixe et suffixe se distinguent par l'ordre dans lequel sont faits ces traitements.
Dans le parcours préfixe, la racine est traitée avant les appels récursifs sur les sous-arbres gauche et droit (faits dans cet ordre). Le parcours préfixe de l'arbre ci-dessus parcourt les nœuds dans l'ordre [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15].
Dans le parcours infixe, le traitement de la racine est fait entre les appels sur les sous-arbres gauche et droit. Le parcours infixe de l'arbre ci-dessus parcourt les nœuds dans l'ordre [3,2,1,5,4,6,7,0,9,11,10,12,8,14,13,15].
Dans le parcours suffixe, la racine est traitée après les appels récursifs sur les sous-arbres gauche et droit (faits dans cet ordre). Le parcours suffixe de l'arbre ci-dessus parcourt les nœuds dans l'ordre [3,2,5,7,6,4,1,11,12,10,9,14,15,13,8,0].
La définition récursive des trois parcours en profondeur en permet une programmation récursive très simple. Pour parcourir un arbre avec une des fonctions de parcours ci-dessous, on appelle la fonction avec la racine de l'arbre comme paramètre.
prefix(Node n) { traitement(n); if (n.ls != nil) prefix(n.ls); if (n.rs != nil) prefix(n.rs); }
infix(Node n) { if (n.ls != nil) infix(n.ls); traitement(n); if (n.rs != nil) infix(n.rs); }
suffix(Node n) { if (n.ls != nil) suffix(n.ls); if (n.rs != nil) suffix(n.rs); traitement(n); }
Dans un langage comme Java, il est souvent utile d'avoir des itérateurs permettant un parcours en profondeur d'un arbre. La programmation récursive se prête mal à la programmation d'un itérateur.
La classe Parcours définit un objet qui parcourt un arbre de manière générique. L'arbre est parcouru comme s'il s'agissait d'un mur qui serait longé par l'objet. L'objet part de la racine et commence à longer le mur en direction du fils gauche de la racine. Il continue à suivre ainsi la branche gauche jusqu'à un nœud qui n'a pas de fils gauche. L'objet contourne ce nœud pour suivre le mur jusqu'au fils droit de ce nœud. Si ce fils droit et également absent, l'objet remonte jusqu'au père de ce nœud. Chaque nœud est alors visité trois fois : une première fois lorsque l'objet provient du père du nœud, une seconde fois après le parcours du sous-arbre gauche du nœud et une troisième et dernière fois après le parcours du sous-arbre droit su nœud. Lorsque certains sous-arbres d'un nœud sont vides, plusieurs visites d'un même nœud se confondent même s'il faut bien les distinguer. En particulier, les trois visites d'une feuilles sont consécutives et se confondent en une seule visite.
Dans un premier temps, on suppose que chaque nœud possède une référence sur son père en plus des références sur ses fils gauche et droit. On suppose donc que la structure Node possède les champs suivants.
class Node { Node ls; // Fils gauche Node rs; // Fils droit Node f; // Père }
class Parcours { Node c; // Noeud courant // Quatre constantes pour désigner les différentes visites d'un noeud final int prefix = 0; // Première visite (Préfixe) final int infix = 1; // Deuxième visite (Infixe) final int suffix = 2; // Troisième visite (Suffixe) final int fini = 3; // Parcours terminé int st; // État : prefix, infix, suffix, ou fini // Constructeur Parcours (Tree t) { if (t.root != nil) { c = t.root; st = prefix; } else st = fini; } // Retourne l'état int state() { return st; } // Retourne le noeud courant et passe au noeud suivant Node next() { Node r = c; // Valeur de retour switch (st) { case prefix: // Première visite du noeud if (c.ls != nil) // Si le fils gauche existe, c = c.ls; // le noeud suivant est le fils gauche. else st = infix; // Sinon, on passe à la deuxième visite. break; case infix: // Deuxième visite du noeud if (c.rs != nil) { // Si le fils droit existe, c = c.rs; // le noeud suivant est le fils droit st = prefix; // et c'est la première visite de ce noeud. } else st = suffix; // Sinon, on passe à la troisième visite. break; case suffix: // Troisième visite du noeud if (c.f != nil) { // Si le père existe if (c == c.f.ls) { // et si le noeud est son fils gauche st = infix; // et c'est la deuxième visite du père } else { // Sinon st = suffix;// et c'est la troisième visite du père. } c = c.f; // le noeud suivant est le père } else st = fini; // Sinon, c'est terminé. } return r; } }
L'implémentation d'un itérateur préfixe à l'aide de la classe Parcours devient très simple.
class ParcoursPrefixe { Parours p; // Constructeur Parcours(Tree t) { p = new Parcours(t); } boolean hasNext() { while(p.state() != p.fini && p.state() != p.prefix) p.next(); return p.state() == p.prefix; } Node next() { if (hasNext()) return p.next(); else throw new NoSuchElementException() } }
L'implémentation d'un parcours infixe ou suffixe est très similaire. Il suffit de remplacer chaque occurence de p.p par p.i ou par p.s
On suppose maintenant que chaque nœud ne possède pas de référence sur son père en plus des références sur ses fils gauche et droit. On suppose donc que la structure Node possède uniquement les champs suivants.
class Node { Node ls; // Fils gauche Node rs; // Fils droit }
Dans l'implémentation de la classe Parcours, il est alors nécessaire de mémoriser le chemin de la racine au nœud courant afin de pouvoir remonter au père lorsque c'est nécessaire. La suite des nœuds de la racine au nœud courant est alors mémoriser dans une pile (Lifo). L'implémentation de la classe Parcours devient la suivante.
class Parcours { Node c; // Noeud courant Lifo b; // Branche de la racine au noeud courant // Le noeud courant n'est pas mis dans la pile. // Quatre constantes pour désigner les différentes visites d'un noeud final int prefix = 0; // Première visite (Préfixe) final int infix = 1; // Deuxième visite (Infixe) final int suffix = 2; // Troisième visite (Suffixe) final int fini = 3; // Parcours terminé int st; // État : p, i, s, ou f // Constructeur Parcours (Tree t) { b = new ListLifo(); // Création de la pile if (t.root != nil) { c = t.root; st = prefix; } else st = fini; } // Retourne l'état int state() { return st; } // Retourne le noeud courant et passe au noeud suivant Node next() { Node r = c; // Valeur de retour switch (st) { case prefix: // Première visite du noeud if (c.ls != nil) { // Si le fils gauche existe, b.put(c); // on ajoute le noeud courant à la branche c = c.ls; // et le noeud suivant est le fils gauche. } else st = infix; // Sinon, on passe à la deuxième visite. break; case i: // Deuxième visite du noeud if (c.rs != nil) { // Si le fils droit existe, b.put(c); // on ajoute le noeud courant à la branche, c = c.rs; // le noeud suivant est le fils droit st = prefix; // et c'est la première visite de ce noeud. } else st = suffix; // Sinon, on passe à la troisième visite. break; case s: // Troisième visite du noeud if (!b.empty()) { // Si la branche n'est pas vide, Node f = b.get(); // le père est retiré de la branche. if (c == f.ls) { // Si le noeud est son fils gauche, st = infix; // et c'est la deuxième visite du père } else { // Sinon st = suffix;// et c'est la troisième visite du père. } c = f; // le noeud suivant est le père } else { st = fini; // Sinon, c'est terminé. } } return r; } }
L'implémentation de la classe ParcoursPrefixe reste identique.
Au lieu d'utiliser un objet de la classe Parcours, le parcours préfixe peut être programmé de manière directe. On obtient alors une implémentation plus efficace. L'idée générale est de stocker dans la pile non pas le nœuds de la branche jusqu'au nœud courant mais de stocker les racines des sous-arbres qui restent à traiter. On peut remarquer que ces racines sont les fils droits de la branche jusqu'au nœud courant à chaque fois que la branche part à gauche.
class ParcoursPrefixe { Lifo b; // Pile des racines des sous-arbres à parcourir // Constructeur Parcours(Tree t) { b = new ListLifo(); // Création de la pile if (t.root != nil) b.put(t.root); // La racine est le premier noeud à traiter } boolean hasNext() { return !b.empty(); // La pile contient les racines des } // sous-arbres encore à traiter Node next() { if (hasNext()) { Node c = b.get(); // Noeud à traiter if (c.rs != nil) n.put(c.rs); // Empilement du fils droit if (c.ls != nil) n.put(c.ls); // Empilement du fils gauche return c; } else throw new NoSuchElementException() } }