Provided by: manpages-fr-dev_3.27fr1.4-1_all bug

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));

DESCRIPTION

       tsearch(),  tfind(),  twalk()  et  tdelete() permettent de manipuler un
       arbre  binaire.  Ces  fonctions  implementent  une  generalisation   de
       l'algorithme  T  de Knuth (6.2.2). Le premier membre de chaque noeud de
       l'arbre est un pointeur vers la donnee elle-meme (le programme appelant
       doit  prendre en charge le stockage de ces donnees). compare pointe sur
       une routine de comparaison prenant en argument deux pointeurs  sur  ces
       donnees.  Elle doit renvoyer un entier negatif, nul, ou positif suivant
       que le premier element est inferieur, egal ou superieur au second.

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

       tfind()  fonctionne  comme  tsearch(),  sauf que si l'element n'est pas
       trouve, la fonction tfind() renvoie NULL.

       tdelete() supprime un element de l'arbre. Ses arguments sont les  memes
       que ceux de tsearch().

       twalk()  execute  un balayage en profondeur d'abord, de gauche a droite
       ensuite, de l'arbre binaire. root pointe sur  le  noeud  de  depart  du
       balayage.  S'il  ne s'agit pas de la vraie racine de l'arbre, seule une
       partie de celui-ci sera balayee. twalk()  appelle  la  fonction  action
       chaque  fois qu'un noeud est rencontre (c'est-a-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
       rencontre.  Le  second  est  un  entier  prenant  l'une   des   valeurs
       suivantes :  preorder, postorder, ou endorder suivant qu'il s'agisse de
       la premiere, deuxieme ou troisieme rencontre du noeud, ou  encore  leaf
       s'il  s'agit  d'un  noeud  feuille  (ces  symboles  sont  definis  dans
       <search.h>). Le troisieme argument est  la  profondeur  du  noeud  dans
       l'arbre, zero correspondant a la racine.

       Plus  generalement,  preorder,  postorder  et  endorder  sont vus comme
       preorder, inorder, et postorder : avant de visiter le noeud fils, apres
       le  premier  et avant le second, apres avoir visite les enfants. Ainsi,
       le choix du nom postorder est un peu deroutant.

       tdestroy() supprime tout l'arbre pointe par root, liberant  toutes  les
       ressources allouees par la fonction tsearch(). Pour liberer les donnees
       de chaque noeud, la fonction free_node est invoquee.  Le  pointeur  sur
       les  donnees  est  passe  en  argument  a  cette  fonction.  Si  aucune
       liberation n'est necessaire, free_node doit pointer vers  une  fonction
       ne faisant rien.

VALEUR RENVOY'EE

       tsearch()  renvoie un pointeur sur un element correspondant de l'arbre,
       sur l'element nouvellement ajoute, ou NULL s'il n'y avait pas assez  de
       memoire  pour  ajouter  le  noeud.  tfind()  renvoie  un  pointeur  sur
       l'element recherche ou NULL si aucune correspondance n'a  ete  trouvee.
       Si  plusieurs  elements correspondent a la cle, celui renvoye n'est pas
       specifie.

       tdelete() renvoie un pointeur sur le noeud pere de  celui  detruit,  ou
       NULL si l'element n'a pas ete trouve.

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

CONFORMIT'E

       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 << apres le sous-arbre de gauche, mais
       avant  le  sous-arbre de droite >>. Certains prefereraient appeler ceci
       << inorder >>, et reserver << postorder >> pour indiquer  << apres  les
       deux sous-arbres >>.

       tdelete()  libere  la  memoire  necessaire  au  stockage  du noeud dans
       l'arbre. Le programme appelant est responsable de la liberation  de  la
       memoire occupee par l'element de donnee correspondant.

       Le  programme  d'exemple  s'appuie sur le fait que twalk() ne fait plus
       jamais reference a un noeud apres avoir appele la fonction  utilisateur
       avec  l'argument  << endorder >>  ou  << leaf >>.  Ceci fonctionne avec
       l'implementation de la bibliotheque GNU, mais n'est pas  specifie  sous
       System V.

EXEMPLE

       Le  programme  suivant  insere  douze  nombres aleatoires dans un arbre
       binaire, ou les doublons  sont  regroupes,  puis  affiche  les  nombres
       classes.

       #define _GNU_SOURCE     /* Expose la declaration 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 memoire\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.27 du projet man-pages
       Linux. Une description du projet et des instructions pour signaler  des
       anomalies       peuvent       etre       trouvees      a      l'adresse
       <URL:http://www.kernel.org/doc/man-pages/>.

TRADUCTION

       Depuis 2010, cette traduction est maintenue a l'aide  de  l'outil  po4a
       <URL:http://po4a.alioth.debian.org/>   par   l'equipe   de   traduction
       francophone       au       sein        du        projet        perkamon
       <URL:http://perkamon.alioth.debian.org/>.

       Christophe  Blaess  <URL:http://www.blaess.fr/christophe/> (1996-2003),
       Alain  Portal  <URL:http://manpagesfr.free.fr/>  (2003-2006).   Nicolas
       Francois et l'equipe francophone de traduction de Debian (2006-2009).

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

       Vous  pouvez  toujours avoir acces a la version anglaise de ce document
       en utilisant la commande << man -L C <section> <page_de_man> >>.