OCAML – Correction TP 3 – les arbres

le sujet

cette correction au format .ml

(* Exercice 1 *)

(* Partie 1 *)

type 'a arbreb =
    ArbreVide
  | Noeud of 'a arbreb * 'a * 'a arbreb;;
  
let est_vide a = match a with
    ArbreVide -> true
  | Noeud(_, _, _) -> false;;
  
let fils_gauche a = match a with
    ArbreVide -> failwith "erreur dans fils_gauche - arbre vide"
  | Noeud(fg, _, _) -> fg;;
    
let fils_droit a = match a with
    ArbreVide -> failwith "erreur dans fils_droit - arbre vide"
  | Noeud(_, _, fd) -> fd;;
  
let etiquette a = match a with
    ArbreVide -> failwith "erreur dans etiquette - arbre vide"
  | Noeud(_, etiq, _) -> etiq;;
    
(* Partie 2 *)

let arb = Noeud(
    Noeud(
        Noeud(
            ArbreVide, 
            17, 
            ArbreVide),
        4,
        Noeud(
            Noeud(
                ArbreVide, 
                10, 
                ArbreVide),
            33,
            Noeud(
                ArbreVide, 
                25, 
                ArbreVide))), 
    12, 
    Noeud(
        Noeud(
            ArbreVide, 
            6, 
            ArbreVide),
        23,
        ArbreVide));;

(* Partie 3 *)

let rec egalarbre a1 a2 = match a1 with
    ArbreVide -> (a2 = ArbreVide)
  | Noeud(fg1, v1, fd1) -> 
      if est_vide a2 then false
      else (v1 = (etiquette a2))
        && (egalarbre fg1 (fils_gauche a2)) 
        && (egalarbre fd1 (fils_droit a2));;

let rec egalarbre2 a1 a2 = match a1 with
    ArbreVide -> if (a2 = ArbreVide) then true else false
  | Noeud(fg1, v1, fd1) -> (match a2 with
      ArbreVide -> false
    | Noeud(fg2, v2, fd2) -> (v1 = v2)
        && (egalarbre2 fg1 fg2) 
        && (egalarbre2 fd1 fd2));;

(* Partie 4 *)

let rec memestruct a1 a2 = match a1 with
    ArbreVide -> (a2 = ArbreVide)
  | Noeud(fg1, _, fd1) -> 
      if est_vide a2 then false
      else (memestruct fg1 (fils_gauche a2)) 
        && (memestruct fd1 (fils_droit a2));;

let rec memestruct2 a1 a2 = match a1 with
    ArbreVide -> (a2 = ArbreVide)
  | Noeud(fg1, _, fd1) ->  (match a2 with
      ArbreVide -> false
    | Noeud(fg2, _, fd2) -> (memestruct2 fg1 fg2)
        && (memestruct2 fd1 fd2));;

(* Partie 5 *)

let rec hauteur a = match a with
    ArbreVide -> 0
  | Noeud(fg, _, fd) -> 1 + max (hauteur fg) (hauteur fd);;

(* Partie 6 *)

let rec mirroir a = match a with
    ArbreVide -> ArbreVide
  | Noeud(fg, etiq, fd) -> Noeud(mirroir fd, etiq, mirroir fg);;

(* Exercice 2 *)

(* Partie 1 *)

let rec listevaleurs a = match a with
    ArbreVide -> []
  | Noeud(fg, etiq, fd) -> (listevaleurs fg) @ [etiq] @ (listevaleurs fd);;
  
(* Partie 2 *)

let rec estdans v a = match a with
    ArbreVide -> false;
  | Noeud(fg, etiq, fd) ->
      if v = etiq then true 
      else if v < etiq then estdans v fg
      else estdans v fd;;
      
(* Partie 3 *)

let rec insere v a = match a with
    ArbreVide -> Noeud(ArbreVide, v, ArbreVide)
  | Noeud(fg, etiq, fd) ->
      if v < etiq then Noeud(insere v fg, etiq, fd)
	  else Noeud(fg, etiq, insere v fd);;

(* Partie 4 *)

let a0 = insere 4 (insere 2 (insere 6 (insere 3 (insere 1 (insere 5 ArbreVide)))));;

listevaleurs a0;;