begin process at 2008 07 06 13:04:00
1 205 544 membres
121 nouveaux aujourd'hui
14 119 membres club

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

GESTION D'UN ARBRE BINAIRE PAR LES CLASSES


Information sur la source

Catégorie :Maths & Algorithmes Classé sous : algorithme, algo Niveau : Débutant Date de création : 29/05/2006 Date de mise à jour : 25/07/2006 18:21:44 Vu : 5 785

Note :
Aucune note

Commentaire sur cette source (1)
Ajouter un commentaire et/ou une note

Description

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

  • #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();
  • }
#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.
25 juillet 2006 18:21:44 :
changement des includes
  • signaler à un administrateur
    Commentaire de excrt le 30/05/2006 20:26:09

    OÙ EST LE FICHIER « mylib.h » ???
    tu devrais tenir le compte des noeuds dans Cl_Arbre et non dans Cl_Noeud ...

Ajouter un commentaire

Pub



Appels d'offres

Plugin Dialer outlook
Budget : 2 000€
Travail graphique- ill...
Budget : 1 000€
creation de marque et ...
Budget : 1 000€

Snippets en rapport

CalendriCode

Juillet 2008
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

VS Express FR Gratuit !

VS Express en français et 100% gratuit !

Téléchargements

Logiciels à télécharger sur le même thème :

Boutique

Boutique de goodies CodeS-SourceS