(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) (* Arbres binaires *) type 'a bintree = | E | N of 'a bintree * 'a * 'a bintree val size: 'a bintree -> int val perfect: int -> int bintree val height: 'a bintree -> int val preorder: string bintree -> unit val inorder: string bintree -> unit val postorder: string bintree -> unit val preorder_iterative: string bintree -> unit val inorder_iterative: string bintree -> unit val postorder_iterative: string bintree -> unit val left: int -> int bintree val right: int -> int bintree (* un peigne, à gauche ou à droite *) val random: int -> string bintree val random_equi: int -> string bintree val of_array: 'a array -> 'a bintree val of_list: 'a list -> 'a bintree (* équilibré *) val all: int -> int bintree list (* tous les arbres binaires d'une certaine taille la racine de chaque (sous-)arbre porte son nombre d'éléments *) val maxsum: int bintree -> int val maxsum_path: int bintree -> int list * int (* arbres binaires avec décompte du nombre d'éléments *) val count: 'a bintree -> ('a * int) bintree (* O(n) *) val card: ('a * int) bintree -> int (* O(1) *) val nth: ('a * int) bintree -> int -> 'a (* O(h) *) val deepest: 'a bintree -> 'a val print: string bintree -> unit val is_bst: 'a bintree -> bool