Provided by: manpages-fr-dev_3.65d1p1-1_all 
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 postorder 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.65 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> ».
GNU 5 janvier 2014 TSEARCH(3)