Provided by: manpages-fr_1.67.0-1_all bug

NOM

       tsearch, tfind, tdelete, twalk - Manipulation d’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 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). 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.  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é,
       alors 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, 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, et 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  tous  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.

ATTENTION

       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 *root=NULL;

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

           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 which, const int depth)
           {
             int *datap;
             void *val;

             switch(which)
               {
               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;
               }
             return;
           }

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

             for (i = 0; i < 12; i++)
               {
                 ptr = (int *)xmalloc(sizeof(int));
                 *ptr = rand()&0xff;
                 val = tsearch((void *)ptr, &root, compare);
                 if(val == NULL) exit(1);
               }
             twalk(root, action);
             return 0;
           }

CONFORMITÉ

       SVID.  La fonction tdestroy() est une extension GNU.

VOIR AUSSI

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

TRADUCTION

       Christophe Blaess, 1996-2003.