Previous Up Next
Version pdf - Version archive

1.3  Types récursifs

1.3.1  Tri par arbre binaire de recherche

Un ABR (arbre binaire de recherche) est un arbre tel que pour chaque noeud x, tous les éléments du sous-arbre gauche ont une valeur inférieure à x et tous les éléments du sous-arbre droit ont une valeur supérieure à x. Nous utiliserons dans les exercices suivants le type

type 'a bin_tree = Empty | Node of 'a bin_tree * 'a * 'a bin_tree;;

Exercice 1

Écrire une fonction ins_abr : (’a -> ’a -> bool) -> ’a -> ’a bin_tree -> ’a bin_tree telle que ins_abr f x t insère l’élément x dans l’arbre t en utilisant la fonction de comparaison f.

Exercice 2

Écrire une fonction abr_of_list : (’a -> ’a -> bool) -> ’a list -> ’a bin_tree telle que abr_of_list f l retourne un arbre contenant tous les éléments de l, disposés avec la fonction f.

Exercice 3

Écrire la fonction list_of_abr : ’a bin_tree -> ’a list retournant une liste contenant les éléments de l’arbre passé en paramètre.

Exercice 4

Écrire une fonction tri_liste : (’a -> ’a -> bool) -> ’a list -> ’a list qui trie la liste passée en paramètre à l’aide d’un ABR.

1.3.2  Fonctions

Nous utiliserons le type suivant pour représenter des fonctions simples :

type exp = Const of int | X | Somme of exp * exp | Produit of exp * exp | Puiss of exp * int;;

Exercice 5

Écrire une fonction str_of_exp : exp -> string telle que str_of_exp e retourne une représentation sous forme de chaîne de caractères de l’expression e.

Exercice 6

Écrire une fonction image : exp -> int -> int telle que image e x retourne l’image de x par la fonction e.

Exercice 7

Écrire une fonction derive : exp -> exp retournant la dérivée de l’expression passée en paramètre.

Exercice 8

Écrire une fonction degre : exp -> int retournant le degré du polynôme représenté par l’expression passée en paramètre.


Previous Up Next