Erreurs courantes en manipulation d'arbres

1. Erreur : la fonction non-void 'inorderTraversal' devrait retourner une valeur [-Wreturn-type] Quelle valeur devrait retourenr l'implémentation récursive ? Un vector ?
2. Aucune fonction membre correspondante pour l'appel 'push' Cause : le type de la stack a été défini comme (TreeNode) alors qu'il devrait être (TreeNode*)

Différents parcuors d'arbres

public:
    vector<int> parcoursInfixe(NoeudArbre* racine) {
        if (!racine) {
            return;
        }

        vector<int> resultat;
        parcoursInfixeRecursif(racine, resultat);
        return resultat;
    }
    
    void parcoursInfixeRecursif(NoeudArbre* racine, vector<int>& resultat) {
        if(!racine) return;
        parcoursInfixeRecursif(racine->gauche, resultat);
        resultat.push_back(racine->valeur);
        parcoursInfixeRecursif(racine->droite, resultat);
    }

Parcours préfixe itératif

void parcoursPrefixe(NoeudArbre* racine, vector<int>& resultat) {
    pile<NoeudArbre*> p;
    p.push(racine);
    while(!p.empty()){
        racine = p.top();
        p.pop();
        resultat.push_back(racine->valeur);
        if(racine->droite) p.push(racine->droite);
        if(racine->gauche) p.push(racine->gauche);
    }
}

Parcours postfixe itératif

pile<NoeudArbre*> p1;
pile<NoeudArbre*> p2;
p1.push(racine); 
while(!p1.empty()){
    racine = p1.top();
    resultat.push_back(racine->valeur);
    p2.push(racine);
    p1.pop();
    if(racine->gauche) p1.push(racine->gauche);
    if(racine->droite) p1.push(racine->droite);
}
while(!p2.empty()){
    resultat.push_back(p2.top()->valeur);
    p2.pop();
}

Parcours infixe itératif

pile<NoeudArbre*> p;
while(!p.empty() || racine){
    if(racine){
        p.push(racine);
        racine = racine->gauche;
    } else{
        racine = p.top();
        resultat.push_back(racine->valeur);
        p.pop();
        racine = racine->droite;
    }
}

Méthode itérative unifiée

p.push(racine);
while(!p.empty()){
    racine = p.top();
    if(racine){
        p.pop();
        if(racine->droite) p.push(racine->droite);
        p.push(racine);
        p.push(nullptr);
        if(racine->gauche) p.push(racine->gauche);
    } else{
        p.pop();
        racine = p.top();
        p.pop();
        resultat.push_back(racine->valeur);
    }
}

Parcours par niveaux d'un arbre

vector<vector<int> > resultat;
if(!racine) return resultat;
            
file<NoeudArbre*> f;
f.push(racine);
while(!f.empty()){
    vector<int> niveauActuel;
    int taille = f.size();
    for(int i = 0; i < taille; i++){
        racine = f.front();
        f.pop();
        niveauActuel.push_back(racine->valeur);
        if(racine->gauche) f.push(racine->gauche);
        if(racine->droite) f.push(racine->droite); 
    }
    resultat.push_back(niveauActuel);
}
return resultat;

Vue droite d'un arbre (méthode DFS)

vector<int> vueDroite(NoeudArbre* racine) {
    int profondeur = 0;
    if(!racine) return resultat;
    parcoursProfondeur(racine, 0);
    return resultat;
}
    
void parcoursProfondeur(NoeudArbre* racine, int niveau){
    if(!racine) return;
    if(niveau == resultat.size()){
        resultat.push_back(racine->valeur);
    }
    niveau++;
    parcoursProfondeur(racine->droite, niveau);
    parcoursProfondeur(racine->gauche, niveau);
}

Arbre N-aire

class Noeud{
    int valeur;
    vector<Noeud*> enfants;
}

vector<vector<int> > resultat;
if(!racine) return resultat;
    file<Noeud*> f;
    f.push(racine);
    while(!f.empty()){
        int taille = f.size();
        vector<int> niveau;
        for(int i = 0; i < taille; i++){
            racine = f.front();
            f.pop();
            niveau.push_back(racine->valeur);
            for(int i = 0; i < racine->enfants.size(); i++){
                if(racine->enfants[i]) f.push(racine->enfants[i]);
            }
        }
        resultat.push_back(niveau);
    }
