Arbre binaire de recherche : définition et mise en oeuvre en C++

Les listes chaînées, les piles et les files d'attente sont des collections linéaires ; un arbre est une collection non linéaire. Dans un arbre général, chaque nœud peut avoir deux liens ou plus vers d'autres nœuds. Bien que les arbres généraux aient de nombreuses applications en informatique (comme les répertoires), nous rencontrons davantage d'arbres binaires, c'est-à-dire des arbres comportant un maximum de deux sous-arbres. Un cas particulier d'arbre binaire est appelé arbre binaire de recherche dans lequel les valeurs des nœuds du sous-arbre de gauche sont inférieures à la valeur de la racine, et les valeurs du sous-arbre de droite sont supérieures à la valeur de la racine. La figure ci-dessous montre un arbre binaire de recherche.

Le parcours d'un arbre binaire de recherche exige que chaque nœud de l'arbre soit traité une fois et une seule dans une séquence prédéterminée. Il existe trois types de traversées : préfixe, postfixe et infixe.

Parcours infixe

Dans le parcours dans l'ordre, le traitement de la racine se situe entre les deux sous-arbres. En d'autres termes, nous devons d'abord parcourir tout le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Cette règle doit être suivie dans chaque sous-arbre. Le parcours infixe de l’arbre de la figure ci-dessus nous donne la séquence suivante. La racine de l'arbre entier vient au milieu. Notez que dans le parcours infixe d'un arbre de recherche binaire, les valeurs sont traitées dans l'ordre croissant.

Parcours préfixe

Dans le parcours préfixe, le nœud racine est traité en premier, suivi de tous les nœuds du sous-arbre gauche parcourus en préfixe, puis de tous les nœuds du sous-arbre droit parcourus en préfixe. Le parcours préfixe de l’arbre de la figure ci-dessus nous donne la séquence suivante. Notez que la racine se trouve au début.

Parcours postfixe

Dans le parcours post-ordre, le traitement de la racine vient après le traitement de deux sous-arbres. En d'autres termes, nous devons d'abord parcourir le sous-arbre gauche, puis le sous-arbre droit et enfin la racine. Cette règle doit être suivie dans chaque sous-arbre. Le parcours post-ordre de l'arbre de la figure ci-dessus nous donne la séquence suivante. Notez que la racine de l'arbre entier se trouve à la fin.

Nous avons discuté trois parcours pour un arbre binaire de recherche (ABR). Lorsqu'un ABR est implémenté correctement, les valeurs des données dans l’ABR sont triées, ce qui signifie que nous pouvons rechercher plus facilement l'arbre (d'où le nom arbre binaire de recherche). Les trois parcours nous aident à construire un ABR, à rechercher un ABR et à détruire un ABR. Cependant, pour chaque problème, nous devons utiliser le bon parcours.

Classe ABR

Dans notre définition, nous définissons un nœud avec des attributs d'arbre, les données stockées dans le nœud donnees et deux pointeurs gauche (sous-arbre gauche) et droit (sous-arbre droit), dans certains livres comme "Algorithmique" écrit par Cormen, leiserson et d'autres, ils utilisent également un attribut parent pour référencer le parent de chaque nœud, mais dans notre définition, nous n'utilisons pas le parent et adaptons nos fonctions pour récupérer le parent si nécessaire.

Ce qui suit est la définition de la classe ABR :

Classe ABR

#ifndef ABR_H
#define ABR_H

#include <iostream>

using namespace std;

// Définition du noeud en tant que struct
template <typename T>
struct Noeud
{
    T donnees;
    Noeud <T>* gauche;
    Noeud <T>* droit;
};

// Définition de la classe Liste
template <class T>
class ABR
{
    private:
        Noeud <T>* racine;
        int compteur;
        Noeud <T>* CreerNoeud (const T& valeur);
        void detruire (Noeud <T>* ptr); // Fonction d'aide
        void inserer (const T& value, Noeud <T>*& ptr); // Fonction d'aide
        void infixe (Noeud <T>* ptr) const; // Fonction d'aide
        void prefixe (Noeud <T>* ptr) const; // Fonction d'aide
        void postfixe (Noeud <T>* ptr) const; // Fonction d'aide
        Noeud <T>* successeur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide
        Noeud <T>* predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide
        void supprimer (Noeud <T>* ptr, Noeud <T>* parent); // Fonction d'aide
        Noeud <T>* recherche (const T& value, Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide
    
    public:
        ABR ();
        ~ABR ();
        void inserer (const T& value);
        void detruire ();
        void supprimer (const T& value);
        Noeud <T>* recherche (const T& value) const;
        void infixe () const;
        void prefixe () const;
        void postfixe () const;
        int taille () const;
        bool estVide () const;
};
#endif
        

Pour les méthodes utilisées dans la classe nous les avons divisées en deux catégories ; les méthodes privées utilisées comme aide pour effectuer les actions réelles, et les méthodes publiques utilisées pour appeler les méthodes privées sans connaître la définition et la mise en œuvre réelles.

Dans les sections suivantes, nous discuterons de la mise en œuvre de chaque méthode en détail.

Le constructeur

Le constructeur initie la racine de l'ABR à NULL (ou 0) et compteur à 0.

// Constructeur
template <class T>
ABR <T> :: ABR():racine (0), compteur (0){}
        

Le destructeur

Le destructeur utilisé pour supprimer la racine et tous ses nœuds descendants, donc détruire l'arbre. Le destructeur appelle la méthode detruire utilisée pour effectuer le travail réel.

// Destructeur
template <class T>
ABR <T> :: ~ABR ()
{
    detruire(racine);
}
        

Détruire un ABR

Comment détruisons-nous un ABR ? La réponse est que nous le faisons nœud par nœud. Cependant, pour supprimer un nœud, le sous-arbre gauche et le sous-arbre droit doivent être vides. Cela suggère que la destruction d'un ABR nécessite un parcours postfixe car le dernier nœud qui doit être détruit est la racine. Nous devons détruire le sous-arbre gauche, puis détruire le sous-arbre droit, et enfin détruire la racine. Cela signifie que nous pouvons écrire un algorithme récursif comme indiqué ci-dessous :

1. Détruire le sous-arbre gauche.
2. Détruire le sous-arbre droit.
3. Supprimer la racine.

// La fonction d'aide (Récursive) appelée par le destructeur
template <class T>
void ABR <T> :: detruire (Noeud <T>* ptr)
{
    if (!ptr){return;}
    
    detruire (ptr -> gauche); // détruire le sous-arbre gauche
    detruire (ptr -> droit); // détruire le sous-arbre droit
    delete ptr; // détruire la racine
}
        

Insertion

Comment insérer des nœuds dans un arbre binaire de recherche ? La réponse est qu'il faut trouver la position du nœud à insérer. La recherche de la position doit commencer à partir de la racine. Il faut insérer la racine puis insérer le sous-arbre gauche ou le sous-arbre droit. Dans chaque sous-arbre, nous faisons la même chose. Cela signifie que nous pouvons écrire un algorithme récursif comme indiqué ci-dessous :

•  Si l'arbre est vide, insérez-le en tant que racine.
•  Insérer dans le sous-arbre de gauche si la valeur est inférieure à la valeur racine.
•  Insérer dans le sous-arbre de droite si la valeur est supérieure à la valeur racine.

// La fonction d'aide (Récursive) appelée par la fonction membre inserer
template <class T>
void ABR <T> :: inserer (const T& valeur, Noeud <T>*& ptr)
{
    // si l'arbre vide, inserer comme racine
    if (!ptr){
        ptr = CreerNoeud (valeur);
        return;
    }
    // si la valeur est inférieure à la valeur de racine, 
    // insérer le noeud dans le sous-arber gauche
    else if (valeur < ptr -> donnees){
        inserer (valeur, ptr -> gauche);
    }
    // Sinon, insérer le noeud dans le sous-arber droit
    else{
        inserer (valeur, ptr -> droit);
    }
}
        

Rechercher un noeud

La méthode de recherche, est plus simple, on compare la valeur de la clé avec la racine si elle ne correspond pas on continue la recherche dans le sous-arbre gauche ou droit, cette méthode par nature est récursive, voici l'algorithme :

1. Si l'arbre est vide, le nœud n’existe pas.
2. Si la valeur recherchée égale à la valeur de la racine, retourner la racine
3. Rechercher dans le sous-arbre de gauche si la valeur est inférieure à la valeur racine.
4. Rechercher dans le sous-arbre de droite si la valeur est supérieure à la valeur racine.

Cette méthode utilisait un paramètre parent (passé par référence) utilisé pour stocker le parent du nœud en question.

// Fonction d'aide (Récursive) appeler par la fonction membre recherche
template <class T>
Noeud <T>* ABR <T> :: recherche (const T& valeur, Noeud <T>* ptr, Noeud <T>*& parent) const
{
    if (!ptr){
        //Arbre est vide
        return NULL;
    }
    else if ((ptr->donnees) == valeur){
        // la valeur recherchée est stockée dans la racine
        return ptr;
    }
    else if (valeur < (ptr->donnees)){
        parent=ptr;
        // la valeur recherchée est dans le sous-arbre gauche
        return recherche (valeur, ptr->gauche, parent);
    }
    else{
        parent=ptr;
        // sinon, la valeur recherchée est dans le sous-arbre droit
        return recherche (valeur, ptr->droit, parent);
    }
}
        

Successeur d’un noeud.

Cette méthode permet de renvoyer le successeur d’un nœud qui est le nœud avec la valeur minimale dans son sous-arbre droit. Cette méthode utilisée lorsque l'on veut supprimer un nœud avec deux enfants

Cette méthode utilisait un paramètre parent (passé en référence) utilisé pour stocker le parent du nœud en question.

template <class T>
Noeud <T>* ABR <T> :: successeur (Noeud <T>* ptr, Noeud <T>*& parent) const{
    if (!ptr){return NULL;}

    Noeud <T>* courant = ptr;
    while (courant->gauche != 0){
        parent = courant;
        courant = courant -> gauche;

    }
    return courant;
}
        

Prédécesseur d’un noeud.

Cette méthode permet de renvoyer le prédécesseur d’un nœud qui est le nœud avec la valeur maximale dans son sous-arbre gauche. Cette méthode utilisée lorsque l'on veut supprimer un nœud avec deux enfants.

Cette méthode utilisait un paramètre parent (passé en référence) utilisé pour stocker le parent du nœud en question.

template <class T>
Noeud <T>* ABR <T> :: predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const{
    if (!ptr){return NULL;}

    Noeud <T>* courant = ptr;
    while (courant->droit != 0){
        parent = courant;
        courant = courant -> droit;
    }
    return courant;
}
        

Supprimer un nœud de l’ABR

L'opération de suppression d’un nœud dans un ABR est plus compliquée que l'ajout et la recherche. Principalement, cette opération peut être divisée en deux étapes :

1. Rechercher le nœud à supprimer ;
2. Si le nœud est trouvé, exécuter l'algorithme de suppression.

La première étape est identique à l'algorithme de recherche, sauf que nous devons tracer le parent du nœud actuel. La deuxième partie est plus délicate. Il y a trois cas, qui sont décrits ci-dessous.

Le noeud à supprimer n'a pas d'enfants.

Ce cas est assez simple. L'algorithme définit le lien correspondant du parent à NULL et supprime le noeud.

Le noeud à supprimer a un seul enfant.

Dans ce cas, le nœud est coupé de l'arbre et l'algorithme lie l'enfant unique (avec son sous-arbre) directement au parent du nœud supprimé.

Le noeud à supprimer a deux enfants.

C'est le cas le plus complexe. La solution standard est basée sur cette idée : on laisse le nœud à enlever où il est, mais on se débarrasse de sa valeur et on trouve une autre valeur à y stocker. Cette valeur est extraite d'un nœud en dessous du nœud en question, et c'est ce nœud qui est en fait supprimé de l'arbre. Maintenant la question quelle valeur devrions-nous prendre ? Simplement nous trouvons le successeur ou prédécesseur du nœud à supprimer, remplaçons la valeur du nœud en question par la valeur stockée dans le successeur (ou prédécesseur), puis supprimons le successeur (ou prédécesseur).

•  Le successeur d'un nœud est un nœud avec une valeur minimale dans son sous-arbre droit
•  Le prédécesseur d'un nœud est un nœud avec une valeur maximale dans son sous-arbre gauche

Notez que le nœud avec une valeur minimale (ou maximale) n'a pas d'enfant à gauche (ou à droite) et, par conséquent, sa suppression peut entraîner dans le premier ou le deuxième cas uniquement.

template <class T>
void ABR <T> :: supprimer (Noeud <T>* ptr, Noeud <T>* parent){
    
    if (ptr->gauche == 0 && ptr->droit == 0)  
    {
        cout << ptr->donnees << parent->donnees<< endl;
        if (ptr != racine)  
        {  
            if (parent->gauche == ptr)  
                parent->gauche = NULL;  
            else  
                parent->droit = NULL;  
        }  
        else  
            racine = NULL;  
  
        delete ptr;     
    } 
    else if (ptr->gauche && ptr->droit)  
    {
        Noeud <T>* pere = ptr;
        // ici vous pouvez utiliser le prédécesseur aussi  
        Noeud <T>* succ  = successeur(ptr->droit, pere);  
        int val = succ->donnees;  
        supprimer(succ, pere);  
        ptr->donnees = val;  
    } 
    else  
    {  
        Noeud <T>* enfant = (ptr->gauche)? ptr->gauche: ptr->droit;  
        if (ptr != racine)  
        {  
            if (ptr == parent->gauche)  
                parent->gauche = enfant;  
            else  
                parent->droit = enfant;  
        }  
  
        else  
            racine = enfant;  

        delete ptr;
    }    
}
        

Cette fonction prend deux paramètres : le nœud à supprimer et son parent (passé par référence)

Cette méthode est appelée par la méthode publique supprimer après avoir localisé le nœud

template <class T>
void ABR <T> :: supprimer (const T& valeur)
{
    Noeud <T>* parent = 0;  
    Noeud <T>* del = recherche(valeur, racine, parent);
    if(del == 0){
        cout << "Le noeud n'appartient pas a l'arbre" << endl;
    }
    else{
        supprimer(del, parent);
    }
}
        

Parcours infixe

// Fonction d'aide (Récursive) appeler par la fonction infixe
template <class T>
void ABR <T> :: infixe (Noeud <T>* ptr) const
{
    if (!ptr){return;}
    
    infixe (ptr -> gauche);
    cout << ptr -> donnees << '\t';
    infixe (ptr -> droit);
}
        

Parcours préfixe

// Fonction d'aide (Récursive) appeler par la fonction prefixe
template <class T>
void ABR <T> :: prefixe (Noeud <T>* ptr) const
{
    if (!ptr){return;}
    
    cout << ptr -> donnees << '\t';
    prefixe (ptr -> gauche);
    prefixe (ptr -> droit);
}
        

Parcours postfixe

// Fonction d'aide (Récursive) appeler par la fonction postfixe
template <class T>
void ABR <T> :: postfixe (Noeud <T>* ptr) const
{
    if (!ptr){return;}
    
    postfixe (ptr -> gauche);
    postfixe (ptr -> droit);
    cout << ptr -> donnees << '\t';
}
        

#ifndef ABR_H
#define ABR_H

#include <iostream>

using namespace std;

// Définition du noeud en tant que struct
template 
struct Noeud
{
    T donnees;
    Noeud <T>* gauche;
    Noeud <T>* droit;
};

// Définition de la classe Liste
template <class T>
class ABR
{
    private:
        Noeud <T>* racine;
        int compteur;
        Noeud <T>* CreerNoeud (const T& valeur);
        void detruire (Noeud <T>* ptr); // Fonction d'aide
        void inserer (const T& value, Noeud <T>*& ptr); // Fonction d'aide
        void infixe (Noeud <T>* ptr) const; // Fonction d'aide
        void prefixe (Noeud <T>* ptr) const; // Fonction d'aide
        void postfixe (Noeud <T>* ptr) const; // Fonction d'aide
        Noeud <T>* successeur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide
        Noeud <T>* predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide
        void supprimer (Noeud <T>* ptr, Noeud <T>* parent); // Fonction d'aide
        Noeud <T>* recherche (const T& value, Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide
    
    public:
        ABR ();
        ~ABR ();
        void inserer (const T& value);
        void detruire ();
        void supprimer (const T& value);
        Noeud <T>* recherche (const T& value) const;
        void infixe () const;
        void prefixe () const;
        void postfixe () const;
        int taille () const;
        bool estVide () const;
};
#endif
                    

#ifndef ABR_CPP
#define ABR_CPP

#include "abr.h"

// Constructeur
template <class T>
ABR <T> :: ABR():racine (0), compteur (0){}

// Destructeur
template <class T>
ABR <T> :: ~ABR ()
{
    detruire(racine);
}

template <class T>
Noeud <T>* ABR <T> :: CreerNoeud (const T& valeur){
    Noeud <T>* temp = new Noeud <T>;
    temp -> donnees = valeur;
    temp -> gauche = NULL;
    temp -> droit = NULL;
    return temp;
}

// Inserer un noeud
template <class T>
void ABR <T> :: inserer (const T& valeur)
{
    inserer (valeur, racine);
    compteur++;
}

// Rechercher un noeud
template <class T>
Noeud <T>* ABR <T> :: recherche (const T& valeur) const
{
    Noeud <T>* parent = 0;  
    return recherche (valeur, racine);
}

// Parcours infixe
template <class T>
void ABR <T> :: infixe () const
{
    infixe(racine);
}

// Parcours prefixe
template <class T>
void ABR <T> :: prefixe () const
{
    prefixe(racine);
}

// Parcours postfixe
template <class T>
void ABR <T> :: postfixe () const
{
    postfixe(racine);
}

// Nombre de noeud dans l'arbre
template <class T>
int ABR <T> :: taille () const
{
    return compteur;
}

template <class T>
bool ABR <T> :: estVide () const
{
    return (compteur == 0);
}

// La fonction d'aide (Récursive) appelée par le destructeur
template <class T>
void ABR <T> :: detruire (Noeud <T>* ptr)
{
    if (!ptr){return;}
    
    detruire (ptr -> gauche); // détruire le sous-arbre gauche
    detruire (ptr -> droit); // détruire le sous-arbre droit
    delete ptr; // détruire la racine
}

// LA fonction d'aide (Récursive) appelée par la fonction membre inserer
template <class T>
void ABR <T> :: inserer (const T& valeur, Noeud <T>*& ptr)
{
    // si l'arbre vide, inserer comme racine
    if (!ptr){
        ptr = CreerNoeud (valeur);
        return;
    }
    // si la valeur est inférieure à la valeur de racine, 
    // insérer le noeud dans le sous-arber gauche
    else if (valeur < ptr -> donnees){
        inserer (valeur, ptr -> gauche);
    }
    // Sinon, insérer le noeud dans le sous-arber droit
    else{
        inserer (valeur, ptr -> droit);
    }
}

// Fonction d'aide (Récursive) appeler par la fonction infixe
template <class T>
void ABR <T> :: infixe (Noeud <T>* ptr) const
{
    if (!ptr){return;}
    
    infixe (ptr -> gauche);
    cout << ptr -> donnees << '\t';
    infixe (ptr -> droit);
}

// Fonction d'aide (Récursive) appeler par la fonction prefixe
template <class T>
void ABR <T> :: prefixe (Noeud <T>* ptr) const
{
    if (!ptr){return;}
    
    cout << ptr -> donnees << '\t';
    prefixe (ptr -> gauche);
    prefixe (ptr -> droit);
}

// Fonction d'aide (Récursive) appeler par la fonction postfixe
template <class T>
void ABR <T> :: postfixe (Noeud <T>* ptr) const
{
    if (!ptr){return;}
    
    postfixe (ptr -> gauche);
    postfixe (ptr -> droit);
    cout << ptr -> donnees << '\t';
}

// Fonction d'aide (Récursive) appeler par la fonction membre recherche
template <class T>
Noeud <T>* ABR <T> :: recherche (const T& valeur, Noeud <T>* ptr, Noeud <T>*& parent) const
{
    if (!ptr){
        //Arbre est vide
        return NULL;
    }
    else if ((ptr->donnees) == valeur){
        // la valeur recherchée est stockée dans la racine
        return ptr;
    }
    else if (valeur < (ptr->donnees)){
        parent=ptr;
        // la valeur recherchée est dans le sous-arbre gauche
        return recherche (valeur, ptr->gauche, parent);
    }
    else{
        parent=ptr;
        // sinon, la valeur recherchée est dans le sous-arbre droit
        return recherche (valeur, ptr->droit, parent);
    }
}

template <class T>
Noeud <T>* ABR <T> :: successeur (Noeud <T>* ptr, Noeud <T>*& parent) const{
    if (!ptr){return NULL;}

    Noeud <T>* courant = ptr;
    while (courant->gauche != 0){
        parent = courant;
        courant = courant -> gauche;

    }
    return courant;
}

template <class T>
Noeud <T>* ABR <T> :: predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const{
    if (!ptr){return NULL;}

    Noeud <T>* courant = ptr;
    while (courant->droit != 0){
        parent = courant;
        courant = courant -> droit;
    }
    return courant;
}


template <class T>
void ABR <T> :: supprimer (const T& valeur)
{
    Noeud <T>* parent = 0;  
    Noeud <T>* del = recherche(valeur, racine, parent);
    if(del == 0){
        cout << "Le noeud n'appartient pas a l'arbre" << endl;
    }
    else{
        supprimer(del, parent);
    }
}


// Fonction d'aide (Récursive) appeler par la fonction membre supprimer
template <class T>
void ABR <T> :: supprimer (Noeud <T>* ptr, Noeud <T>* parent){
    
    if (ptr->gauche == 0 && ptr->droit == 0)  
    {
        cout << ptr->donnees << parent->donnees<< endl;
        if (ptr != racine)  
        {  
            if (parent->gauche == ptr)  
                parent->gauche = NULL;  
            else  
                parent->droit = NULL;  
        }  
        else  
            racine = NULL;  
  
        delete ptr;     
    } 
    else if (ptr->gauche && ptr->droit)  
    {
        Noeud <T>* pere = ptr;
        // ici vous pouvez utiliser le prédécesseur aussi  
        Noeud <T>* succ  = successeur(ptr->droit, pere);  
        int val = succ->donnees;  
        supprimer(succ, pere);  
        ptr->donnees = val;  
    } 
    else  
    {  
        Noeud <T>* enfant = (ptr->gauche)? ptr->gauche: ptr->droit;  
        if (ptr != racine)  
        {  
            if (ptr == parent->gauche)  
                parent->gauche = enfant;  
            else  
                parent->droit = enfant;  
        }  
  
        else  
            racine = enfant;  

        delete ptr;
    }    
}

#endif

#include "abr.cpp"

int main ( ){

    // Instanciation d'un ABR
    ABR <int> arbre;
    arbre.inserer(40);
    arbre.inserer(50);
    arbre.inserer(14);
    arbre.inserer(16);
    arbre.inserer(5);
    arbre.inserer(3);
    arbre.inserer(7);
    arbre.inserer(55);
    arbre.inserer(45);

    cout << '\n';
    cout << "Le parcours infixe de cet arbre est : "<< endl;
    arbre.infixe();
    cout << '\n';

    cout << '\n';
    cout << "Le parcours postfixe de cet arbre est : "<< endl;
    arbre.postfixe();
    cout << '\n';

    cout << '\n';
    cout << "Le parcours prefixe de cet arbre est : "<< endl;
    arbre.prefixe();
    cout << '\n';

    cout << '\n';
    if(arbre.recherche(3) != 0){
        cout << "Le noeud avec la cle 3 appartient a l'arbre" << endl;
    }
    else{
        cout << "Le noeud avec la cle 3 n'appartient pas a l'arbre" << endl;
    }

    if(arbre.recherche(60) != 0){
        cout << "Le noeud avec la cle 60 appartient a l'arbre" << endl;
    }
    else{
        cout << "Le noeud avec la cle 60 n'appartient pas a l'arbre" << endl;
    }

    arbre.supprimer(3);
    cout << '\n';
    cout << "Le parcours infixe de l'arbre apres la suppression de 3 devient : "<< endl;
    arbre.infixe();

    arbre.supprimer(40); 
    cout << '\n';
    cout << "Le parcours infixe de l'arbre apres la suppression 40 devient : "<< endl;
    arbre.infixe();

    return 0;
}
        

Résultat

Le parcours infixe de cet arbre est : 
3       5       7       14      16      40      45      50      55

Le parcours postfixe de cet arbre est :
3       7       5       16      14      45      55      50      40

Le parcours prefixe de cet arbre est :
40      14      5       3       7       16      50      45      55

Le noeud avec la cle 3 appartient a l'arbre
Le noeud avec la cle 60 n'appartient pas a l'arbre

Le parcours infixe de l'arbre apres la suppression de 3 devient :
5       7       14      16      40      45      50      55
Le parcours infixe de l'arbre apres la suppression 40 devient :
5       7       14      16      45      50      55