Option info - TD6 Arbres, Piles et Files

type 'a arbre = Vide|Noeud of 'a * 'a arbre * 'a arbre;;

let exemple =
Noeud(1,
        Noeud(2,
                Noeud(4,Vide,Vide),
                Noeud(5,
                        Noeud(8,Vide,Vide),
                        Noeud(9,Vide,Vide)
                        )),
        Noeud(3,
                Noeud(6,Vide,Vide),
                Noeud(7,Vide,Vide)));;

(* Un parcours en largeur *)

let parcours_largeur arbre =
    let rec auxparcours en_attente a_renvoyer = match en_attente with
        | [] -> a_renvoyer
        | Vide::t -> auxparcours t a_renvoyer
        | Noeud (a,fg,fd)::t -> auxparcours (t@[fg]@[fd]) (a::(a_renvoyer))
        in
        List.rev(auxparcours [arbre] []);;


(* Deux parcours en profondeur *)

let parcours_profondeur arbre =
    let rec auxparcours arbre a_renvoyer = match arbre with
    | Vide -> a_renvoyer
    | Noeud (n,fg,fd) -> auxparcours fd (auxparcours fg (n::a_renvoyer))
    in
    List.rev(auxparcours arbre []);;

parcours_profondeur exemple;;

let parcours_profondeur_liste arbre =
    let rec aux en_attente a_renvoyer = match en_attente with
        | [] -> a_renvoyer
        | Vide::t -> aux t a_renvoyer
        | Noeud (a,fg,fd)::t -> aux (fg::fd::t) (a::(a_renvoyer))
        in
        List.rev(aux [arbre] []);;

parcours_profondeur_liste exemple;;


(*
La complexité dans le meilleur des cas est O(n) -> t toujours vide, donc linéaire
La complexité dans le pire des cas est O(n²) -> on concatène, donc O(n) par appel.
Il aurait fallu utiliser des files
*)



(* TP 6 Structures de données *)

(* Exercice 1 *)
• Queue.create crée une nouvelle le, vide au départ. C'est donc l'implémentation de creer_le_vide.
• Queue.is_empty teste si une le est vide. C'est donc l'implémentation de est_vide.
• Stack.add permet d'emler un élément à la n d'une le. C'est donc l'implémentation de enler.
• Queue.take élimine le premier élément dans la le (effet de bord) et le retourne. Si la le est vide, cela provoque l'exception Empty. C'est donc l'implémentation de defiler;;


(* Une première fonction qui transforme une 'a Queue en 'a liste, et inversément *)

let queue_into_list q =
let l = ref [] in
let condition = ref true in
while !condition do
    if (Queue.is_empty q) then condition:=false
    else l:= (Queue.take q)::(!l)
    done;
List.rev(!l);;

let list_into_queue l =
let rec aux l q = match l with
|[] -> q
|h::t -> begin (Queue.add h q);
            aux t q;
            end
in aux l ( Queue.create () );;

queue_into_list (list_into_queue [1;2;3;4]);;


(* On réadapte la fonction parcours_en_largeur sur des files ! *)

let parcours_largeur_file arbre =

let file = Queue.create () in
Queue.add arbre file;

let rec aux a_renvoyer =
if Queue.is_empty file then a_renvoyer
else
let arbre = Queue.take file in
match arbre with
|Vide -> aux (a_renvoyer)
|Noeud (n,fg,fd) ->     begin
                            Queue.add fg file;
                            Queue.add fd file;
                            aux (n::a_renvoyer);
                            end
in List.rev (aux []);;

parcours_largeur_file exemple;;


(* Exercice 2.1 *)


let stack_into_list s =
let l = ref [] in
let condition = ref true in

while !condition do

if Stack.is_empty s then condition:=false
else l:=(Stack.pop s)::!l
done;
(List.rev !l);;


let list_into_stack l =
let s = Stack.create () in

let rec aux l = match l with
|[] -> s
|h::t -> (Stack.push h s);
            aux t;
in
aux (List.rev l);;


stack_into_list (list_into_stack [1;2;3;4]);;



(* Exercice 2.2 *)

type couleur = Bleue | Rouge and assiette = couleur * int ;;



let range_assiette pile =

let pile_rouge = Stack.create () in
let pile_bleue = Stack.create () in



while not (Stack.is_empty pile) do
let assiette = Stack.pop pile in
match assiette with
|(Bleue,a) -> Stack.push (Bleue,a) pile_bleue
|(Rouge,a) -> Stack.push (Rouge,a) pile_rouge
done;

while not (Stack.is_empty pile_bleue) do
let assiette = Stack.pop pile_bleue in
Stack.push assiette pile;
done;
while not (Stack.is_empty pile_rouge) do
let assiette = Stack.pop pile_rouge in
Stack.push assiette pile;
done;;

let s = list_into_stack [(Bleue,5);(Rouge,6);(Bleue,7);(Rouge,9)];;
range_assiette s;;
stack_into_list s;;