return resultat;

Connexion des nœuds frères

while(!f.empty()){
    int taille = f.size();
    Noeud* precedent;
    precedent = f.front();            
    for(int i = 0; i < taille; i++){                
        Noeud* courant;
        if(i == 0){
            courant = f.front();
            precedent = f.front();
        } else{
            courant = f.front();
            precedent->suivant = courant;
            precedent = precedent->suivant;
        }                                
        f.pop();
        if(courant->gauche) f.push(courant->gauche);
        if(courant->droite) f.push(courant->droite);
                
        if(i == taille-1){
            precedent->suivant = nullptr;
        }
    }
}
return racine;

Connexion des nœuds frères (version récursive)

Noeud* connecterFreres(Noeud* racine) {
    if(!racine) return racine;        
    if(racine->gauche){
        racine->gauche->suivant = racine->droite;
        if(racine->suivant) racine->droite->suivant = racine->suivant->gauche;
    }
    connecterFreres(racine->gauche);
    connecterFreres(racine->droite);
    return racine;
}

Symétrie d'un arbre (comparaison récursive)

bool comparer(NoeudArbre* gauche, NoeudArbre * droite){
    if(!gauche && !droite) return true;
    else if(!droite || !gauche) return false;
    else if(gauche->valeur != droite->valeur) return false;
    else{
        bool a = comparer(gauche->gauche, droite->droite);
        bool b = comparer(gauche->droite, droite->gauche);
        return a && b;
    }
}

Vérification de sous-arbre (récursif)

bool estSousArbre(NoeudArbre* racine, NoeudArbre* sousRacine) {
    if(!racine && !sousRacine) return true;
    if(!racine || !sousRacine) return false;
    if(comparer(racine, sousRacine)) return true;
    return estSousArbre(racine->gauche, sousRacine) || estSousArbre(racine->droite, sousRacine);
}

Profondeur d'un arbre N-aire

int obtenirProfondeur(Noeud* racine)
    if(!racine) return 0;
    int maxProf = 0;
    for(int i = 0; i < racine->enfants.size(); i++){
        maxProf = max(maxProf, obtenirProfondeur(racine->enfants[i]));
    }
    return maxProf + 1;
}

Comptage des nœuds d'un arbre (récursif)

int compterNoeuds(NoeudArbre* racine) {
    if (racine == nullptr) return 0;
    NoeudArbre* gauche = racine->gauche;
    NoeudArbre* droite = racine->droite;
    int hauteurGauche = 0, hauteurDroite = 0;
    while (gauche) {  
        gauche = gauche->gauche;
        hauteurGauche++;
    }
    while (droite) { 
        droite = droite->droite;
        hauteurDroite++;
    }
    if (hauteurGauche == hauteurDroite) {
        return (2 << hauteurGauche) - 1;
    }
    return compterNoeuds(racine->gauche) + compterNoeuds(racine->droite) + 1;
}

Arbre binaire équilibré

bool estEquilibre(NoeudArbre* racine) {
    if(!racine) return true;        
    if(obtenirHauteur(racine) != -1)
        return true;
    return false;   
}
    
int obtenirHauteur(NoeudArbre *racine){
    if(!racine) return 0;
    int gauche = obtenirHauteur(racine->gauche);
    int droite = obtenirHauteur(racine->droite);
    if(gauche == -1) return -1;
    if(droite == -1) return -1;
    if(abs(gauche - droite) > 1) return -1;
    else return 1 + max(gauche, droite);
}

Obtenir tous les chemins d'un arbre binaire

vector<string> cheminsArbreBinaire(NoeudArbre* racine) {
    vector<string > resultat;
    vector<int >chemin;
    if(!racine) return resultat;
    parcours(racine, chemin, resultat);
    return resultat;
}
    
void parcours(NoeudArbre * courant ,vector<int>&chemin ,vector<string>&resultat  ){
    chemin.push_back(courant->valeur);
    if(!courant->gauche && !courant->droite){
        string s;
        for(int i = 0; i < chemin.size() - 1; i++){
            s += to_string(chemin[i]);
            s += "->";
        }
        s += to_string(chemin[chemin.size()-1]);
        resultat.push_back(s);
        return;        
    }
    if(courant->gauche) {
        parcours(courant->gauche, chemin, resultat);
        chemin.pop_back();
    }
    if(courant->droite) {
        parcours(courant->droite, chemin, resultat);
        chemin.pop_back();
    }
}

Version simplifiée récursive

void compter(NoeudArbre *racine,string chemin,vector &resultat){ chemin+=to_string(racine->valeur); if(!racine->gauche&&!racine->droite){ resultat.push_back(chemin); return ; } if(racine->gauche) { compter(racine->gauche,chemin+"->",resultat) ; } if(racine->droite) { compter(racine->droite,chemin+"->",resultat) ; } }

Version itérative

vector cheminsArbreBinaire(NoeudArbre* racine) { pile<NoeudArbre > pileNoeuds; pile pileChemins; vector resultat; if(!racine) return resultat; pileNoeuds.push(racine); pileChemins.push(to_string(racine->valeur)); while(!pileNoeuds.empty()){ NoeudArbre noeud = pileNoeuds.top(); pileNoeuds.pop(); string chemin = pileChemins.top(); pileChemins.pop(); if(!noeud->gauche && !noeud->droite){ resultat.push_back(chemin); } if(noeud->droite){ pileNoeuds.push(noeud->droite); pileChemins.push(chemin+"->"+to_string(noeud->droite->valeur)); } if(noeud->gauche){ pileNoeuds.push(noeud->gauche); pileChemins.push(chemin+"->"+to_string(noeud->gauche->valeur)); } } return resultat; }

Somme des feuilles gauches : Pour déterminer si un nœud est une feuille gauche, on doit vérifier depuis son parent

if(noeud->gauche && !noeud->gauche->droite && !noeud->gauche->gauche)

Si vous devez parcourir tout l'arbre, la fonction récursive ne doit pas avoir de valeur de retour. Si vous devez parcourir un chemin spécifique, la fonction récursive doit avoir une valeur de retour !

Trouver la valeur de la feuille gauche du dernier niveau

int maxProfondeur = INT_MIN;
    int valeurCible;
    int trouverFeuilleGaucheInferieure(NoeudArbre* racine) {
        parcours(racine, 0);
        return valeurCible;
    }
    void parcours(NoeudArbre* racine, int longueurGauche){
        if(!racine->gauche && !racine->droite) {
            if(longueurGauche > maxProfondeur){
                valeurCible = racine->valeur;
                maxProfondeur = longueurGauche;
            }
        }
        if(racine->gauche) parcours(racine->gauche, longueurGauche+1);
        if(racine->droite) parcours(racine->droite, longueurGauche+1);
    }

Somme des chemins

bool aSommeChemin(NoeudArbre* racine, int sommeCible) {
       if(dfs(racine, sommeCible) == -1) return true;
       return false;    
    }
    
    int  dfs(NoeudArbre * racine, int sommeRestante){
        if(!racine) return 0;
        sommeRestante -= racine->valeur;
        if(sommeRestante == 0 && !racine->gauche && !racine->droite) return -1;
        if(dfs(racine->gauche, sommeRestante) == -1) return -1;
        if(dfs(racine->droite, sommeRestante) == -1) return -1;
        return 0;
    }

bool aSommeChemin(NoeudArbre* racine, int somme) {
        if (racine == nullptr) return false;
        if (!racine->gauche && !racine->droite && somme == racine->valeur) {
            return true;
        }
        return aSommeChemin(racine->gauche, somme - racine->valeur) || aSommeChemin(racine->droite, somme - racine->valeur);
    }

