Semaine 3 – Arbres binaires de recherche

photo : CC-By-Nc-Sa Stefan Geens

, par Pierre

Implémentation des arbres binaires de recherche.

  1. (* Un type des arbres binaires d'entiers *)
  2. type arbreBin =
  3. | Feuille
  4. | Noeud of arbreBin * int * arbreBin;;
  5.  
  6. exception ArbreVide;;
  7.  
  8. (* DONE faire un autre exemple d'arbre *)
  9. let abr1 = Noeud (Noeud (Feuille, 10, Feuille),
  10. 20,
  11. Noeud (Noeud (Feuille,
  12. 30,
  13. Noeud (Feuille, 40, Feuille)),
  14. 50,
  15. Feuille));;
  16.  
  17. (* parcours infixe retourne une liste standard *)
  18. let rec parcoursInfixeAB = function
  19. | Feuille->[]
  20. | Noeud (gauche,x,droit) ->
  21. parcoursInfixeAB(gauche)@
  22. x::parcoursInfixeAB(droit);;
  23.  
  24. parcoursInfixeAB abr1;;
  25.  
  26. (* un affichage structuré des AB *)
  27. let rec afficherABligne = function
  28. | Feuille -> print_string "."
  29. | Noeud (gauche, x, droite) ->
  30. afficherABligne gauche;
  31. afficherABligne droite;
  32. ;;
  33.  
  34. (* DONE le plus grand entier d'un arbre binaire quelconque *)
  35. let rec maxAB = function
  36. | Feuille -> raise ArbreVide
  37. | Noeud (Feuille, x, Feuille) -> x
  38. | Noeud (Feuille, x, d) -> max x (maxAB d)
  39. | Noeud (g, x, Feuille) -> max x (maxAB g)
  40. | Noeud (g, x, d) -> max x (max (maxAB g) (maxAB d))
  41. ;;
  42.  
  43. (* DONE map sur les arbres *)
  44. let rec mapAB f = function
  45. | Feuille -> Feuille
  46. | Noeud (g, x, d) -> Noeud (mapAB f g, f x, mapAB f d)
  47. ;;
  48.  
  49. mapAB (function x -> x + 1) abr1;;
  50.  
  51. let carre = function x -> x * x in
  52. mapAB carre abr1;;
  53.  
  54. (* DONE hauteur de l'arbre *)
  55. let rec hauteurAB = function
  56. | Feuille -> 0
  57. | Noeud (g, x, d) -> 1 + (max (hauteurAB g) (hauteurAB d))
  58. ;;
  59.  
  60. hauteurAB abr1;;
  61.  
  62. (* ---------------------------------------- *)
  63. (* ABR : Arbres binaires de recherche *)
  64. (* ---------------------------------------- *)
  65.  
  66. (* le minimum d'un arbre binaire de recherche *)
  67. let rec minABR = function
  68. | Feuille -> raise ArbreVide
  69. | Noeud (Feuille, x, d) -> x
  70. | Noeud (g, x, d) -> minABR g;;
  71.  
  72. minABR abr1;;
  73.  
  74. (* rechercher un élément dans un ABR *)
  75. let rec rechercherABR n = function
  76. | Feuille -> false
  77. | Noeud (gauche, x, droite) ->
  78. if x = n then true
  79. else
  80. if x > n
  81. then rechercherABR n gauche
  82. else rechercherAB n droite;;
  83.  
  84.  
  85. rechercherABR 33 abr1;;
  86. rechercherABR 30 abr1;;
  87.  
  88. (* DONE insertion d'un entier dans un arbre binaire de recherche *)
  89. exception RepetitionABR
  90. let rec insererABR n = function
  91. | Feuille -> Noeud (Feuille, n, Feuille)
  92. | Noeud (g,x,d) ->
  93. if x = n then raise RepetitionABR
  94. else if x > n
  95. then Noeud (insererABR n g, x, d)
  96. else Noeud (g, x, insererABR n d)
  97. ;;
  98. let abr2 = insererABR 46 abr1;;
  99.  
  100.  
  101. let rec planter = function
  102. | [] -> Feuille
  103. | x::xs -> insererABR x (planter xs)
  104. ;;
  105.  
  106. let abr3 = planter [45; 56; 34; 57; 28; 23];;
  107. parcoursInfixeAB abr3;;
  108.  
  109. let triparABR = function l -> parcoursInfixeAB (planter l);;
  110.  
  111. (* DONE suppression d'un entier dans un arbre binaire de recherche *)
  112. let rec supprimerABR n = function
  113. | Feuille -> Feuille
  114. | Noeud (g, x, d) when n != x ->
  115. if n < x
  116. then Noeud (supprimerABR n g, x, d)
  117. else Noeud (g, x, supprimerABR n d)
  118. | Noeud (g, x, Feuille) -> g
  119. | Noeud (Feuille, x, d) -> d
  120. | Noeud (g, x, d) -> let r = minABR(d) in
  121. Noeud (g, r, supprimerABR r d)
  122. ;;
  123.  
  124. parcoursInfixeAB abr3;;
  125. parcoursInfixeAB (supprimerABR 56 abr3);;
  126.  
  127. ;;
  128.  
  129. (* ---------------------------------------- *)
  130. (* Affichage /joli/ des arbres binaires *)
  131. (* ---------------------------------------- *)
  132.  
  133. (* affichera le debut de la ligne courante... *)
  134. let rec afficher_indentation = function
  135. | [] -> ()
  136. | true::xs ->
  137. afficher_indentation xs;
  138. | false::xs ->
  139. afficher_indentation xs;
  140. ;;
  141.  
  142. afficher_indentation [false; true; true; false; true; false; false];
  143. ;;
  144.  
  145. (* On utilise une liste auxilliaire pour se souvenir du debut de la *)
  146. (* ligne courante lors des appels récursifs. *)
  147. let rec afficherAB_inner liste = function
  148. | Feuille -> ()
  149. | Noeud (Feuille, x, Feuille) ->
  150. afficher_indentation liste;
  151. | Noeud (gauche, x, Feuille) ->
  152. afficher_indentation (true::liste);
  153. afficher_indentation liste;
  154. afficherAB_inner liste gauche
  155. | Noeud (Feuille, x, droite) ->
  156. print_string " -- ";
  157. afficherAB_inner (false::liste) droite
  158. | Noeud (gauche, x, droite) ->
  159. print_string " -- ";
  160. afficherAB_inner (true::liste) droite;
  161. afficher_indentation liste;
  162. afficherAB_inner liste gauche
  163. ;;
  164.  
  165. let afficherAB arbre = afficherAB_inner [] arbre;;
  166.  
  167. afficherAB abr1;;
  168. afficherAB abr2;;
  169. afficherAB abr3;;
  170. let abr4 = insererABR 60 abr1;;
  171. afficherAB abr4;;
  172. let abr5 = supprimerABR 10 abr4;;
  173. afficherAB abr5;;

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]