Provided by: manpages-fr-dev_2.64.1-1_all bug

NOM

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

SYNOPSIS

       #include <search.h>

       void *tsearch(const void *clé, void **racptr,
        int (*compare)(const void *, const void *));

       void *tfind(const void *clé, const void **racptr,
        int (*compare)(const void *, const void *));

       void *tdelete(const void *clé, void **racptr,
        int (*compare)(const void *, const void *));

       void twalk(const void *racine, void (*action)(const void *noeudp,
        const VISIT type,
        const int prof));

       #define _GNU_SOURCE
       #include <search.h>

       void tdestroy(void *racine, void (*libérer_noeud)(void *noeudp));

DESCRIPTION

       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. clé pointe sur l’élément à
       chercher.  Si  l’arbre  est  vide,  alors  racptr  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. racine 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 racine, libérant toutes les
       ressources allouées par la fonction tsearch(). Pour libérer les données
       de  chaque  noeud,  la fonction libérer_noeud est invoquée. Le pointeur
       sur les données est passé en  argument  à  cette  fonction.  Si  aucune
       libération  n’est  nécessaire,  libérer_noeud  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  racptr
       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
       SysV.

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.

       #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 *noeudp, const VISIT type, const int prof)
       {
           int *datap;

           switch (type) {
           case preorder:
               break;
           case postorder:
               datap = *(int **) noeudp;
               printf("%6d\n", *datap);
               break;
           case endorder:
               break;
           case leaf:
               datap = *(int **) noeudp;
               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, &racine, compare);
               if (val == NULL)
                   exit(EXIT_FAILURE);
           }
           twalk(racine, action);
           exit(EXIT_SUCCESS);
       }

VOIR AUSSI

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

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> ».