Provided by:
manpages-fr-dev_3.27fr1.4-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
#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> >>.