Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TD5- LES ARBRES BINAIRES DE RECHERCHE ( CORRIGÉ) Exercice 1 : Soit A un arbre b

TD5- LES ARBRES BINAIRES DE RECHERCHE ( CORRIGÉ) Exercice 1 : Soit A un arbre binaire représenté par des pointeurs contenant des valeurs entières positives et distinctes et soit x un entier appartenant à l’arbre A. (Utilisez les types Nœud, AB et ABR définis en cours). 1. Écrire une fonction récursive Max_Val (A : AB) : entier qui permet de retourner la valeur maximale dans l’arbre binaire A non vide. Fonction Max_Val (A: AB): entier Var X, Y, Z, max : entier Début X  A^.val Si (A^.fg ≠ Nil et A^.fd ≠ Nil) alors Y  Max_Val ( A^.fg ) Z  Max_Val ( A^.fd ) max  Maximum(X, Y, Z ) Sinon Si (A^.fg ≠ Nil ) alors Y  Max_Val ( A^.fg ) max  Maximum(X, Y) Sinon Si (A^.fd ≠ Nil ) alors Z  Max_Val ( A^.fd ) max  Maximum(X, Z ) Sinon max  X Fsi Fsi Fsi Retourner ( max ) Fin // Maximum(…) Fonction retournant le maximum parmi les valeurs entrées en paramètres Fonction Est-ABR ( A : AB) : booléen Var Vgauche, Vdroite : entier Début Si (A = Nil) alors Retourner ( vrai ) Sinon Si ( A^.fg = Nil) alors Vgauche  A^.val - 1 Sinon Vgauche  Max_Val ( A^.fg) Finsi Si ( A^.fd = Nil) alors Vdroite  A^.val - 1 Sinon Vdroite  Min_Val ( A^.fg) Finsi Si (A^.val ≥ Vgauche et A^.val < Vdroite) alors Retourner ( Est-ABR ( A^.fg) et Est-ABR ( A^.fd) ) Finsi Finsi Fin Fonction Père ( A : ABR, x : entier) : ^Nœud Début Si ( A = Nil ) ou ( A^.val = x ) ou ( (A^.fg = Nil et A^.fd = Nil) ) alors Retourner ( Nil ) Sinon Si ( A^.fg^.val = x ) ou ( A^.fd^.val = x ) alors Retourner ( A ) Sinon Si ( A^.val > x ) alors Retourner ( Père ( A^.fg, x ) ) Sinon Retourner ( Père ( A^.fd, x ) ) Fsi Fsi Fsi Fin 2. Nous supposons, dans la suite, que la fonction Min_Val (A : AB): entier, qui retourne la valeur minimale dans A, est définie. Ecrire une fonction récursive Est-ABR (A : AB) : booléen qui retourne vrai si A est un arbre binaire de recherche, faux sinon. 3. Ecrire une fonction récursive Père (A : ABR, x : entier) : ^Nœud qui étant donné un arbre binaire de recherche A et P un nœud de A permet de retourner l’adresse du nœud père de P s’il existe, Nil sinon (P est la racine). 4. Ecrire une fonction Successeur (A : ABR, x: entier):entier qui retourne la valeur immédiatement supérieure à x dans A. Si x n’admet pas de successeur, la fonction retourne -1. Nous supposons, dans la suite, que la fonction prédécesseur(A:ABR,x:entier):entier, qui retourne la valeur immédiatement inférieure à x dans A, est aussi définie. 5. Écrire la fonction récursive Nbr_inf(A: ABR, x: entier) : entier qui retourne le nombre de valeurs inférieures à x dans A. Fonction Successeur ( A : ABR, x : entier) : entier Var Px : entier ; Pe : ^Nœud Début Px  Recherche ( A, x) Si (Px ≠ Nil ) alors Si Px^.fd ≠ Nil ) alors Retourner ( Min(A^.fd) ) Sinon Pe  Père ( A, x ) Tantque ( Pe ≠ Nil ) et ( Pe^.fd = Px ) Faire Px  Pe Pe  Père ( A, Px^.val ) FinTantque Si ( Pe = Nil ) alors Retourner ( -1 ) Sinon Retourner ( Pe^.val) Fsi Finsi Finsi Fin Fonction Nbr_inf ( A : ABR, x : entier) : booléen Var Pr : entier Début Si (A ≠ Nil) alors Pr  prédécesseur ( A, x ) Si ( Pr = -1 ) alors Retourner ( 0 ) Sinon Retourner ( 1 + Nbr_inf ( A, Pr) ) Fsi Fsi Fin Nous supposons, dans la suite, que la fonction Nbr_sup(A: ABR, x: entier): entier qui retourne le nombre de valeurs supérieures à x dans A est aussi définie. 6. Nous voulons maintenant trouver la valeur médiane de l’arbre A. x est la valeur médiane de A si : | Nbr_inf(A, x) - Nbr_sup(A, x)| ≤ 1. (1) Pour trouver la valeur médiane de A, on commence par tester si la racine de A vérifie la propriété (1) ou non, sinon, nous considérons, selon les cas, sa valeur précédente ou sa valeur suivante. La recherche se poursuit jusqu’a trouver la valeur médiane. Écrire la fonction récursive Médiane (A: ABR): entier. Exercice 2 : arbres binaires de recherche et rangs On enrichit la structure des arbres binaires de recherche en ajoutant un champ numérique nbg à chaque nœud, qui contiendra le nombre de nœuds de son sous-arbre gauche. Un ABR non vide est donc représenté par une liste à 4 éléments [val, nbg, fg, fd]. On supposera que les valeurs d’un arbre de recherche sont toutes distinctes. 1. Définir le type ABR correspondant. Fonction Médiane ( A : ABR) : entier Var Ninf, Nsup, x : entier Début x  A^.val Ninf  Nbr_inf(A, x) Nsup  Nbr_sup(A, x) Si ( Abs (Ninf – Nsup) ≤ 1 ) alors Retourner ( x ) Sinon Si ( Ninf > Nsup ) alors Retourner ( Médiane ( A^.fg ) ) Sinon Retourner (Médiane ( A^.fd ) ) Fsi Fsi Fin Type Nœud = enregistrement val : entier nbg : entier fg,fd :^Nœud finenregistrement Type ABR = ^Nœud 2. Dessinez l’arbre de recherche obtenu en insérant dans un arbre vide les valeurs suivantes : 12, 5, 24, 3, 37, 49, 25, 17, 8 et 29, dans cet ordre et en faisant apparaître le champ nbg pour chaque nœud. 3. La procédure permettant d’insérer une nouvelle valeur dans un arbre de recherche doit être modifiée de façon à mettre à jour le champ nbg. Ecrire cette nouvelle procédure d’insertion. 12 3 24 1 5 1 3 0 37 2 17 0 8 0 49 0 25 0 29 0 Procédure Insérer ( var A: ABR, x: entier ) Var Début Si (A = Nil) alors Allouer (A) A^.val  x A^.nbg  0 A^.fg  Nil A^.fd  Nil Sinon Si ( x < A^.val ) alors A^.nbg  A^.nbg + 1 Insérer (A^.fg, x) Sinon Insérer (A^.fd, x) Finsi Finsi Fin 4. Le rang r(x) d’un élément x ﬁgurant dans l’arbre de recherche A est égal au nombre d’éléments de A strictement plus petit que x : le rang du plus petit élément de A est donc égal à 0. Soit r ≥0, écrire une fonction récursive Rechercher (A: ABR, r : entier ): entier qui retourne l’élément (entier) de A de rang r. On suppose que A contient au moins r + 1 éléments. 5. Ecrire une fonction récursive Rang (A: ABR, x : entier): entier qui étant donné un arbre binaire de recherche A et un élément x retourne son rang (on supposera que x existe bien dans A). Fonction Rechercher (A: ABR, r : entier ): entier Début Si (A^.nbg = r ) alors Retourner ( A^.val) Sinon Si ( r < A^.nbg ) alors Retourner (Recherche (A^.fg, r)) Sinon Retourner (Recherche (A^.fd, r – A^.nbg - 1)) Finsi Finsi Fin Fonction Rang (A: ABR, x : entier): entier Début Si (A^.val = x ) alors Retourner ( A^.nbg) Sinon Si ( x < A^.val ) alors Retourner (Rang (A^.fg, x)) Sinon Retourner (Rang (A^.fd, x ) + A^.nbg + 1)) Finsi Finsi Fin Exercice 3 : Un étudiant en physique lui a été confié d’effectuer des expérimentations et de collecter des mesures. Les valeurs mesurées, qui sont de type réels, ont été stockées dans une structure arborescente de type ABR. L’étudiant prend ces valeurs pour les montrer à son tuteur. Celui- ci lui a indique que des études théoriques affirment que ces valeurs doivent être en dehors d’un certain intervalle [Vmin, Vmax]. Ainsi, il demande à son étudiant de vérifier que les valeurs mesurées appartenant à cet intervalle ne dépassent pas les 5%; sinon il va falloir réviser le dispositif et refaire les expérimentations. Pour aider votre camarade, il vous est demandé d’écrire une procédure : Affiche_interalle ( A : ABR, Vmin, Vmax: réel) 1. qui affiche les valeurs de l’ABR qui appartiennent à l’intervalle [Vmin, Vmax] dans l’ordre croissant. Vmin et Vmax sont deux constantes réelles données. Cette procédure doit respecter les régles suivantes: - le parcours doit être optimisé: on ne doit pas parcourir les sous-arbres si on’a pas d’espoir de trouver des valeurs appartenant à cet intervalle; - un arbre dont la racine n’appartient pas à cet intervalle peut avoir dans sa descendance des nœuds portant des valeurs appartenant à l’intervalle; On ne fait qu’un seul parcours de l’arbre, sans faire aucune recherche. Procédure Affiche_interalle ( A : ABR, Vmin, Vmax: réel) Début Si (A ≠ Nil) alors Si (A^.val < Vmin) alors Affiche_intervalle (A^.fd, Vmin, Vmax) Sinon Si (A^.val ≤ Vmax) alors Affiche_intervalle(A^.fg, Vmin, Vmax) écrire (A^.val) uploads/Science et Technologie/ td-abr-corrige.pdf