:: Enseignements :: Licence :: L2 :: 2008-2009 :: Structures de données ::
[LOGO]

Arbres binaires de Recherche

Arbres binaires

Définir le type abr_t nécessaire à la gestion d'un arbre binaire de recherche dont les valeurs stockées aux sommets sont des entiers. On rappelle la propriété des arbres binaires de recherche: Soit x un sommet d'un arbre binaire de recherche. Si y est un sommet du sous-arbre gauche de x alors sa clé est inférieure ou égale à celle de x. Si y est un sommet du sous-arbre droit de x alors sa clé est supérieure à celle associée à x.

  1. Écrire la fonction d'allocation abr_t* abr_alloc(int cle) qui retourne un sommet d'un arbre binaire de recherche initialisé avec la clé cle.
  2. Écrire la procédure abr_t* abr_dealloc(abr_t **abr) qui supprime la memoire allouée pour l'arbre de recherche abr. Au retour de la procédure, abr == NULL.
  3. Écrire la fonction récursive abr_t* abr_rechercher_rec(abr_t *abr, int cle) qui retourne un sommet de clé cle dans l'arbre binaire de recherche abr. La fonction retourne NULL si aucun sommet de l'arbre binaire de recherche n'a la clé cle.
  4. Écrire la fonction abr_t* abr_rechercher_it(abr_t *abr, int cle), version itérative de la fonction abr_t* abr_rechercher_rec(abr_t *abr, int cle).
  5. Écrire la fonction abr_t* abr_minimum(abr_t *abr) (resp. abr_t* abr_minimum(abr_t *abr)) qui retourne le sommet de l'arbre binaire de recherche abr contenant la clé la plus petite (resp. grande).
  6. Écrire la fonction abr_t* abr_successeur(abr_t *abr) (resp. abr_t* abr_predecesseur(abr_t *abr)) qui retourne le sommet de l'arbre binaire de recherche abr contenant la plus petite (resp. grande) clé supérieure (resp. inférieure) à la clé contenue dans le sommet abr.
  7. Écrire la fonction void abr_inserer(abr_t **abr, abr_t *cible) qui insère le sommet cible dans l'arbre binaire de recherche abr.
  8. Écrire la fonction void abr_supprimer(abr_t **abr, abr_t *cible) qui supprime le sommet cible dans l'arbre binaire de recherche abr.
  9. On consière la définitions suivante: /* type parcours arbre binaire */ typedef enum __abr_parcours_t__ { PARCOURS_PREFIXE, PARCOURS_INFIXE, PARCOURS_SUFFIXE } abr_parcours_t; Écrire la fonction void abr_afficher(abr_t *abr, abr_parcours_t parcours) qui affiche les clé de l'arbre binaire de recherche abr dans l'ordre préfixe, infixe ou suffixe (ordre fixé par l'arguement parcours).
  10. Utilisez un arbre binaire de recherche pour trier un tableau d'entiers. Cette méthode est-elle efficace?
© Université de Marne-la-Vallée