Loading

NOM

       tsearch, tfind, tdelete, twalk, tdestroy - Manipuler un arbre binaire

SYNOPSIS

       #include <search.h>

       void *tsearch(const void *key, void **rootp,
                       int (*compar)(const void *, const void *));

       void *tfind(const void *key, const void **rootp,
                       int (*compar)(const void *, const void *));

       void *tdelete(const void *key, void **rootp,
                       int (*compar)(const void *, const void *));

       void twalk(const void *root, void (*action)(const void *nodep,
                                          const VISIT which,
                                          const int depth));

       #define _GNU_SOURCE
       #include <search.h>

       void tdestroy(void *root, void (*free_node)(void *nodep));

       tsearch(),  tfind(),  twalk()  et  tdelete() permettent de manipuler un
       arbre  binaire.  Ces  fonctions  implémentent  une  généralisation   de
       l’algorithme  T  de Knuth (6.2.2). Le premier membre de chaque noeud de
       l’arbre est un pointeur vers la donnée elle-même (le programme appelant
       doit  prendre en charge le stockage de ces données). compare pointe sur
       une routine de comparaison prenant en argument deux pointeurs  sur  ces
       données.  Elle doit renvoyer un entier négatif, nul, ou positif suivant
       que le premier élément est inférieur, égal ou supérieur au second.

       tsearch() recherche un élément dans l’arbre. key pointe sur l’élément à
       chercher.  rootp  pointe  vers  une  variable qui pointe à la racine de
       l’arbre. Si l’arbre est vide, alors rootp doit pointer sur une variable
       pointant  sur  NULL.  Si  l’élément  est trouvé dans l’arbre, tsearch()
       renvoie un pointeur sur celui-ci. Sinon tsearch() ajoute l’élément dans
       l’arbre et renvoie un pointeur sur lui.

       tfind()  fonctionne  comme  tsearch(),  sauf que si l’élément n’est pas
       trouvé, la fonction tfind() renvoie NULL.

       tdelete() supprime un élément de l’arbre. Ses arguments sont les  mêmes
       que ceux de tsearch().

       twalk()  exécute  un balayage en profondeur d’abord, de gauche à droite
       ensuite, de l’arbre binaire. root pointe sur  le  noeud  de  départ  du
       balayage.  S’il  ne s’agit pas de la vraie racine de l’arbre, seule une
       partie de celui-ci sera balayée. twalk()  appelle  la  fonction  action
       chaque  fois qu’un noeud est rencontré (c’est-à-dire trois fois pour un
       noeud interne et une seule fois pour une feuille  de  l’arbre).  action
       doit  accepter trois arguments. Le premier est un pointeur sur le noeud
       rencontré.  Le  second  est  un  entier  prenant  l’une   des   valeurs
       suivantes :  preorder, postorder, ou endorder suivant qu’il s’agisse de
       la première, deuxième ou troisième rencontre du noeud, ou  encore  leaf
       s’il  s’agit  d’un  noeud  feuille  (ces  symboles  sont  définis  dans
       <search.h>). Le troisième argument est  la  profondeur  du  noeud  dans
       l’arbre, zéro correspondant à la racine.

       Plus  généralement,  preorder,  postorder  et  endorder  sont vus comme
       preorder, inorder, et postorder : avant de visiter le noeud fils, après
       le  premier  et avant le second, après avoir visité les enfants. Ainsi,
       le choix du nom postorder est un peu déroutant.

       tdestroy() supprime tout l’arbre pointé par root, libérant  toutes  les
       ressources allouées par la fonction tsearch(). Pour libérer les données
       de chaque noeud, la fonction free_node est invoquée.  Le  pointeur  sur
       les  données  est  passé  en  argument  à  cette  fonction.  Si  aucune
       libération n’est nécessaire, free_node doit pointer vers  une  fonction
       ne faisant rien.

VALEUR RENVOYÉE

       tsearch()  renvoie un pointeur sur un élément correspondant de l’arbre,
       sur l’élément nouvellement ajouté, ou NULL s’il n’y avait pas assez  de
       mémoire  pour  ajouter  le  noeud.  tfind()  renvoie  un  pointeur  sur
       l’élément recherché ou NULL si aucune correspondance n’a  été  trouvée.
       Si  plusieurs  éléments correspondent à la clé, celui renvoyé n’est pas
       spécifié.

       tdelete() renvoie un pointeur sur le noeud père de  celui  détruit,  ou
       NULL si l’élément n’a pas été trouvé.

       tsearch(),  tfind()  et  tdelete()  renvoient  également  NULL si rootp
       valait NULL.

