Guest User

kdo de noel

a guest
Dec 9th, 2019
89
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