Introduction aux parcours d'arbre binaire

Les trois types de parcours d'arbre binaire constituent des opérations fondamentales en informatique. Chaque parcours peut être implémenté de deux manières : récursivement (plus lisible) ou itérativement (avec une pile, évitant les risques de débordement de pile). Ce guide présente des implémentations complètes avec des explications détaillées.

Définition d'un nœud d'arbre binaire

Créons d'abord une classe générique pour représenter un nœud :

class NoeudArbre {
    int valeur;
    NoeudArbre gauche;
    NoeudArbre droit;
    
    NoeudArbre() {}
    
    NoeudArbre(int val) {
        this.valeur = val;
    }
    
    NoeudArbre(int val, NoeudArbre g, NoeudArbre d) {
        this.valeur = val;
        this.gauche = g;
        this.droit = d;
    }
}

Parcours préordonné (racine → gauche → droit)

Principe : visiter d'abord le nœud courant, puis traiter récursivement le sous-arbre gauche, et enfin le sous-arbre droit.

Approche récursive

class Solution {
    public List<Integer> parcoursPreorde(NoeudArbre racine) {
        List<Integer> resultat = new ArrayList<>();
        traiterPreorde(racine, resultat);
        return resultat;
    }

    private void traiterPreorde(NoeudArbre actuel, List<Integer> resultat) {
        if (actuel == null) return;
        resultat.add(actuel.valeur);           // 1. Visiter la racine
        traiterPreorde(actuel.gauche, resultat);  // 2. Sous-arbre gauche
        traiterPreorde(actuel.droit, resultat);   // 3. Sous-arbre droit
    }
}

Approche itérative avec pile

En utilisant le principe LIFO de la pile, on empile d'abord le sous-arbre droit, puis le gauche, pour obtenir l'ordre « racine → gauche → droit » :

class Solution {
    public List<Integer> parcoursPreorde(NoeudArbre racine) {
        List<Integer> resultat = new ArrayList<>();
        if (racine == null) return resultat;
        
        Deque<NoeudArbre> pile = new LinkedList<>();
        pile.push(racine);
        
        while (!pile.isEmpty()) {
            NoeudArbre actuel = pile.pop();
            resultat.add(actuel.valeur);         // Visiter la racine
            
            // Empiler droit en premier (traitement différé), puis gauche
            if (actuel.droit != null) pile.push(actuel.droit);
            if (actuel.gauche != null) pile.push(actuel.gauche);
        }
        return resultat;
    }
}

Parcours infixé (gauche → racine → droit)

Principe : traiter d'abord le sous-arbre gauche, visiter la racine, puis traiter le sous-arbre droit.

Approche récursive

class Solution {
    public List<Integer> parcoursInfixe(NoeudArbre racine) {
        List<Integer> resultat = new ArrayList<>();
        traiterInfixe(racine, resultat);
        return resultat;
    }

    private void traiterInfixe(NoeudArbre actuel, List<Integer> resultat) {
        if (actuel == null) return;
        traiterInfixe(actuel.gauche, resultat);   // 1. Sous-arbre gauche
        resultat.add(actuel.valeur);               // 2. Visiter la racine
        traiterInfixe(actuel.droit, resultat);    // 3. Sous-arbre droit
    }
}

Approche itérative avec pile

On descend d'abord jusqu'au nœud le plus à gauche en empilant les nœuds rencontrés, puis on remontre en visitant les racines et en taritant les sous-arbres droits :

class Solution {
    public List<Integer> parcoursInfixe(NoeudArbre racine) {
        List<Integer> resultat = new ArrayList<>();
        Deque<NoeudArbre> pile = new LinkedList<>();
        NoeudArbre courant = racine;
        
        while (courant != null || !pile.isEmpty()) {
            // Descendre jusqu'au nœud extrême gauche
            while (courant != null) {
                pile.push(courant);
                courant = courant.gauche;
            }
            
            // Dépiler et visiter le nœud
            courant = pile.pop();
            resultat.add(courant.valeur);
            
            // Passer au sous-arbre droit
            courant = courant.droit;
        }
        return resultat;
    }
}

Parcours postordonné (gauche → droite → racine)

Principe : traiter d'abord le sous-arbre gauche, puis le droit, et enfin visiter la racine.

Approche récursive

class Solution {
    public List<Integer> parcoursPostorde(NoeudArbre racine) {
        List<Integer> resultat = new ArrayList<>();
        traiterPostorde(racine, resultat);
        return resultat;
    }

    private void traiterPostorde(NoeudArbre actuel, List<Integer> resultat) {
        if (actuel == null) return;
        traiterPostorde(actuel.gauche, resultat);   // 1. Sous-arbre gauche
        traiterPostorde(actuel.droit, resultat);    // 2. Sous-arbre droit
        resultat.add(actuel.valeur);                // 3. Visiter la racine
    }
}

Approche itérative - Méthode 1 : inversion du parcours préordonné

On modifie le parcours préordonné pour obtenir l'ordre « racine → droit → gauche », puis on inverse la séquence résultat :

class Solution {
    public List<Integer> parcoursPostorde(NoeudArbre racine) {
        List<Integer> resultat = new ArrayList<>();
        if (racine == null) return resultat;
        
        Deque<NoeudArbre> pile = new LinkedList<>();
        pile.push(racine);
        
        while (!pile.isEmpty()) {
            NoeudArbre actuel = pile.pop();
            resultat.add(actuel.valeur);           // Ordre : racine
            
            // Empiler gauche en premier, droit ensuite
            if (actuel.gauche != null) pile.push(actuel.gauche);
            if (actuel.droit != null) pile.push(actuel.droit);
        }
        
        Collections.reverse(resultat);            // Inverser : gauche → droit → racine
        return resultat;
    }
}

Approche itérative - Méthode 2 : technique de marquage

On utilise un marqueur null pour distinguer les nœuds déjà traités des nœuds à traiter :

class Solution {
    public List<Integer> parcoursPostorde(NoeudArbre racine) {
        List<Integer> resultat = new ArrayList<>();
        if (racine == null) return resultat;
        
        Deque<NoeudArbre> pile = new LinkedList<>();
        pile.push(racine);
        
        while (!pile.isEmpty()) {
            NoeudArbre actuel = pile.pop();
            if (actuel != null) {
                pile.push(actuel);                 // Empiler la racine
                pile.push(null);                   // Marqueur pour traitement ultérieur
                if (actuel.droit != null) pile.push(actuel.droit);
                if (actuel.gauche != null) pile.push(actuel.gauche);
            } else {
                resultat.add(pile.pop().valeur);   // Traitement de la racine
            }
        }
        return resultat;
    }
}

Tableau comparatif des parcours

L'approche récursive offre une lisibilité supérieure, tandis que l'approche itérative nécessite une bonne maîtrise des opérations sur pile (particulièrement pour les parcours infixé et postordonné). En pratique, la récursion convient aux arbres de faible profondeur, tandis que l'itération est préférable pour les arbres profonds afin d'éviter les débordements de pile d'exécution.