On considère un arbre binaire de recherche ordinaire, où les clés sont par exemple des entiers. Ecrire une procédure récursive pour faire afficher les coupes gauches et droites de l'arbre selon une clé c. Il s'agit de construire deux arbres CoupeGauche et CoupeDroite dont les clés sont respectivement le clés de l'arbre initial inférieures ou égales à c, et les clés de l'arbre initial supérieures à c. Les deux coupes doivent encore être des arbres binaires de recherche et on peut faire ceci sans créer de nouveaux noeuds (pas de new). L'entête d'une procédure qui réalise ceci peut être:
procedure coupe (a:Arbre; c:Typecle; var CoupeGauche,CoupeDroite:Arbre)Vous pourrez visualiser les deux coupes à l'aide du dessin d'un arbre binaire fait en Td7.
Quelle est la complexité de la procédure ?
Une solution apparaîtra ici.