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