CONFORMITÉ

       SVr4, POSIX.1-2001. La fonction tdestroy() est une extension GNU.

NOTES

       twalk() utilise un  pointeur  sur  la  racine,  alors  que  les  autres
       fonctions  utilisent  un  pointeur  sur  une  variable  pointant sur la
       racine.

       Pour twalk(), postorder signifie « après le sous-arbre de gauche,  mais
       avant  le  sous-arbre  de droite ». Certains préféreraient appeler ceci
       « inorder », et réserver « postorder » pour indiquer « après  les  deux
       sous-arbres ».

       tdelete()  libère  la  mémoire  nécessaire  au  stockage  du noeud dans
       l’arbre. Le programme appelant est responsable de la libération  de  la
       mémoire occupée par l’élément de donnée correspondant.

       Le  programme  d’exemple  s’appuie sur le fait que twalk() ne fait plus
       jamais référence à un noeud après avoir appelé la fonction  utilisateur
       avec   l’argument   « endorder »  ou  « leaf ».  Ceci  fonctionne  avec
       l’implémentation de la bibliothèque GNU, mais n’est pas  spécifié  sous
       System V.

EXEMPLE

       Le  programme  suivant  insère  douze  nombres aléatoires dans un arbre
       binaire, où les doublons  sont  regroupés,  puis  affiche  les  nombres
       classés.

       #define _GNU_SOURCE     /* Expose la déclaration de tdestroy() */
       #include <search.h>
       #include <stdlib.h>
       #include <stdio.h>
       #include <time.h>

       void *racine = NULL;

       void *
       xmalloc(unsigned n)
       {
           void *p;
           p = malloc(n);
           if (p)
               return p;
           fprintf(stderr, "pas assez de mémoire\n");
           exit(EXIT_FAILURE);
       }

       int
       compare(const void *pa, const void *pb)
       {
           if (*(int *) pa < *(int *) pb)
               return -1;
           if (*(int *) pa > *(int *) pb)
               return 1;
           return 0;
       }

       void
       action(const void *nodep, const VISIT type, const int prof)
       {
           int *datap;

           switch (type) {
           case preorder:
               break;
           case postorder:
               datap = *(int **) nodep;
               printf("%6d\n", *datap);
               break;
           case endorder:
               break;
           case leaf:
               datap = *(int **) nodep;
               printf("%6d\n", *datap);
               break;
           }
       }

       int
       main(void)
       {
           int i, *ptr;
           void *val;

           srand(time(NULL));
           for (i = 0; i < 12; i++) {
               ptr = (int *) xmalloc(sizeof(int));
               *ptr = rand() & 0xff;
               val = tsearch((void *) ptr, &root, compare);
               if (val == NULL)
                   exit(EXIT_FAILURE);
               else if ((*(int **) val) != ptr)
                   free(ptr);
           }
           twalk(root, action);
           tdestroy(root, free);
           exit(EXIT_SUCCESS);
       }

VOIR AUSSI

       bsearch(3), hsearch(3), lsearch(3), qsort(3), feature_test_macros(7)

COLOPHON

       Cette  page  fait  partie  de  la  publication 3.23 du projet man-pages
       Linux. Une description du projet et des instructions pour signaler  des
       anomalies       peuvent       être       trouvées      à      l’adresse
       http://www.kernel.org/doc/man-pages/.

TRADUCTION

       Cette page de manuel a été traduite  et  mise  à  jour  par  Christophe
       Blaess  <http://www.blaess.fr/christophe/> entre 1996 et 2003, puis par
       Alain Portal <aportal AT univ-montp2 DOT fr> jusqu’en 2006, et  mise  à
       disposition sur http://manpagesfr.free.fr/.

       Les mises à jour et corrections de la version présente dans Debian sont
       directement         gérées         par         Nicolas         François
       <nicolas.francois@centraliens.net>    et    l’équipe   francophone   de
       traduction de Debian.

       Veuillez  signaler  toute  erreur   de   traduction   en   écrivant   à
       <debian-l10n-french@lists.debian.org> ou par un rapport de bogue sur le
       paquet manpages-fr.

       Vous pouvez toujours avoir accès à la version anglaise de  ce  document
       en utilisant la commande « man -L C <section> <page_de_man> ».