(* Un type des arbres binaires d'entiers *) type arbreBin = | Feuille | Noeud of arbreBin * int * arbreBin;; exception ArbreVide;; (* DONE faire un autre exemple d'arbre *) let abr1 = Noeud (Noeud (Feuille, 10, Feuille), 20, Noeud (Noeud (Feuille, 30, Noeud (Feuille, 40, Feuille)), 50, Feuille));; (* parcours infixe retourne une liste standard *) let rec parcoursInfixeAB = function | Feuille->[] | Noeud (gauche,x,droit) -> parcoursInfixeAB(gauche)@ x::parcoursInfixeAB(droit);; parcoursInfixeAB abr1;; (* un affichage structuré des AB *) let rec afficherABligne = function | Feuille -> print_string "." | Noeud (gauche, x, droite) -> print_string "("; afficherABligne gauche; print_string ", "; print_int x; print_string ", "; afficherABligne droite; print_string ")" ;; (* DONE le plus grand entier d'un arbre binaire quelconque *) let rec maxAB = function | Feuille -> raise ArbreVide | Noeud (Feuille, x, Feuille) -> x | Noeud (Feuille, x, d) -> max x (maxAB d) | Noeud (g, x, Feuille) -> max x (maxAB g) | Noeud (g, x, d) -> max x (max (maxAB g) (maxAB d)) ;; (* DONE map sur les arbres *) let rec mapAB f = function | Feuille -> Feuille | Noeud (g, x, d) -> Noeud (mapAB f g, f x, mapAB f d) ;; mapAB (function x -> x + 1) abr1;; let carre = function x -> x * x in mapAB carre abr1;; (* DONE hauteur de l'arbre *) let rec hauteurAB = function | Feuille -> 0 | Noeud (g, x, d) -> 1 + (max (hauteurAB g) (hauteurAB d)) ;; hauteurAB abr1;; (* ---------------------------------------- *) (* ABR : Arbres binaires de recherche *) (* ---------------------------------------- *) (* le minimum d'un arbre binaire de recherche *) let rec minABR = function | Feuille -> raise ArbreVide | Noeud (Feuille, x, d) -> x | Noeud (g, x, d) -> minABR g;; minABR abr1;; (* rechercher un élément dans un ABR *) let rec rechercherABR n = function | Feuille -> false | Noeud (gauche, x, droite) -> if x = n then true else if x > n then rechercherABR n gauche else rechercherAB n droite;; rechercherABR 33 abr1;; rechercherABR 30 abr1;; (* DONE insertion d'un entier dans un arbre binaire de recherche *) exception RepetitionABR let rec insererABR n = function | Feuille -> Noeud (Feuille, n, Feuille) | Noeud (g,x,d) -> if x = n then raise RepetitionABR else if x > n then Noeud (insererABR n g, x, d) else Noeud (g, x, insererABR n d) ;; let abr2 = insererABR 46 abr1;; let rec planter = function | [] -> Feuille | x::xs -> insererABR x (planter xs) ;; let abr3 = planter [45; 56; 34; 57; 28; 23];; parcoursInfixeAB abr3;; let triparABR = function l -> parcoursInfixeAB (planter l);; (* DONE suppression d'un entier dans un arbre binaire de recherche *) let rec supprimerABR n = function | Feuille -> Feuille | Noeud (g, x, d) when n != x -> if n < x then Noeud (supprimerABR n g, x, d) else Noeud (g, x, supprimerABR n d) | Noeud (g, x, Feuille) -> g | Noeud (Feuille, x, d) -> d | Noeud (g, x, d) -> let r = minABR(d) in Noeud (g, r, supprimerABR r d) ;; parcoursInfixeAB abr3;; parcoursInfixeAB (supprimerABR 56 abr3);; ;; (* ---------------------------------------- *) (* Affichage /joli/ des arbres binaires *) (* ---------------------------------------- *) (* affichera le debut de la ligne courante... *) let rec afficher_indentation = function | [] -> () | true::xs -> afficher_indentation xs; print_string " | " | false::xs -> afficher_indentation xs; print_string " " ;; afficher_indentation [false; true; true; false; true; false; false]; print_int 12; print_string "\n" ;; (* On utilise une liste auxilliaire pour se souvenir du debut de la *) (* ligne courante lors des appels récursifs. *) let rec afficherAB_inner liste = function | Feuille -> () | Noeud (Feuille, x, Feuille) -> print_int x; print_string "\n"; afficher_indentation liste; | Noeud (gauche, x, Feuille) -> print_int x; print_string "\n"; afficher_indentation (true::liste); print_string "\n"; afficher_indentation liste; afficherAB_inner liste gauche | Noeud (Feuille, x, droite) -> print_int x; print_string " -- "; afficherAB_inner (false::liste) droite | Noeud (gauche, x, droite) -> print_int x; print_string " -- "; afficherAB_inner (true::liste) droite; print_string "\n"; afficher_indentation liste; afficherAB_inner liste gauche ;; let afficherAB arbre = afficherAB_inner [] arbre;; afficherAB abr1;; afficherAB abr2;; afficherAB abr3;; let abr4 = insererABR 60 abr1;; afficherAB abr4;; let abr5 = supprimerABR 10 abr4;; afficherAB abr5;;