Parcours d'arbres

Introduction

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.

Parcours en largeur

Définition et exemple

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].

Programmation

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
    }
}

Parcours en profondeurs

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.

Définitions et exemples

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].

Programmation récursive

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);
}

Programmation itérative

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.

Avec les liens pères dans les nœuds

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

Sans les liens père dans les nœuds

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.

Parcours préfixe amélioré

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()
    }
}