open Tree let () = assert (mem_size E = 0); assert (mem_size (N (E, 1, E)) = 1) let rec perfect n = match n with | 0 -> E | n -> N (perfect (n-1), n, perfect (n-1)) let () = Format.printf "Je teste mem_size avec des arbres binaires parfaits.@."; assert (mem_size (perfect 0) = 0); assert (mem_size (perfect 1) = 1); assert (mem_size (perfect 2) = 3); assert (mem_size (perfect 3) = 7); assert (mem_size (perfect 4) = 15); Format.printf "OK@." let rec perfect2 n = match n with | 0 -> E | n -> let t = perfect2 (n-1) in N (t, n, t) let () = Format.printf "Je teste mem_size avec des arbres binaires parfaits,@."; Format.printf "cette fois construits différemment (avec du partage)@."; assert (mem_size (perfect2 0) = 0); assert (mem_size (perfect2 1) = 1); assert (mem_size (perfect2 2) = 2); assert (mem_size (perfect2 3) = 3); assert (mem_size (perfect2 4) = 4); Format.printf "OK@." let rec fib n = match n with | 0 | 1 as n -> N (E, n, E) | n -> N (fib (n-2), n, fib (n-1)) let () = Format.printf "Je teste mem_size avec des arbres de Fibonacci.@."; assert (mem_size (fib 0) = 1); assert (mem_size (fib 1) = 1); assert (mem_size (fib 2) = 3); assert (mem_size (fib 3) = 5); assert (mem_size (fib 4) = 9); Format.printf "OK@." let fib2 n = let a = Array.make (n + 2) (N (E, 0, E)) in a.(1) <- N (E, 1, E); for k = 2 to n + 1 do a.(k) <- N (a.(k-2), k, a.(k-1)) done; a.(n) let () = Format.printf "Je teste mem_size avec des arbres de Fibonacci,@."; Format.printf "cette fois construits différemment (avec du partage)@."; assert (mem_size (fib2 0) = 1); assert (mem_size (fib2 1) = 1); assert (mem_size (fib2 2) = 3); assert (mem_size (fib2 3) = 4); assert (mem_size (fib2 4) = 5); Format.printf "OK@."; Format.printf "Tous les tests sont passés avec succès.@."