SHARE
TWEET

kdo de noel

a guest Dec 9th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /************************************************************************/
  2. /* Auteur : S. Gueye                            */
  3. /* TP : Arbres Binaires de Recherche                    */
  4. /* Date dernière maj : 25/11/2019                  */
  5. /************************************************************************/
  6.  
  7. #include <iostream>
  8. #include <fstream>
  9. #include <algorithm>
  10. #include "ABR.h"
  11.  
  12. using namespace std;
  13.  
  14. /****************************************/
  15. /* Objectif : Constructeur d'un noeud dont les fils sont NULL
  16. /* Entrées : entier x
  17. /* Complexité : 0(1)
  18. /****************************************/
  19. noeud::noeud(int x)
  20. {
  21.     cle = x;
  22.     fg = fd = pere =  NULL;
  23.     h = d = 0;
  24. }
  25.  
  26.  
  27. /****************************************/
  28. /* Objectif : Destructeur d'un noeud
  29. /****************************************/
  30. noeud::~noeud()
  31. {
  32.     if(fg)
  33.         delete(fg);
  34.     if(fd)
  35.         delete(fd);
  36. }
  37.  
  38. /****************************************/
  39. /* Objectif : Constructeur d'un ABR
  40. /****************************************/
  41. ABR::ABR()
  42. {
  43.     r = NULL;
  44. }
  45.  
  46.  
  47. /****************************************/
  48. /* Objectif : Constructeur d'un ABR
  49. /****************************************/
  50. ABR::ABR(char* filename)
  51. {
  52.     r = NULL;
  53.     ifstream file(filename);
  54.     int n,tmp,cpt = 0;
  55.  
  56.     file >> n;
  57.     for(int i = 0; i < n ; i++){
  58.         file >> tmp;   
  59.         if(insertion(tmp)){
  60.             cpt++;
  61.         }
  62.     }
  63.  
  64.     cout << "Nombre d'éléments insérés = " << cpt << endl; 
  65.     cout << "Hauteur de l'arbre = " << hauteur() << endl;
  66.     cout << "Affichage infixe = ";
  67.     infixe(r);
  68.     cout << endl;
  69.     file.close();
  70. }
  71.  
  72.  
  73.  
  74. /****************************************/
  75. /* Objectif : Destructeur d'un AB
  76. /****************************************/
  77. ABR::~ABR()
  78. {
  79.     if(r)
  80.         delete(r);
  81. }
  82.  
  83. /****************************************/
  84. /* Objectif : Accesseur à la racine r
  85. /****************************************/
  86. noeud* ABR::root()
  87. {
  88.     return(r);
  89. }
  90.  
  91. /****************************************/
  92. /* Objectif : Parcours infixe
  93. /****************************************/
  94. void ABR::infixe(noeud* x)
  95. {
  96.     if(x){
  97.         infixe(x->fg);
  98.         cout << " " << x->cle;
  99.         infixe(x->fd);
  100.     }
  101. }
  102.  
  103. /****************************************/
  104. /* Objectif : Renvoie la hauteur de l'arbre de
  105. racine r
  106. /****************************************/
  107. int ABR::hauteur()
  108. {
  109.     return(r->h);
  110. }
  111.  
  112. /****************************************/
  113. /* Objectif : Insertion de "cle" dans l'arbre
  114. /* Une cle étant un identifiant. Il faudra vérifier que celle
  115. que l'on veut insérer n'existe pas déjà dans l'arbre.
  116. Si oui il ne faudra pas l'insérer.
  117.  
  118. - La méthode doit renvoyer "vrai" si l'insertion a pu être faite
  119. et "faux" sinon.
  120. - Si l'insertion a été faite le message suivant est affiché :
  121.         cout << "Insertion de : " << cle << " " << endl;
  122. /****************************************/
  123. bool ABR::insertion(int cle)
  124. {
  125.     noeud * y;
  126.     noeud* x = r;
  127.     noeud* pere = NULL;
  128.     bool existe = false;
  129.  
  130.     while(x != NULL){
  131.  
  132.         pere = x;
  133.         if(cle < x->cle)
  134.             x = x->fg;
  135.         else
  136.         if(cle > x->cle)
  137.             x = x->fd;
  138.         else{
  139.             existe = true;
  140.             x = NULL;
  141.         }          
  142.     }
  143.  
  144.     if(! existe){
  145.         cout << "Insertion de : " << cle << " " << endl;
  146.         y = new noeud(cle);
  147.  
  148.         if(pere == NULL)
  149.             r  = y;
  150.         else{
  151.             y->pere = pere;
  152.             if(cle < pere->cle){
  153.                 pere->fg = y;
  154.             }
  155.                
  156.             else{
  157.                 pere->fd = y;
  158.             }
  159.         }
  160.        
  161.         // Réquilibrage de l'arbre à partir du père du nouveau noeud inséré.
  162.         if(y->pere != NULL){
  163.             requilibre(y->pere);
  164.         }
  165.            
  166.     }  
  167.  
  168.     return(!existe);
  169. }
  170.  
  171.  
  172. /****************************************/
  173. /* Objectif :
  174. /* Rotation droite à partir de x
  175. /* x et x->fg sont supposés non nuls.
  176. /****************************************/
  177. void ABR::rotationDroite(noeud* x)
  178. {
  179.     // Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
  180.     // l'exécution
  181.     cout << "rotationDroite................" << endl;
  182.     noeud *G = x->fg;
  183.     x->fg = G->fd;
  184.     G->fd = x;
  185.    
  186.     if(x->fg!=NULL){
  187.         x->fg->pere = x;
  188.     }
  189.     if(x->pere!=NULL){
  190.         if(x==x->pere->fg){
  191.             x->pere->fg = G;
  192.         }
  193.         else{
  194.             x->pere->fd = G;
  195.         }
  196.     }
  197.     G->pere = x->pere;
  198.     x->pere = G;
  199.    
  200.     // calcul de h et d pour x
  201.     if(x->fd && x->fg){
  202.         x->h = max(x->fg->h,x->fd->h)+1;
  203.         x->d = (x->fg->h) - (x->fd->h);
  204.     }
  205.     else if((x->fg==NULL)&&(x->fd==NULL)){
  206.         x->h = 0;
  207.         x->d = 0;
  208.     }
  209.     else if(x->fg==NULL){
  210.         x->h = (x->fd->h)+1;
  211.         x->d = -1 - (x->fd->h);
  212.     }
  213.     else{
  214.         x->h = (x->fg->h)+1;
  215.         x->d = (x->fg->h)+1;
  216.     }
  217.    
  218.     //calcul h et d pour G
  219.     if(G->fd && G->fg){
  220.         G->h = max(G->fg->h,G->fd->h)+1;
  221.         G->d = (G->fg->h) - (G->fd->h);
  222.     }
  223.     else if((G->fg==NULL)&&(G->fd==NULL)){
  224.         G->h = 0;
  225.         G->d = 0;
  226.     }
  227.     else if(G->fg==NULL){
  228.         G->h = (G->fd->h)+1;
  229.         G->d = -1 - (G->fd->h);
  230.     }
  231.     else{
  232.         G->h = (G->fg->h)+1;
  233.         G->d = (G->fg->h)+1;
  234.     }
  235.     x = G;
  236.     if(x->pere==NULL){
  237.         r = x;
  238.     }
  239. }
  240.  
  241. /****************************************/
  242. /* Objectif : Rotation gauche à partir de x
  243. /* x et x->fd sont supposés non nuls.
  244. /****************************************/
  245. void ABR::rotationGauche(noeud* x)
  246. {
  247.     // Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
  248.     // l'exécution
  249.     cout << "rotationGauche................" << endl;
  250.     noeud *L = x->fd;
  251.     x->fd = L->fg;
  252.     L->fg = x;
  253.     if(x->fd!=NULL){
  254.         x->fd->pere = x;
  255.     }
  256.     if(x->pere!=NULL){
  257.         if(x==x->pere->fg){
  258.             x->pere->fg = L;
  259.         }
  260.         else{
  261.             x->pere->fd = L;
  262.         }
  263.     }
  264.     L->pere = x->pere;
  265.     x->pere = L;
  266.     //calcul h et d pour x
  267.     if(x->fd && x->fg){
  268.         x->h = max(x->fg->h,x->fd->h)+1;
  269.         x->d = (x->fg->h) - (x->fd->h);
  270.     }
  271.     else if((x->fg==NULL)&&(x->fd==NULL)){
  272.         x->h = 0;
  273.         x->d = 0;
  274.     }
  275.     else if(x->fg==NULL){
  276.         x->h = (x->fd->h)+1;
  277.         x->d = -1 - (x->fd->h);
  278.     }
  279.     else{
  280.         x->h = (x->fg->h)+1;
  281.         x->d = (x->fg->h)+1;
  282.     }
  283.    
  284.     //calcul h et d pour L
  285.     if(L->fd && L->fg){
  286.         L->h = max(L->fg->h,L->fd->h)+1;
  287.         L->d = (L->fg->h) - (L->fd->h);
  288.     }
  289.     else if((L->fg==NULL)&&(L->fd==NULL)){
  290.         L->h = 0;
  291.         L->d = 0;
  292.     }
  293.     else if(L->fg==NULL){
  294.         L->h = (L->fd->h)+1;
  295.         L->d = -1 - (L->fd->h);
  296.     }
  297.     else{
  298.         L->h = (L->fg->h)+1;
  299.         L->d = (L->fg->h)+1;
  300.     }
  301.     x = L;
  302.     if(x->pere==NULL){
  303.         r = x;
  304.     }
  305. }
  306.  
  307. /****************************************/
  308. /* Objectif : Rotation droite-gauche à partir de x
  309. /* x et x->fd sont supposés non nuls.
  310. /****************************************/
  311. void ABR::rotationDroiteGauche(noeud* x)
  312. {
  313.     // Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
  314.     // l'exécution
  315.     cout << "rotationDroiteGauche.........." << endl;
  316.     rotationDroite(x->fd);
  317.     rotationGauche(x);
  318.    
  319.     // !!! A COMPLETER !!! //
  320. }
  321.  
  322. /****************************************/
  323. /* Objectif : Rotation gauche-droite à partir de x
  324. /* x et x->fg sont supposés non nuls.
  325. /****************************************/
  326. void ABR::rotationGaucheDroite(noeud* x)
  327. {
  328.     // Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
  329.     // l'exécution
  330.     cout << "rotationGaucheDroite.........." << endl;
  331.     rotationGauche(x->fg);
  332.     rotationDroite(x);
  333.  
  334.     // !!! A COMPLETER !!! //
  335. }
  336.  
  337. /****************************************/
  338. /* Objectif : Requilibre (si nécessaire) l'arbre en partant
  339. de x et en remontant les pères. x est supposé non nul.
  340. /****************************************/
  341. void ABR::requilibre(noeud* x)
  342. {
  343.     //initialise la hauteur
  344.     int vraiHauteur = x->h;
  345.    
  346.     //Calcul de h et d
  347.     if(x->fd && x->fg){
  348.         x->h = max(x->fg->h,x->fd->h)+1;
  349.         x->d = (x->fg->h) - (x->fd->h);
  350.     }
  351.     else if((x->fg==NULL)&&(x->fd==NULL)){
  352.         x->h = 0;
  353.         x->d = 0;
  354.     }
  355.     else if(x->fg==NULL){
  356.         x->h = (x->fd->h)+1;
  357.         x->d = -1 - (x->fd->h);
  358.     }
  359.     else{
  360.         x->h = (x->fg->h)+1;
  361.         x->d = (x->fg->h)+1;
  362.     }
  363.    
  364.     // Test pour rotation
  365.     if(x->d!=0){
  366.         if((x->d == 2)&&(x->fg->d==1)){
  367.             rotationDroite(x);
  368.         }
  369.         else if((x->d==-2)&&(x->fd->d==-1)){
  370.             rotationGauche(x);
  371.         }
  372.         else if((x->d==2)&&(x->fg->d==-1)){
  373.             rotationGaucheDroite(x);
  374.         }
  375.         else if((x->d==-2)&&(x->fd->d==1)){
  376.             rotationDroiteGauche(x);
  377.         }
  378.     }
  379.     if((vraiHauteur != x->h)&&(x->pere)){
  380.         requilibre(x->pere);
  381.     }
  382.    
  383. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top