Gestion d'un arbre binaire par les classes

Commenter

Contenu du snippet

Ceci compléte la recherche des alogorithmes de base, dans la même série que la Pile,File voici : "la gestion élémentaire d'un arbre binaire en utilisant une classe dynamique".
Qu'est ce qu'un arbre binaire :
On peu concevoir un arbre binaire comme un noeud racine composé de deux branches (une gauche
et une droite)chaque brance est composé d'un noeud, lui-même composé de deux branches.
voir le NET pour plus d'info...
Celui-ci est utilisé comme cet exemple pour faire des tris.
L'exemple de test utilise un tri de char.
Ce code à été compilé avec Borland C++ 5.5 (sans Bug apparent)

Source / Exemple : 


#include <stdio.h>
#include <iostream>
 using namespace std;
 
//On va creer ici un arbre binaire 
//un arbre qui a 1 noeuds constitué de deux branches, un sur la gauche, qui contient 
//les valeurs inferieurs au noeud en cours, et une sur la droite, qui 
//contient les valeurs supérieures ... 

template <class T> class Cl_Arbre;

//--------------------------------------------------------
//                      DEBUT CLASSE Cl_Noeud
//--------------------------------------------------------
  template <class T> 
  class Cl_Noeud{ 
    private:
      static int NbrNoeuds;

    public: 
      Cl_Noeud *gauche; 
      Cl_Noeud *droite; 
      T valeur; 
      inline T & val()const{return valeur;};
      Cl_Noeud(){NbrNoeuds++;};
      ~Cl_Noeud(){delete gauche;delete droite;};
      friend class Cl_Arbre <T> ;
  };//end class 
//--------------------------------------------------------
//                      FIN CLASSE Cl_Noeud
//--------------------------------------------------------
  template<class T> 
  int Cl_Noeud<T>::NbrNoeuds = 0;
//--------------------------------------------------------
//                      DEBUT CLASSE Cl_Arbre
//--------------------------------------------------------
  template<class T> 
  class Cl_Arbre{ 
    private: 
      Cl_Noeud <T> *racine; 
      void Inserer (Cl_Noeud <T> *); 
      void Balayage(Cl_Noeud <T> *);
      Cl_Noeud <T> *DonnepRacine()const{return racine;};// renvoie un pointeur sur le pNoeud racine 
      Cl_Noeud <T> *Rechercher (const T)const; 

    public: 
      Cl_Arbre (){racine = NULL;} //constructeur
      ~Cl_Arbre (){delete racine;} //constructeur
      void Creer (const T); 
      void Supprimer(const T); 
      void Affichage(void); 
      void NbrNoeuds(void){cout << Cl_Noeud<T>::NbrNoeuds;}; 
  };//end class 
//--------------------------------------------------------
//                      FIN CLASSE Cl_Arbre
//--------------------------------------------------------
//------------------------------------------------------------------------------
// FONCTION      : Affichage
// DESCRIPTION   : Affiche l'arbre à l'écran
//-------------------------------------------------------------------------------
  template <class T> 
  void Cl_Arbre<T>::Affichage(){ 
 //Si racine différent de NULL alors il affiche l'arbre
   if(racine!=NULL) 
   //Affectation du pointeur racine à pNoeud
     Balayage(racine);
    else
       cout << "Arbre vide!" << endl;
   //end if
  }//end process 

//------------------------------------------------------------------------------
// FONCTION      : Balaye
// DESCRIPTION   : fonction recursive de balayage dans l'arbre
//-------------------------------------------------------------------------------
  template <class T> 
  void Cl_Arbre<T>::Balayage(Cl_Noeud<T> *pNoeud){ 

   //On traverse vers la gauche (valeurs inferieures), si il existe 
     if (pNoeud->gauche) Balayage(pNoeud->gauche); 

   //On affiche le noeud en cours 
     if (pNoeud) cout << pNoeud->valeur << "\n"; 

   //Et traverse vers la droite (valeurs superieurs) 
     if (pNoeud->droite) Balayage(pNoeud->droite); 

  }//end process 

//------------------------------------------------------------------------------
// FONCTION      : Creer
// DESCRIPTION   : Création d'un Noeud 
//-------------------------------------------------------------------------------
  template <class T> 
  void Cl_Arbre <T>::Creer(const T val){ 
  //Allocation memoire pour un nouveau pNoeud 
    Cl_Noeud <T> * pNoeudTmp = new Cl_Noeud <T>; 
  //Initialisation des pointeur pNoeud à NULL
    pNoeudTmp->gauche = NULL; 
    pNoeudTmp->droite = NULL; 
  //Transfert de la valeur 
    pNoeudTmp->valeur = val; 
  //Insérer dans l'arborescence de l'arbre 
    Inserer (pNoeudTmp); 
  }//end process
  
//------------------------------------------------------------------------------
// FONCTION      : Inserer
// DESCRIPTION   : Insertion d'un pNoeud dans l'arbre; 
//-------------------------------------------------------------------------------
  template <class T> 
  void Cl_Arbre<T>::Inserer(Cl_Noeud <T> *pNoeud){ 
  //Si le pNoeud est vide, on sort 
    if (!pNoeud) return; 
  
  //Si l'arbre est vide, on lui accroche le Noeud et on sort 
    if (racine == NULL){ 
      racine = pNoeud; 
      return; 
    }//end if 

  //Création de deux pointeurs de déplacement dans l'arbre et initilisation
    Cl_Noeud<T> * courant = racine; 
    Cl_Noeud<T> * precedent = NULL; 
  
  //On se déplace à travers l'arbre jusqu'a ce que courant atteint la valeur NULL
  //precedent memorise l'adresse du dernier Noeud
    while (courant){ 
      precedent = courant; 
      if (pNoeud->valeur < courant->valeur) 
        courant = courant->gauche; 
       else 
          courant = courant->droite; 
    }//end while
 
  //Maintenant on place le nouveau noeud dans la bonne branche
    if(pNoeud->valeur < precedent->valeur) 
      precedent->gauche = pNoeud; 
     else 
       precedent->droite = pNoeud; 
  }//end process 

//------------------------------------------------------------------------------
// FONCTION      : Supprimer
// DESCRIPTION   : Supprime une pNoeud de l arbre 
//      On peut obtenir un pointeur sur un pNoeud via la methode Rechercher(...); 
//-------------------------------------------------------------------------------
  template<class T> 
  void Cl_Arbre<T>::Supprimer(const T val){ 
  
    Cl_Noeud<T> *pNoeud = Rechercher(val);

  //Si le noeud est = NULL , on sort la valeur n'existe pas. 
    if (!pNoeud){
     cout << "Recherche infructueuse! impossible de trouver cette valeur." << endl;
     return; 
    }//end if

  //Créations 3 pointeurs pour mémoriser 
  //les paramétres de pointeurs du Noeuds à supprimer et la racine
    Cl_Noeud<T> *droite = pNoeud->droite; 
    Cl_Noeud<T> *gauche = pNoeud->gauche; 
    Cl_Noeud<T> *courant = racine; 
  
  //CAS 1 : La valeur à supprimer est dans le noeud racine
    if(pNoeud == racine){ 
    //On transfer le pointeur droite supérieur dans racine
      racine = droite; 

    //Si le pointeur gauche du noeud supprimé n'est pas NULL,
    //Il faut réinsérer le noeud qui à été coupé par la suppression
    //pour reconstruire notre arbre
      if(gauche) Inserer(gauche); 

    //On libere la mémoire du noeud contenant la valeur supprimée
      delete pNoeud;
      return; 
    }//end if 
  
  //CAS 2 : tous les autres cas
  // on fait un balayage à travers l'arborescence
    while(courant){ 
    //Si une des branches de ce noeud est celle que l'on recherche, 
    //on sort de la boucle while 
      if(courant->droite == pNoeud || courant->gauche == pNoeud) break;

    //Sinon, on continue
      if(pNoeud->valeur >= courant->valeur) 
        courant = courant->droite; 
       else 
         courant = courant->gauche; 
     }//end while 
  
    if(courant->droite == pNoeud) 
      courant->droite = droite; 
     else 
       courant->gauche = droite; 
  //end if

  //Accrochage du fils du Noeud disparu 
    if(gauche) Inserer(gauche); 
  
  //Enfin, on libère l'objet pNoeud de la mémoire
    delete pNoeud; 
    cout << "Noeud effacé!" << endl;
  }//end process 
  
//------------------------------------------------------------------------------
// FONCTION      : Rechercher
// DESCRIPTION   : Renvoie un pointeur sur un element 
//      de l'arbre qui est == a val 
//-------------------------------------------------------------------------------
  template <class T> 
  Cl_Noeud<T> *Cl_Arbre<T>::Rechercher(const T val)const{ 

  //Création d'un pointeur de mémorisation d'adresse de racine
    Cl_Noeud<T> *courant = racine; 
  
  //Si la valeur du pointeur n'est pas NULL on continue
    while(courant){ 
    //Si le Noeud a la bonne valeur, 
    //on renvoie l'adresse du pointeur courant sinon on continue
      if(courant->valeur == val) return courant; 

    //Si la valeur est inférieure, on control le noeud de droite
    //Si elle est supérieure, on contrôl le noeud de gauche
      if (val < courant->valeur) 
        courant = courant->gauche; 
       else 
         courant = courant->droite; 
    }//end while 

  //Si rien trouvé  on retourne la valeur NULL
    return NULL; 
  }//end process 
  

  
void main(void){ 
  //On cree un nouvel arbre, qui contiendra des entiers 
    Cl_Arbre <char> arbre; 
  
  //On le remplit de valeurs 
    arbre.Creer('C'); 
    arbre.Creer('A'); 
    arbre.Creer('X'); 
    arbre.Creer('Z'); 
    arbre.Creer('T'); 
    arbre.Creer('I'); 
    arbre.Creer('H'); 
    arbre.Creer('M');
  
  //En affichant, on se rend compte que l arbre est trié 
  //Magique ! 
    arbre.Affichage(); 
    cout << "\nFIN PROGRAM 1" << endl;
    arbre.Supprimer('Z'); 
    arbre.Affichage(); 
    cout << "\nFIN PROGRAM 2" << endl;
    arbre.NbrNoeuds();
}

Conclusion :


Ceci est un exemple de base (n'est peut-être pas la meilleur sollution
mais cela fonctionne.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (UKR6900)