Prépa Code Connexion Inscription

Écrire une fonction est_abr : int arbre -> bool qui renvoie true si l'arbre est un arbre binaire de recherche (ABR) valide, false sinon.

Convention (attention, elle est importante) : pour chaque nœud de valeur v, - toutes les valeurs du sous-arbre gauche sont inférieures ou égales à v (≤), - toutes les valeurs du sous-arbre droit sont strictement supérieures à v (>).

Autrement dit, les doublons sont autorisés à gauche.

est_abr Vide = true.

On écrira une fonction auxiliaire récursive aux : int arbre -> int option -> int option -> bool qui vérifie que toutes les étiquettes d'un sous-arbre sont dans l'intervalle ]min_opt, max_opt] (avec None représentant l'absence de borne). À chaque descente, on resserre l'intervalle.

Différence avec une simple comparaison aux fils directs : il ne suffit pas de vérifier que le fils gauche est ≤ à la racine et le fils droit > ; il faut la contrainte sur tout le sous-arbre.