[code] Implantation des arbres binaires de recherche du lundi 7/04 2008

, par Pierre

  1. # include <stdlib.h>
  2. # include <stdio.h>
  3. # include <assert.h>
  4.  
  5. /* Les éléments : type et comparaison */
  6. typedef int element_t;
  7.  
  8. int comparer(element_t a, element_t b){
  9. if (a < b) return 1;
  10. if (a > b) return -1;
  11. return 0;
  12. }
  13.  
  14. void affiche_element(element_t e) {
  15. printf("%2d ", e);
  16. }
  17.  
  18. /* Les ABR : type */
  19. typedef struct abr_s {
  20. struct abr_s *parent;
  21. struct abr_s *droite;
  22. struct abr_s *gauche;
  23. element_t e;
  24. } *abr_t;
  25.  
  26. /* Parcours dans l'ordre pour affichage */
  27. void parcours_infixe(abr_t x) {
  28. if (x) {
  29. parcours_infixe(x->gauche);
  30. affiche_element(x->e);
  31. parcours_infixe(x->droite);
  32. }
  33. }
  34.  
  35. /* minimum(x) renvoie le noeud contenant le minimum de l'arbre, ou
  36.   NULL si l'arbre est vide */
  37. abr_t minimum(abr_t x) {
  38. if (x) {
  39. while (x->gauche) {
  40. x = x->gauche;
  41. }
  42. }
  43. return x;
  44. }
  45.  
  46. abr_t maximum(abr_t x) {
  47. if (x) {
  48. while (x->droite) {
  49. x = x->droite;
  50. }
  51. }
  52. return x;
  53. }
  54.  
  55. /* Recherche d'un élément, renvoie le noeud contenant l'élément ou
  56.   bien NULL si absent */
  57. abr_t rechercher(abr_t x, element_t a) {
  58. if (x) {
  59. switch (comparer(a, x->e)) {
  60. case 1:
  61. return rechercher(x->gauche, a);
  62. break;
  63. case -1:
  64. return rechercher(x->droite, a);
  65. break;
  66. case 0:
  67. return x;
  68. }
  69. }
  70. return NULL; /* élément introuvable */
  71. }
  72.  
  73. /* successeur(y): renvoie le successeur de y dans l'arbre ou NULL s'il
  74.   n'existe pas */
  75. abr_t successeur(abr_t y){
  76. assert(y);
  77. if (y->droite) {
  78. return minimum(y->droite);
  79. }
  80. else {
  81. while ( y-> parent && (y == (y->parent)->droite) ) {
  82. y = y->parent;
  83. }
  84. return y->parent;
  85. }
  86. }
  87.  
  88. abr_t predecesseur(abr_t y){
  89. assert(y);
  90. if (y->gauche) {
  91. return maximum(y->gauche);
  92. }
  93. else {
  94. while ( y-> parent && (y == (y->parent)->gauche) ) {
  95. y = y->parent;
  96. }
  97. return y->parent;
  98. }
  99. }
  100.  
  101. /* nouveau_noeud(a), crée (allocation mémoire) et renvoie un arbre à
  102.   un seul noeud contenant l'élément a. */
  103. abr_t nouveau_noeud(element_t a) {
  104. abr_t x;
  105. x = malloc(sizeof(abr_t));
  106. if (!x) perror("malloc");
  107. x->parent = NULL;
  108. x->gauche = NULL;
  109. x->droite = NULL;
  110. x->e = a;
  111. return x;
  112. }
  113.  
  114. void effacer_noeud(abr_t x) {
  115. free(x);
  116. }
  117.  
  118. /* inserer(&x, a) insere un élément a dans un arbre binaire de
  119.   recherche x. S'il existe déjà un élément b égal à a dans l'arbre
  120.   aucun noeud n'est créé (pas de répétition). La fonction inserer()
  121.   ne renvoie rien, l'arbre x est passé par adresse (px = adresse de
  122.   l'arbre) pour être directement modifié (argument-résultat). */
  123.  
  124. void inserer(abr_t *px, element_t e) {
  125. abr_t x, parent;
  126. int cote;
  127. if ( !(*px) ) {
  128. *px = nouveau_noeud(e);
  129. return;
  130. }
  131. x = *px;
  132. /* Recherche de la place de a (parent et côté où le mettre) */
  133. while ( x ) {
  134. parent = x;
  135. switch ( cote = comparer(e, x->e) ) {
  136. case 1:
  137. x = x->gauche;
  138. break;
  139. case -1:
  140. x = x->droite;
  141. break;
  142. case 0:
  143. return; /* pas de répétition dans l'arbre */
  144. }
  145. }
  146. /* parent sera le parent du nouveau noeud, la valeur de cote dit de
  147.   quel côté l'attacher à son parent. */
  148. x = nouveau_noeud(e);
  149. x->parent = parent;
  150. if (cote == 1) {
  151. parent->gauche = x;
  152. }
  153. else {
  154. parent->droite = x;
  155. }
  156. }
  157.  
  158. /* supprimer(px, y) supprime l'élément contenu dans le noeud d'adresse
  159.   y de l'arbre d'adresse px (argument-résultat).
  160.  
  161.   Remarque : pour supprimer un élément a il faut d'abord chercher
  162.   dans l'arbre l'adresse du noeud qui le contient.
  163.   Exemple:
  164.   supprimer(&x, rechercher(x, a));
  165.   Ou bien:
  166.   if (y = rechercher(x, a)) supprimer(&x, y);
  167. */
  168.  
  169. void supprimer(abr_t *px, abr_t y) {
  170. assert(y);
  171. if (y->gauche && y->droite) {
  172. abr_t z;
  173. z = successeur(y); /* en fait z = minimum(y->droite) */
  174. y->e = z->e;
  175. supprimer(px, z);
  176. }
  177. else {
  178. abr_t fils;
  179. if ( y->gauche ) {
  180. fils = y->gauche;
  181. } else {
  182. fils = y->droite;
  183. }
  184. /* Si il y avait un parent alors fils remplace y auprès de ce parent */
  185.  
  186. if ( y->parent ) {
  187. if ( y == (y->parent)->gauche ) {
  188. (y->parent)->gauche = fils;
  189. } else {
  190. (y->parent)->droite = fils;
  191. }
  192. } else {
  193. *px = fils;
  194. }
  195. /* le parent de y devient le nouveau parent du fils */
  196.  
  197. if (fils) {
  198. fils->parent = y->parent;
  199. }
  200. effacer_noeud(y);
  201. }
  202. }
  203.  
  204. /* Rotations :
  205.  
  206.  x -> b ---rot. droite de centre x--> a <- x
  207.   / \ / \
  208.   a C <--rot. gauche de centre x--- A b
  209.   / \ / \
  210.   A B B C
  211.  
  212. */
  213.  
  214. void rotation_droite(abr_t x) {
  215. abr_t y, A, B, C;
  216. element_t e;
  217. assert(x && x->gauche);
  218. y = x->gauche;
  219. A = y->gauche;
  220. B = y->droite;
  221. C = x->droite;
  222. /* échange des deux éléments */
  223. e = x->e;
  224. x->e = y->e;
  225. y->e = e;
  226.  
  227. /* remise en place des sous-arbres */
  228. x->droite = y;
  229. x->gauche = A;
  230. A->parent = x;
  231. y->gauche = B;
  232. y->droite = C;
  233. C->parent = y;
  234. }
  235.  
  236. /* Affichage "simple" en mode texte, exemple :
  237.  
  238. L'arbre 4
  239.   / \
  240.   1 7
  241.   / \ \
  242.   0 3 9
  243.   /
  244.   8
  245.  
  246. s'affichera comme ceci :
  247.  
  248.  
  249.  4 ----- 7 ----- 9
  250.  | |
  251.  | 8
  252.  |
  253.  1 ----- 3
  254.  |
  255.  0
  256.  
  257. */
  258.  
  259. /* fonction auxilliaire pour l'affichage d'une ligne de traits
  260.   verticaux représentant la descendance à gauche. */
  261. void afficher_arbre_aux1(abr_t x){
  262. if (x->parent) {
  263. afficher_arbre_aux1(x->parent);
  264. if (x == (x->parent)->droite) {
  265. if ((x->parent)->gauche) {
  266. printf(" | "); /* 8 caractères */
  267. }
  268. else {
  269. printf(" "); /* 8 caractères */
  270. }
  271. }
  272. }
  273. }
  274.  
  275. /* afficher_arbre(x) réalise l'affichage de x sur la sortie standard
  276.   comme décrit plus haut. */
  277. void afficher_arbre(abr_t x){
  278. if (x) { /* Si l'arbre n'est pas vide, on réalise l'affichage par
  279. appels récursifs sur les sous-arbres non vides. */
  280. affiche_element(x->e);
  281. if (x->droite) { /* noeuds de droite sur la même ligne */
  282. printf("-----");
  283. afficher_arbre(x->droite);
  284. }
  285. else { /* plus rien à droite : fin de ligne */
  286. printf("\n");
  287. }
  288. if (x->gauche) {
  289. afficher_arbre_aux1(x->gauche);
  290. printf(" | \n"); /* 8 caractères */
  291. afficher_arbre_aux1(x->gauche);
  292. afficher_arbre(x->gauche);
  293. }
  294. }
  295. else { /* Si l'arbre est vide on le signale */
  296. printf("\n (arbre vide)\n\n");
  297. }
  298. }
  299.  
  300. int main() {
  301. abr_t x = NULL;
  302. element_t i;
  303. element_t tab[] = {5, 2, 4, 3, 7, 6, 1, 9, 8, 0};
  304.  
  305. for (i = 0; i < 10; i++) {
  306. inserer(&x, tab[i]);
  307. }
  308. parcours_infixe(x);
  309. printf("fin du parcours \n");
  310. printf("\nAffichage ***************************\n");
  311. afficher_arbre(x);
  312.  
  313. supprimer(&x, rechercher(x, 6));
  314. printf("\nAffichage (supprimer 6)**************\n");
  315. afficher_arbre(x);
  316.  
  317. supprimer(&x, rechercher(x, 5));
  318. printf("\nAffichage (supprimer 5)**************\n");
  319. afficher_arbre(x);
  320.  
  321. rotation_droite(rechercher(x, 2));
  322. printf("\nAffichage (rotation_droite 2)********\n");
  323. afficher_arbre(x);
  324.  
  325. supprimer(&x, rechercher(x, 2));
  326. printf("\nAffichage (supprimer 2)**************\n");
  327. afficher_arbre(x);
  328.  
  329. supprimer(&x, rechercher(x, 7));
  330. printf("\nAffichage (supprimer 7)**************\n");
  331. afficher_arbre(x);
  332.  
  333. return EXIT_SUCCESS;
  334. }

Télécharger

Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]