vector<vector<int> >resultat;
    vector<int> chemin;
    vector<vector<int>> cheminsSomme(NoeudArbre* racine, int sommeCible) {
                if(!racine) return resultat;
        chemin.push_back(racine->valeur);
        dfs(racine , sommeCible - racine->valeur);
        return resultat;
    }
    
    void dfs(NoeudArbre* racine, int reste){
            if(!racine->gauche && !racine->droite && reste == 0) {
                resultat.push_back(chemin);
                return;
            }
            if(racine->gauche){ 
                chemin.push_back(racine->gauche->valeur);
                dfs(racine->gauche, reste - racine->gauche->valeur);
                chemin.pop_back();
            }
            if(racine->droite){
                chemin.push_back(racine->droite->valeur);
                dfs(racine->droite, reste - racine->droite->valeur);
                chemin.pop_back();
            }
    }

Construction d'un arbre binaire à partir de parcours

NoeudArbre* construire(vector<int>& infixe, vector<int>& postfixe) {
    if (postfixe.size() == 0) return nullptr;
    
    int valeurRacine = postfixe[postfixe.size() - 1];
    NoeudArbre* racine = new NoeudArbre(valeurRacine);

    if (postfixe.size() == 1) return racine;

    int indexSeparateur;
    for (indexSeparateur = 0; indexSeparateur < infixe.size(); indexSeparateur++) {
        if (infixe[indexSeparateur] == valeurRacine) break;
    }

    vector<int> infixeGauche(infixe.begin(), infixe.begin() + indexSeparateur);
    vector<int> infixeDroite(infixe.begin() + indexSeparateur + 1, infixe.end());

    postfixe.resize(postfixe.size() - 1);
    
    vector<int> postfixeGauche(postfixe.begin(), postfixe.begin() + infixeGauche.size());
    vector<int> postfixeDroite(postfixe.begin() + infixeGauche.size(), postfixe.end());

    racine->gauche = construire(infixeGauche, postfixeGauche);
    racine->droite = construire(infixeDroite, postfixeDroite);

    return racine;
}

Optimisation : utiliser des indices au lieu de créer de nouveaux vecteurs

NoeudArbre* construireMaximum(vector<int>& nums) {
    return construireMax(nums, 0, nums.size());
}
    
NoeudArbre* construireMax(vector<int>& v, int gauche, int droite) {
    if(gauche >= droite) return nullptr;
    
    int maxIndex = gauche;
    for(int i = gauche + 1; i < droite; i++){
        if(v[maxIndex] < v[i]) {
            maxIndex = i;
        }
    }
    
    NoeudArbre* noeud = new NoeudArbre(v[maxIndex]);
    noeud->gauche = construireMax(v, gauche, maxIndex);
    noeud->droite = construireMax(v, maxIndex + 1, droite);
    
    return noeud;
}

Fusion d'arbres binaires

NoeudArbre* fusionnerArbres(NoeudArbre* arbre1, NoeudArbre* arbre2) {
    if (arbre1 == nullptr) return arbre2;
    if (arbre2 == nullptr) return arbre1;
    
    file<pair<NoeudArbre*, NoeudArbre*>> f;
    f.push({arbre1, arbre2});
    
    while(!f.empty()) {
        auto paire = f.front();
        f.pop();
        NoeudArbre* noeud1 = paire.first;
        NoeudArbre* noeud2 = paire.second;
        
        noeud1->valeur += noeud2->valeur;
        
        if (noeud1->gauche != nullptr && noeud2->gauche != nullptr) {
            f.push({noeud1->gauche, noeud2->gauche});
        }
        if (noeud1->droite != nullptr && noeud2->droite != nullptr) {
            f.push({noeud1->droite, noeud2->droite});
        }
        
        if (noeud1->gauche == nullptr && noeud2->gauche != nullptr) {
            noeud1->gauche = noeud2->gauche;
        }
        if (noeud1->droite == nullptr && noeud2->droite != nullptr) {
            noeud1->droite = noeud2->droite;
        }
    }
    return arbre1;
}

Version récursive de la fusion

NoeudArbre* fusionnerArbresRecursif(NoeudArbre* racine1, NoeudArbre* racine2) {
    if(!racine1) return racine2;
    if(!racine2) return racine1;
    
    racine1->valeur += racine2->valeur;
    racine1->gauche = fusionnerArbresRecursif(racine1->gauche, racine2->gauche);
    racine1->droite = fusionnerArbresRecursif(racine1->droite, racine2->droite);
    return racine1;
}