Provided by: manpages-fr-dev_3.57d1p1-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         /* Consultez feature_test_macros(7) */
       #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 implémentent une généralisation de l'algorithme T de Knuth (6.2.2).  Le  premier
       membre  de  chaque  nœud 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). compar 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 parcours en profondeur d'abord, de gauche à droite ensuite, de l'arbre
       binaire. root pointe sur le nœud de départ du parcours. 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 nœud est rencontré (c'est-à-dire trois fois pour un nœud  interne
       et  une  seule fois pour une feuille de l'arbre). action doit accepter trois arguments. Le
       premier argument est un pointeur sur le nœud rencontré. La structure  du  nœud  n'est  pas
       spécifiée,    mais   il   est   possible   transformer   le   pointeur   sous   forme   de
       pointeur-vers-pointeur-vers-élément afin d'accéder à l'élément enregistré  dans  le  nœud.
       L'application  ne  doit  pas  modifier  la structure pointée par cet argument. Le deuxième
       argument 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 nœud,
       ou la valeur  leaf  s'il  s'agit  d'un  nœud  feuille  (ces  symboles  sont  définis  dans
       <search.h>).  Le troisième argument est la profondeur du nœud dans l'arbre, le nœud racine
       ayant la profondeur zéro.

       Ordinairement, preorder, postorder et endorder sont connus sous le nom preorder (préfixe),
       inorder  (infixe),  et  postorder  (postfixe) :  avant  de  visiter le nœud fils, après le
       premier et avant le second, après avoir visité les enfants. Ainsi, le choix du  nom  post‐
       order 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 nœud, 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  nœud.
       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 nœud 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.

       tdelete()  libère  la  mémoire  nécessaire  au stockage du nœud 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
       nœud 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 supprimé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>

       static void *racine = NULL;

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

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

       static 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 = 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)

COLOPHON

       Cette  page  fait partie de la publication 3.57 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

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

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

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