Provided by: manpages-fr-dev_4.15.0-9_all 
NOM
tsearch, tfind, tdelete, twalk, twalk_r, tdestroy - Manipuler un arbre binaire de
recherche
SYNOPSIS
#include <search.h>
typedef enum { preorder, postorder, endorder, leaf } VISIT;
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void *tfind(const void *key, void *const *rootp,
int (*compar)(const void *, const void *));
void *tdelete(const void *restrict key, void **restrict rootp,
int (*compar)(const void *, const void *));
void twalk(const void *root,
void (*action)(const void *nodep, VISIT which,
int depth));
#define _GNU_SOURCE /* Consultez feature_test_macros(7) */
#include <search.h>
void twalk_r(const void *root,
void (*action)(const void *nodep, VISIT which,
void *closure),
void *closure);
void tdestroy(void *root, void (*free_node)(void *nodep));
DESCRIPTION
tsearch(), tfind(), twalk() et tdelete() permettent de manipuler un arbre binaire de
recherche. 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 vers la racine de l'arbre. Si l'arbre est vide, alors
rootp doit pointer sur une variable devant être réglée à NULL. Si l'élément est trouvé
dans l'arbre, tsearch() renvoie un pointeur sur le nœud de l'arbre correspondant. (En
d'autres termes, tsearch() retourne un pointeur sur un pointeur sur l'élément.) Si
l'élément n'est pas trouvé, tsearch() l'ajoute dans l'arbre et renvoie un pointeur sur le
nœud de l'arbre correspondant.
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é. 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 de 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.
twalk_r() est similaire à twalk(), mais à la place de l'argument depth, le pointeur
argument closure est passé à chaque invocation de la fonction de rappel d'action,
inchangé. Ce pointeur peut être utilisé pour passer de l'information vers et depuis la
fonction de rappel de façon sûre pour les threads, sans utiliser de variables globales.
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 nœud correspondant de l'arbre, ou sur le nœud
nouvellement ajouté, ou NULL s'il n'y avait pas assez de mémoire pour ajouter le nœud.
tfind() renvoie un pointeur sur le nœud recherché, ou NULL si aucune correspondance n'a
été trouvée. Si plusieurs éléments correspondent à la clé, l’élément dont le nœud est
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é. Si le nœud détruit était le nœud racine, tdelete() renvoie un pointer ne
pointant sur aucun objet valable et auquel il ne faut pas accéder.
tsearch(), tfind() et tdelete() renvoient également NULL si rootp valait NULL.
VERSIONS
twalk_r() a été ajoutée à la glibc dans la version 2.30.
ATTRIBUTS
Pour une explication des termes utilisés dans cette section, consulter attributes(7).
┌─────────────────────────────────────────────┬──────────────────────┬────────────────────┐
│Interface │ Attribut │ Valeur │
├─────────────────────────────────────────────┼──────────────────────┼────────────────────┤
│tsearch(), tfind(), tdelete() │ Sécurité des threads │ MT-Safe race:rootp │
├─────────────────────────────────────────────┼──────────────────────┼────────────────────┤
│twalk() │ Sécurité des threads │ MT-Safe race:root │
├─────────────────────────────────────────────┼──────────────────────┼────────────────────┤
│twalk_r() │ Sécurité des threads │ MT-Safe race:root │
├─────────────────────────────────────────────┼──────────────────────┼────────────────────┤
│tdestroy() │ Sécurité des threads │ MT-Safe │
└─────────────────────────────────────────────┴──────────────────────┴────────────────────┘
CONFORMITÉ
POSIX.1-2001, POSIX.1-2008, SVr4. Les fonctions tdestroy() et twalk_t() sont des
extensions 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ées
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.
EXEMPLES
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 <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
static void *racine = NULL;
static void *
xmalloc(size_t n)
{
void *p;
p = malloc(n);
if (p)
return p;
fprintf(stderr, "insufficient memory\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, VISIT which, int depth)
{
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 **val;
srand(time(NULL));
for (int i = 0; i < 12; i++) {
int *ptr = xmalloc(sizeof(*ptr));
*ptr = rand() & 0xff;
val = tsearch(ptr, &root, compare);
if (val == NULL)
exit(EXIT_FAILURE);
else if (*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 5.13 du projet man-pages Linux. Une description
du projet et des instructions pour signaler des anomalies et la dernière version de cette
page peuvent être trouvées à l'adresse https://www.kernel.org/doc/man-pages/.
TRADUCTION
La traduction française de cette page de manuel a été créée par Christophe Blaess
<https://www.blaess.fr/christophe/>, Stéphan Rafin <stephan.rafin@laposte.net>, Thierry
Vignaud <tvignaud@mandriva.com>, François Micaux, Alain Portal <aportal@univ-montp2.fr>,
Jean-Philippe Guérard <fevrier@tigreraye.org>, Jean-Luc Coulon (f5ibh) <jean-
luc.coulon@wanadoo.fr>, Julien Cristau <jcristau@debian.org>, Thomas Huriaux
<thomas.huriaux@gmail.com>, Nicolas François <nicolas.francois@centraliens.net>, Florentin
Duneau <fduneau@gmail.com>, Simon Paillard <simon.paillard@resel.enst-bretagne.fr>, Denis
Barbier <barbier@debian.org>, David Prévot <david@tilapin.org>, Jean-Baptiste Holcroft
<jean-baptiste@holcroft.fr> et Grégoire Scano <gregoire.scano@malloc.fr>
Cette traduction est une documentation libre ; veuillez vous reporter à la GNU General
Public License version 3 ⟨https://www.gnu.org/licenses/gpl-3.0.html⟩ concernant les
conditions de copie et de distribution. Il n'y a aucune RESPONSABILITÉ LÉGALE.
Si vous découvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un
message à ⟨debian-l10n-french@lists.debian.org⟩.