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>
void *racine = NULL;
void *
xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if (p)
return p;
fprintf(stderr, "pas assez de mémoire\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 = 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.44 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> ».