144. Parcours Pré-Ordre d'un Arbre Binaire

Méthode Récursive

La mise en œuvre récursive dépend de trois éléments fondamentaux :

1. Définir les paramètres et la valeur de retour de la fonction récursive.
2. Établir la condition d'arrêt de base.
3. Définir la logique d'appel récursif pour un nœud unique.

/**
 * Définition pour un nœud d'arbre binaire.
 * struct NoeudArbre {
 *     int valeur;
 *     NoeudArbre *gauche;
 *     NoeudArbre *droit;
 *     NoeudArbre() : valeur(0), gauche(nullptr), droit(nullptr) {}
 *     NoeudArbre(int x) : valeur(x), gauche(nullptr), droit(nullptr) {}
 *     NoeudArbre(int x, NoeudArbre *gauche, NoeudArbre *droit) : valeur(x), gauche(gauche), droit(droit) {}
 * };
 */
class Solution {
public:
    vector<int> parcoursPreordre(NoeudArbre* racine) {
        vector<int> résultat;
        parcourir(racine, résultat);
        return résultat;
    }
private:
    void parcourir(NoeudArbre* noeud, vector<int> &vecteur) {
        if (!noeud) return;
        vecteur.push_back(noeud->valeur);
        parcourir(noeud->gauche, vecteur);
        parcourir(noeud->droit, vecteur);
    }
};

Les parcours en-ordre (94. Parcours en-ordre) et post-ordre (145. Parcours post-ordre) suivent une logique similaire. Il suffit d'interchanger l'ordre des appels récursifs.

Méthode Itérative

Parocurs Pré-Ordre

L'ordre d'accès et de traitmeent des nœuds est identique (la racine est traitée en premier). On traite un nœud en stockant sa valeur puis en empilant ses enfants droit puis gauche.

vector<int> parcoursPreordreIteratif(NoeudArbre* racine) {
    vector<int> résultat;
    if (!racine) return résultat;
    stack<NoeudArbre*> pile;
    pile.push(racine);
    while (!pile.empty()) {
        NoeudArbre* courant = pile.top();
        pile.pop();
        if (courant->droit) pile.push(courant->droit);
        if (courant->gauche) pile.push(courant->gauche);
        résultat.push_back(courant->valeur);
    }
    return résultat;
}

Parcours Post-Ordre

On adapte le parcours pré-ordre en inversant l'ordre d'empilement des enfants (gauche puis droit) pour obtenir un ordre « racine-droite-gauche ». Ensuite, on inverse le tableau résultat pour obtenir le post-ordre (gauche-droite-racine).

vector<int> parcoursPostordreIteratif(NoeudArbre* racine) {
    vector<int> résultat;
    if (!racine) return résultat;
    stack<NoeudArbre*> pile;
    pile.push(racine);
    while (!pile.empty()) {
        NoeudArbre* courant = pile.top();
        pile.pop();
        if (courant->gauche) pile.push(courant->gauche);
        if (courant->droit) pile.push(courant->droit);
        résultat.push_back(courant->valeur);
    }
    reverse(résultat.begin(), résultat.end());
    return résultat;
}

Parcours en-Ordre

Dans ce parcours, l'ordre d'accès aux nœuds diffère de leur ordre de traitement. La méthode itérative utilise un pointeur pour la navigation et une pile pour le traitement des nœuds.

vector<int> parcoursEnordreIteratif(NoeudArbre* racine) {
    vector<int> résultat;
    stack<NoeudArbre*> pile;
    NoeudArbre* courant = racine;
    while (courant || !pile.empty()) {
        while (courant) {
            pile.push(courant);
            courant = courant->gauche;
        }
        courant = pile.top();
        pile.pop();
        résultat.push_back(courant->valeur);
        courant = courant->droit;
    }
    return résultat;
}

Méthode Itérative Unifiée

Pour uniformiser l'écriture des trois parcours, on utilise un marqueur nullptr dans la pile. Lorsqu'un tel marqueur est désempilé, le prochain nœud dans la pile est celui à traiter.

Exemple : Parcours en-Ordre Unifié

vector<int> parcoursEnordreUnifié(NoeudArbre* racine) {
    vector<int> résultat;
    stack<NoeudArbre*> pile;
    if (racine) pile.push(racine);
    while (!pile.empty()) {
        NoeudArbre* sommet = pile.top();
        if (sommet) {
            pile.pop();
            // Empiler dans l'ordre inverse : droit, racine (marquée), gauche
            if (sommet->droit) pile.push(sommet->droit);
            pile.push(sommet);
            pile.push(nullptr); // Marqueur pour le traitement futur
            if (sommet->gauche) pile.push(sommet->gauche);
        } else {
            pile.pop(); // Retirer le marqueur nullptr
            NoeudArbre* noeudATraiter = pile.top();
            pile.pop();
            résultat.push_back(noeudATraiter->valeur);
        }
    }
    return résultat;
}

L'application aux parcours pré-ordre et post-ordre se fait en modifiant simplement l'ordre d'empilement des enfants et du marqueur.