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.      print_string "(";
  31.      afficherABligne gauche;
  32.      print_string ", ";
  33.      print_int x;
  34.      print_string ", ";
  35.      afficherABligne droite;
  36.      print_string ")"
  37. ;;
  38.  
  39. (* DONE le plus grand entier d'un arbre binaire quelconque *)
  40. let rec maxAB = function
  41.   | Feuille -> raise ArbreVide
  42.   | Noeud (Feuille, x, Feuille) -> x
  43.   | Noeud (Feuille, x, d) -> max x (maxAB d)
  44.   | Noeud (g, x, Feuille) -> max x (maxAB g)
  45.   | Noeud (g, x, d) -> max x (max (maxAB g) (maxAB d))
  46. ;;
  47.  
  48. (* DONE map sur les arbres *)
  49. let rec mapAB f = function
  50.   | Feuille -> Feuille
  51.   | Noeud (g, x, d) -> Noeud (mapAB f g, f x, mapAB f d)
  52. ;;
  53.  
  54. mapAB (function x -> x + 1) abr1;;
  55.  
  56. let carre = function x -> x * x in
  57.     mapAB carre abr1;;
  58.  
  59. (* DONE hauteur de l'arbre *)
  60. let rec hauteurAB = function
  61.   | Feuille -> 0
  62.   | Noeud (g, x, d) -> 1 +  (max (hauteurAB g) (hauteurAB d))
  63. ;;
  64.  
  65. hauteurAB abr1;;
  66.  
  67. (* ---------------------------------------- *)
  68. (* ABR : Arbres binaires de recherche       *)
  69. (* ---------------------------------------- *)
  70.  
  71. (* le minimum d'un arbre binaire de recherche *)
  72. let rec minABR = function
  73.   | Feuille -> raise ArbreVide
  74.   | Noeud (Feuille, x, d) -> x
  75.   | Noeud (g, x, d) -> minABR g;;
  76.  
  77. minABR abr1;;
  78.  
  79. (* rechercher un élément dans un ABR *)
  80. let rec rechercherABR n = function
  81.   | Feuille -> false
  82.   | Noeud (gauche, x, droite) ->
  83.      if x = n then true
  84.      else
  85.        if x > n
  86.        then rechercherABR n gauche
  87.        else rechercherAB n droite;;
  88.  
  89.  
  90. rechercherABR 33 abr1;;
  91. rechercherABR 30 abr1;;
  92.  
  93. (* DONE insertion d'un entier dans un arbre binaire de recherche *)
  94. exception RepetitionABR
  95. let rec insererABR n = function
  96.   | Feuille -> Noeud (Feuille, n, Feuille)
  97.   | Noeud (g,x,d) ->
  98.      if x = n then raise RepetitionABR
  99.      else if x > n
  100.      then Noeud (insererABR n g, x, d)
  101.      else Noeud (g, x, insererABR n d)
  102. ;;
  103. let abr2 = insererABR 46 abr1;;
  104.  
  105.  
  106. let rec planter = function
  107.   | [] -> Feuille
  108.   | x::xs -> insererABR x (planter xs)
  109. ;;
  110.  
  111. let abr3 = planter [45; 56; 34; 57; 28; 23];;
  112. parcoursInfixeAB abr3;;
  113.  
  114. let triparABR = function l -> parcoursInfixeAB (planter l);;
  115.  
  116. (* DONE suppression d'un entier dans un arbre binaire de recherche *)
  117. let rec supprimerABR n = function
  118.   | Feuille -> Feuille
  119.   | Noeud (g, x, d) when n != x ->
  120.      if n < x
  121.      then Noeud (supprimerABR n g, x, d)
  122.      else Noeud (g, x, supprimerABR n d)
  123.   | Noeud (g, x, Feuille) -> g
  124.   | Noeud (Feuille, x, d) -> d
  125.   | Noeud (g, x, d) -> let r = minABR(d) in
  126. Noeud (g, r, supprimerABR r d)
  127. ;;
  128.  
  129. parcoursInfixeAB abr3;;
  130. parcoursInfixeAB (supprimerABR 56 abr3);;
  131.  
  132. ;;
  133.  
  134. (* ---------------------------------------- *)
  135. (* Affichage /joli/ des arbres binaires     *)
  136. (* ---------------------------------------- *)
  137.  
  138. (* affichera le debut de la ligne courante... *)
  139. let rec afficher_indentation = function
  140.   | [] -> ()
  141.   | true::xs ->
  142.      afficher_indentation xs;
  143.      print_string " |    "
  144.   | false::xs ->
  145.      afficher_indentation xs;
  146.      print_string "      "
  147. ;;
  148.  
  149. afficher_indentation [false; true; true; false; true; false; false];
  152. ;;
  153.  
  154. (* On utilise une liste auxilliaire pour se souvenir du debut de la *)
  155. (* ligne courante lors des appels récursifs.                        *)
  156. let rec afficherAB_inner liste = function
  157.   | Feuille -> ()
  158.   | Noeud (Feuille, x, Feuille) ->
  159.      print_int x;
  160.      print_string "\n";
  161.      afficher_indentation liste;
  162.   | Noeud (gauche, x, Feuille) ->
  163.      print_int x;
  164.      print_string "\n";
  165.      afficher_indentation (true::liste);
  166.      print_string "\n";
  167.      afficher_indentation liste;
  168.      afficherAB_inner liste gauche
  169.   | Noeud (Feuille, x, droite) ->
  170.      print_int x;
  171.      print_string " -- ";
  172.      afficherAB_inner (false::liste) droite
  173.   | Noeud (gauche, x, droite) ->
  174.      print_int x;
  175.      print_string " -- ";
  176.      afficherAB_inner (true::liste) droite;
  177.      print_string "\n";
  178.      afficher_indentation liste;
  179.      afficherAB_inner liste gauche
  180. ;;
  181.  
  182. let afficherAB arbre = afficherAB_inner [] arbre;;
  183.  
  184. afficherAB abr1;;
  185. afficherAB abr2;;
  186. afficherAB abr3;;
  187. let abr4 = insererABR 60 abr1;;
  188. afficherAB abr4;;
  189. let abr5 = supprimerABR 10 abr4;;
  190. afficherAB abr5;;

Télécharger

Recherche

Enseignement

Administration

Université Sorbonne Paris Nord Des services numériques pour étudier
Curriculum Vitæ [pdf]
Comment me contacter

Autres réalisations (logiciels, etc.)

Bluehats & UnivMobile , Présentation de la démarche design employée pour UnivMobile faite à la rencontre bluehats du 11 décembre 2019. [pdf, jpg]
Mon université en 2030, Texte d'une intervention que j'ai faite dans le cadre d'une soirée Cap 2030, organisée par le EdFab à Cap Digital le 27 février (...)
Thymio, Python et Asebamedulla
des QCM en ligne grâce à org-mode (et jQuery, et MathJax), org-mode [org, html, css]

Café

Expérience du désir
Enseigner la programmation
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 (...)
Paris 13 Villetaneuse, pas encore la vélorution !
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]

Divers

Affiche CiE 2016
Augmenter l’espace de stockage d’un hote GNU/Linux (VirtualBox etc.)
AperoTIC sur les réseaux sociaux
ADULLACT, Pour être un peu moins seul à défendre l'usage et le développement de logiciels libres dans mon travail (et autour), j'ai adhéré à l'ADULLACT en tant (...)
Hacker l’éducation (Open bidouille camp 2 // Fac lab de Gennevilliers)
Expo : et l’Homme… créa le robot
MathJax
Onglets dans un rapport $\LaTeX$ [gz, png, pdf, gz]
Logo LIPN et accessoires [svg, svg, png, tex, pdf, tif, zip, png, eps, svg]
Ventilo pour ibook (retrouvé) [jpg]