Arbre Binaire de Recherche générique

Arbre Binaire de Recherche générique - C++ - Programmation

Marsh Posté le 16-10-2005 à 01:24:08    

Yo,
 
   Alors voilà j'ai fait ma petite classe ABR générique qui marche pas trop mal, manque plus que des trucs tordus genre les fonctions de réequilibrage de l'arbre.
 
   Je poste surtout ce code pour entendre des critiques sur ma façon de m'y prendre (je suis un noob en C++), histoire d'éviter les mauvaises habitudes.
 
   J'ai surement oublié grave de trucs.
 
PS : Taz, tappe pas trop fort stp  :sweat:  
 
La classe Noeud (bon là cash il y a un gros defaut c'est *fils_gauche et *fils_droit qui sont en public, bein oué ... faudrai que je change apres) :

Code :
  1. //Fichier Noeud.h
  2. #include <cstdlib>
  3. #include <iostream>
  5. using namespace std;
  7. template <class Type>
  8. class Noeud
  9. {
  10.       Type element;
  12.       public:
  13.              Noeud<Type> *fils_gauche;
  14.              Noeud<Type> *fils_droit;
  15.              //Constructeur
  16.              Noeud(Type el=0, Noeud<Type> *f_g=NULL, Noeud<Type> *f_d=NULL);
  17.              //Destructeur
  18.              ~Noeud();
  19.              //Accesseu element
  20.              Type get_element();
  21.              //Accesseur fils_gauche
  22.              Noeud<Type> *get_fg();
  23.              //Accesseur fils_droit
  24.              Noeud<Type> *get_fd();
  25.              //Effacer
  26.              void effacer(Noeud<Type> *n);           
  27.          //Surcharge de <
  28.          bool operator<(Noeud<Type> b);
  29.          //Cloner un noeud
  30.          Noeud<Type> *clone(Noeud<Type> *n);
  31.          //Cloner this
  32.              Noeud<Type> *clone();
  33. };
  35. template <class Type>
  36. Noeud<Type>::Noeud(Type el, Noeud<Type> *f_g, Noeud<Type> *f_d)
  37. {
  38.                          element = el;
  39.                          fils_gauche = f_g;
  40.                          fils_droit = f_d;
  41. }
  43. template <class Type>
  44. Noeud<Type>::~Noeud()
  45. {
  46.    // ??? Je pense qu'il fo rien mettre la, pas sur
  47. }
  49. template <class Type>
  50. Type Noeud<Type>::get_element()
  51. {
  52.      return element;
  53. }
  55. template <class Type>
  56. Noeud<Type> *Noeud<Type>::get_fg()
  57. {
  58.                      return fils_gauche;                       
  59. }
  61. template <class Type>
  62. Noeud<Type> *Noeud<Type>::get_fd()
  63. {
  64.                      return fils_droit;
  65. }
  67. //Methode recursive pour effacer un noeud
  68. template <class Type>
  69. void Noeud<Type>::effacer(Noeud<Type> *n)
  70. {
  71.      if(n->fils_gauche)
  72.          effacer(n->fils_gauche);
  73.      if(n->fils_droit)
  74.          effacer(n->fils_droit);
  75.      delete(n);
  76. }
  78. //Surcharge de <
  79. template <class Type>
  80. bool Noeud<Type>::operator<(Noeud<Type> b){
  81.   return element < b.get_element();
  82. }
  84. //Cloner un noeud
  85. template <class Type>
  86. Noeud<Type> *Noeud<Type>::clone(Noeud<Type> *n)
  87. {
  88.             Noeud<Type> *res = new Noeud<Type>(n->get_element());
  89.             if(n->fils_gauche)
  90.                res->fils_gauche = clone(n->fils_gauche);
  91.             if(n->fils_droit)
  92.                res->fils_droit = clone(n->fils_droit);
  93.            
  94.             return res;
  95. }
  97. //Cloner this
  98. template <class Type>
  99. Noeud<Type> *Noeud<Type>::clone()
  100. {
  101.             Noeud<Type> *res = this;
  102.             if(this->fils_gauche)
  103.                res->fils_gauche = clone(this->fils_gauche);
  104.             if(this->fils_droit)
  105.                res->fils_droit = clone(this->fils_droit);
  106.            
  107.             return res;
  108. }


 
La classe ABR :

Code :
  1. //Fichier ABR.h
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <vector>
  5. #include "Noeud.h"
  7. using namespace std;
  9. //Declaration de la classe ABR
  10. template <class Type> class ABR;
  12. //Declaration de la fonction de surcharge de <<
  13. template <class Type>
  14. ostream &operator<<(ostream &o, const ABR<Type> &a);
  16. //Declaration de la classe ABR
  17. template <class Type>
  18. class ABR
  19. {
  20.    //Et oui je sais que c'est laid mais c'est comme ca !!   
  21.    friend ostream &operator<< <>(ostream &o, const ABR<Type> &a);
  22.  
  23.    Noeud<Type> *racine;     
  24.  
  25.    public:
  26.       ABR();     
  27.       ABR(Type el);
  28.       ABR(Noeud<Type> *n);
  29.       //Destructeur
  30.       ~ABR();
  31.       //Accesseur
  32.       Noeud<Type> *get_racine();
  33.       //Consultation
  34.       bool consulter(Type el);
  35.       //Insertion d'un element
  36.       bool inserer(Type el);
  37.       //Insertion d'un sous arbre
  38.       void inserer_arbre(const ABR<Type> &a);     
  39.       //Effacer
  40.       bool effacer(Type el); 
  41.       //Effacement de this
  42.       void effacer();       
  43.       //Affichage
  44.       void dump(ostream &o);
  45.       //Remplissage d'un vector
  46.       void rempl(Noeud<Type> *n, vector<Type> &v);
  47.       //Affichage normal
  48.       void affiche(Noeud<Type> *n, ostream &o);
  49.       //Affichage trie
  50.       void trie_affiche(ostream &o);     
  51.       //Cloner l'arbre passé en param  
  52.       ABR<Type> clone(const ABR<Type> &a);
  53.       //Cloner l'arbre courant
  54.       ABR<Type> clone();
  55. };
  57. //Constructeur sans params
  58. template <class Type>
  59. ABR<Type>::ABR()
  60. {
  61.           racine = NULL;
  62. };
  64. //Constructeur avec el
  65. template <class Type>
  66. ABR<Type>::ABR(Type el)
  67. {
  68.     racine = new Noeud<Type>(el);
  69. };
  71. //Constructeur avec un ptr sur noeud
  72. template <class Type>
  73. ABR<Type>::ABR(Noeud<Type> *n)
  74. {
  75.     racine = n;
  76. };
  78. //Destructeur
  79. template <class Type>
  80. ABR<Type>::~ABR()
  81. {
  82.   racine->effacer(racine);
  83. };
  85. //Accesseur pour la racine
  86. template <class Type>
  87. Noeud<Type> *ABR<Type>::get_racine()
  88. {
  89.    return racine;
  90. };
  92. //Consultation
  93. //Renvoi un booleen si l'element est present
  94. template <class Type>
  95. bool ABR<Type>::consulter(Type el)
  96. {
  97.      Noeud<Type> *actuel = racine;
  98.      while(actuel)
  99.      {
  100.        if(actuel->get_element() == el)
  101.            return true;
  102.        else
  103.            if(actuel->get_element() < el)
  104.              actuel = actuel->fils_gauche;
  105.            else
  106.              actuel = actuel->fils_droit;                                   
  107.      }
  108.      return false;
  109. };                                   
  111. //Insertion
  112. template <class Type>
  113. bool ABR<Type>::inserer(Type el)
  114. {
  115.   Noeud<Type> **actuel = &racine;
  117.   while(*actuel){
  118.     //Si on est dessus on fait rien
  119.     if((*actuel)->get_element() == el){
  120.       return 0;
  121.     }else{
  122.       //Si notre el est inf a element de la racine
  123.       //on va a gauche
  124.       if(el < (*actuel)->get_element()){
  125.        actuel = &((*actuel)->fils_gauche);
  126.       }else{
  127.        actuel = &((*actuel)->fils_droit);
  128.       }
  129.     }
  130.   }
  131.   //On crée un nouveau noeud
  132.   *actuel = new Noeud<Type>(el);
  133.   return 1;
  134. };
  136. //Insertion d'un sous-arbre  
  137. template <class Type>
  138. void ABR<Type>::inserer_arbre(const ABR<Type> &a)
  139. {
  140.   //Variable d'adresse pour parcourir l'arbre courant     
  141.   Noeud<Type> **actuel = &(racine); 
  142.   //Element de la racine de l'arbre a inserer
  143.   Type el = (a.racine)->get_element();
  145.   while(*actuel){
  146.     //Si on est dessus on insere (bourrinage)
  147.     if((*actuel)->get_element() == el){
  148.       *actuel = (a.racine)->clone();
  149.     }else{
  150.       //Si notre el est inf a element de la racine
  151.       //on va a gauche
  152.       if(el < (*actuel)->get_element()){
  153.        actuel = &((*actuel)->fils_gauche);
  154.       }else{
  155.        actuel = &((*actuel)->fils_droit);
  156.       }
  157.     }
  158.   }
  159.   //Insertion du sous arbre
  160.   *actuel = (a.racine)->clone();
  161. };
  163. //Methode pour effacer un element (ne racorde pas les noeuds fils)
  164. template <class Type>
  165. bool ABR<Type>::effacer(Type el)
  166. {
  167.   Noeud<Type> **actuel = &racine;
  169.   while(*actuel){
  170.     //Si on est dessus on fait rien
  171.     if((*actuel)->get_element() == el){
  172.         //On efface le noeud
  173.         delete(*actuel);
  174.         return true;
  175.     }else{
  176.       //Si notre el est inf a element de la racine
  177.       //on va a gauche
  178.       if(el < (*actuel)->get_element()){
  179.        actuel = &((*actuel)->fils_gauche);
  180.       }else{
  181.        actuel = &((*actuel)->fils_droit);
  182.       }
  183.     }
  184.   }
  185.   return false;
  186. }
  188. //Methode pour l'affichage triée, sera heritee
  189. template <class Type>
  190. void ABR<Type>::rempl(Noeud<Type> *n, vector<Type> &v)
  191. {
  192.        if(n != NULL){         
  193.             v.push_back(n->get_element());         
  194.           if(n->fils_gauche != NULL)
  195.              rempl(n->fils_gauche, v);
  196.            
  197.           if(n->fils_droit != NULL)
  198.              rempl(n->fils_droit, v);
  199.      }                   
  200. };
  202. //Affichage normal
  203. template <class Type>
  204. void ABR<Type>::affiche(Noeud<Type> *n, ostream &o)
  205. {
  206.   o << "[" <<  n->get_element() << " : " ;
  207.   o << ((n->fils_gauche != NULL) ? (n->fils_gauche)->get_element() : (Type)NULL)  << ", ";
  208.   o << ((n->fils_droit != NULL) ? (n->fils_droit)->get_element() : (Type)NULL)  << "]" << endl;
  209.   if(n->fils_gauche != NULL){   
  210.     affiche(n->get_fg(), o);
  211.   }
  212.   if(n->fils_droit != NULL){   
  213.     affiche(n->get_fd(), o);
  214.   }
  215. };
  217. //Methode pour trier et afficher l'arbre
  218. template <class Type>
  219. void ABR<Type>::trie_affiche(ostream &o)
  220. {
  221.     //Declaration
  222.     vector<Type> vec;   
  223.     //Remplissage
  224.     rempl(racine, vec); 
  225.     //Tri du vector
  226.     sort(vec.begin(), vec.end());           
  227.     o << "\n" << endl;       
  228.     for(int i = 0; i<vec.size(); i++){
  229.              o << vec[i] <<  " ";
  230.     }
  231.     o << endl;
  232. };
  234. //Methode pour l'affichage (sera heritee)
  235. template <class Type>
  236. void ABR<Type>::dump(ostream &o)
  237. {
  238.      //Affichage normal
  239.      affiche(racine, o);
  240.      //Affichage triée
  241.      trie_affiche(o);   
  242. };
  244. //Methode pour cloner un arbre
  245. template <class Type>
  246. ABR<Type> ABR<Type>::clone(const ABR<Type> &a)
  247. {
  248.     //Creation d'un noeud bidon
  249.     Noeud<Type> bidon(0);   
  250.     //Creation de l'arbre a renvoyer
  251.     ABR<Type> res(bidon.clone(a.racine));
  252.     return res;       
  253. }
  255. //Methode pour cloner this
  256. template <class Type>
  257. ABR<Type> ABR<Type>::clone()
  258. {
  259.     //Creation d'un noeud bidon
  260.     Noeud<Type> bidon(0);       
  261.     //Creation de l'arbre a renvoyer
  262.     ABR<Type> res(bidon.clone(this->racine));
  263.     return res;       
  264. }
  266. //Surcharge de <<         
  267. template <class Type>
  268. ostream &operator<<(ostream &o, const ABR<Type> &a)
  269. {       
  270.     o << "AFFICHAGE DE l'ARBRE : " << endl;   
  271.     //Creation d'un noeud bidon
  272.     Noeud<Type> bidon(0);   
  273.     //Creation d'un arbre temporaire
  274.     ABR<Type> temp(bidon.clone(a.racine));   
  275.     temp.dump(o);   
  276.     return o; 
  277. };


 
Le petit main :

Code :
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include "ABR.h"
  5. using namespace std;
  7. int main(int argc, char *argv[])
  8. { 
  9.     // TEST DE LA CLASSE ABR
  10.     ABR<int> arbre_int(3);
  11.     cout << "arbre_int.inserer(4) : " << arbre_int.inserer(4) << endl;
  12.     cout << "arbre_int.inserer(5) : " << arbre_int.inserer(5) << endl;
  13.     cout << "arbre_int.inserer(1) : " << arbre_int.inserer(1) << endl;
  14.     cout << "arbre_int.inserer(2) : " << arbre_int.inserer(2) << endl;
  15.     cout << arbre_int << endl;
  16.    
  17.     ABR<float> arbre_float(9);
  18.     cout << "arbre_float.inserer(4) : " << arbre_float.inserer(4) << endl;
  19.     cout << "arbre_float.inserer(5) : " << arbre_float.inserer(5) << endl;
  20.     cout << "arbre_float.inserer(1) : " << arbre_float.inserer(1) << endl;
  21.     cout << "arbre_float.inserer(2) : " << arbre_float.inserer(2) << endl;
  22.     cout << arbre_float << endl;
  23.    
  24.     //Test du clonage
  25.     ABR<float> t = arbre_float.clone();
  26.     cout << t << endl;   
  27.    
  28.     //Test de l'insertion d'un sous-arbre
  29.     cout << "\nTEST DE L'INSERTION D'UN SOUS ARBRE :\n" << endl;
  30.     ABR<short> a;
  31.     cout << "a.inserer(4) : " << a.inserer(4) << endl;
  32.     cout << "a.inserer(5) : " << a.inserer(5) << endl;
  33.     cout << "a.inserer(9) : " << a.inserer(9) << endl;
  34.    
  35.     ABR<short> b;
  36.     cout << "b.inserer(1) : " << b.inserer(1) << endl;
  37.     cout << "b.inserer(6) : " << b.inserer(6) << endl;
  38.     cout << "b.inserer(8) : " << b.inserer(8) << endl;   
  39.        
  40.     cout << "a.inserer_arbre(b) : " << endl;
  41.     a.inserer_arbre(b);
  42.    
  43.     cout << a << endl;
  44.    
  45.     system("PAUSE" );
  46.     return EXIT_SUCCESS;
  47. }


 
Ca compile et s'execute sans probs du moins avec ces quelques ptits tests dans le main.


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 16-10-2005 à 01:24:08   

Reply

Marsh Posté le 16-10-2005 à 11:50:06    

A vue de nez, je pense que tes methodes "effacer" font le travail du destructeur. Moi, je virerais les methodes "effacer" et mettrais leur contenu dans le(s) destructeur(s) (la ou tu n'etais pas sur qu'il faille rien mettre). Mais p-e que je me trompe et que ce n'est pas possible partout, a voir.
 
Dans le meme ordre d'idees, Noeud<Type>::Noeud(Type el,...) devrait a mon avis etre plutot Noeud<Type>::Noeud(Type *el=NULL, ...).
 
Taz te dirait sans doute que tu reinventes la roue, - mais l'exercice est interessant -, et aussi (avec raison) que les accesseurs n'ont pas besoin de s'appeler get et set, mais que get_element peut s'appeler plus simplement element() et set_element(Type el) plus simplement element(Type el).
 
 
Il y ad'autres trucs bizarres comme cette fonction censée retourner un bool et dans laquelle on lit "return 0;" et "return 1;".
 
Enfin, pour tester ce type d'algo assez delicat, un coup de Valgrind ou de Boundschecker n'est pas superflu.


Message édité par el muchacho le 17-10-2005 à 21:25:59

---------------
Les aéroports où il fait bon attendre, voila un topic qu'il est bien
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed