TP du 2 juin et du 26 mai 2021 OCAML

ocaml_bintree_base.ml

type 'a binaryTree =
	| None
	| Node of ('a binaryTree)*'a*('a binaryTree)
;;

let tree1 = Node(
	Node(
		Node(Node(None, 7, None), 4, None),
		2,
		Node(None, 5, None)
	),
	1,
	Node(
		Node(None, 6, None),
		3,
		None
	)
);;

let rec size tree = match tree with
	| None -> 0
	| Node(left, label, right) -> (size left) + (size right) + 1;;

size tree1;;

let rec height tree = match tree with
	| None -> -1
	| Node(left, label, right) -> (
		let hLeft = height left and hRight = height right in
		if hLeft > hRight then (hLeft + 1) else (hRight + 1)
	);;

height tree1;;

let rec maxTree tree = match tree with
	| None -> failwith "Pas de maximum dans un None x)"
	| Node(None, x, None) -> x
	| Node(left, x, None) -> max (maxTree left) x
	| Node(None, x, right) -> max (maxTree right) x
	| Node(left, x, right) -> max (max (maxTree left) (maxTree right)) x;;

maxTree tree1;;

let isTreeFull inTree = 
	let rec aux tree = match tree with
		| None -> failwith "Cannot say if None is complete"
		| Node(None, x, None) -> (true, 0)
		| Node(left, x, None) -> (false, (snd (aux left)) + 1)
		| Node(None, x, right) -> (false, (snd (aux right)) + 1)
		| Node(left, x, right) -> 
			let (leftB, leftH) = aux left in
			let (rightB, rightH) = aux right in
			(leftB && rightB && leftH = rightH, leftH + 1)
		in
		fst(aux inTree)
	;;

let tree2 = Node(
	Node(
		Node(None, 5, None),
		2,
		Node(None, 5, None)
	),
	1,
	Node(
		Node(None, 6, None),
		3,
		Node(None, 50, None)
	)
);;


let tree3 = Node(
	Node(
		Node(None, 5, None),
		2,
		Node(None, 5, None)
	),
	1,
	Node(
		Node(None, 6, None),
		3,
		None
	)
);;


isTreeFull tree2;;

isTreeFull tree3;;


let arbre_of_vect vect = 
	let len = (Array.length vect) in
	let rec aux i =
		if i >= len then None
		else
			Node(
				(if (2*i+1) >= len then None else (aux (2*i+1))),
				vect.(i),
				(if (2*i+2) >= len then None else (aux (2*i+2)))
			)
		in
	aux 0;;

arbre_of_vect [| 1; 2; 3; 4; 5 |];;

open Graphics;;
#load "graphics.cma";;

let draw_tree tree =
	Graphics.open_graph "1000x1000";
	Graphics.clear_graph ();
	Graphics.set_color Graphics.black;
	Graphics.fill_rect 0 0 1000 1000;

	let rec aux subTree x y i = match subTree with
		| None -> ()
		| Node(left, la, right) -> (
			Graphics.moveto (x) (y);
			(if left != None then (
				Graphics.moveto (x-3) (y-5);
				let toX = x-(i/2) and toY = (y-100) in
	 			Graphics.set_color Graphics.white;
				Graphics.lineto (toX+5) (toY+18);
				aux left toX toY (i/2);
			));
			(if right != None then (
				let toX = x+(i/2) and toY = (y-100) in
				Graphics.moveto (x+9) (y-5);
	 			Graphics.set_color Graphics.white;
				Graphics.lineto (toX+5) (toY+18);
				aux right toX toY (i/2);
			));
			Graphics.set_color Graphics.white;
			Graphics.fill_circle (x+5) (y+5) 15;
			let label = (string_of_int la) in
			Graphics.moveto (x-(if la >= 10 then 3 else 0)) (y-(if la >= 10 then 2 else 1));
			Graphics.set_color Graphics.black;
			Graphics.draw_string label;

		)
	in
	(aux tree 500 800 500);;

let tree4 = arbre_of_vect [| 1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20;21;21;21 |];;

(*
Graphics.moveto 0 480;;
Graphics.draw_string "hello, world!";;
*)
draw_tree tree3;;

let rec prefixe bt = match bt with
		| None -> []
		| Node(left, x, right) -> 
			x::((prefixe left)@(prefixe right))
		;;
		
let rec infixe bt = match bt with
		| None -> []
		| Node(left, x, right) -> 
			(infixe left)@[x]@(infixe right)
		;;
		
let rec postfixe bt = match bt with
		| None -> []
		| Node(left, x, right) -> 
			(postfixe left)@(postfixe right)@[x]
		;;

let rec militaire bt = match bt with
		| None -> []
		| Node(left, x, right) -> 
			militaire
		;;

type 'a file = {mutable file : 'a list};;
let cree_file () = { file = [] };;
let file_vide fil = fil.file = [];;
let ajoute fil e = fil.file <- fil.file @ [e] ;;
let retire fil = if file_vide fil then failwith "file vide"
	else begin
		let e::reste = fil.file in
		fil.file <- reste;
		e
	end ;;

let parcours_militaire arbre = 
	let f = cree_file () in
	let rec aux l =
		if file_vide f then l
		else (
			let a = retire f in
			match a with
			| None -> aux l
			| Node(left, x, right) -> (
				ajoute f left;
				ajoute f right;
				aux (l@[x])
			)
		)
	in
	ajoute f arbre;
	aux [];;
	
parcours_militaire (arbre_of_vect [| 1; 2; 3; 4; 5; 6; 7 |]);;