Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2744 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  Arbre Binaire de Recherche générique

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Arbre Binaire de Recherche générique

n°1223887
Chronoklaz​m
Posté le 16-10-2005 à 01:24:08  profilanswer
 

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


 
La classe ABR :

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


 
Le petit main :

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


 
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 !
mood
Publicité
Posté le 16-10-2005 à 01:24:08  profilanswer
 

n°1223931
el muchach​o
Comfortably Numb
Posté le 16-10-2005 à 11:50:06  profilanswer
 

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

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  Arbre Binaire de Recherche générique

 

Sujets relatifs
Déclaration d'amitié pour fonction générique.construire un arbre n-aire
Recherche récursiveMethode toString() générique, introspection.
Recherche de méthode de lecture de source HTMLMoteur de recherche ou robot
manupiler un fichier binairerecherche de script
Représentation négatif d'un nombre binaire.Recherche LOGICIEL....AIDEZ MOI SVP
Plus de sujets relatifs à : Arbre Binaire de Recherche générique


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR