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));
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 noeud 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). compare 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 balayage en profondeur d’abord, de gauche à droite
ensuite, de l’arbre binaire. root pointe sur le noeud de départ du
balayage. 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 noeud est rencontré (c’est-à-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
rencontré. Le second 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 noeud, ou encore leaf
s’il s’agit d’un noeud feuille (ces symboles sont définis dans
<search.h>). Le troisième argument est la profondeur du noeud dans
l’arbre, zéro correspondant à la racine.
Plus généralement, preorder, postorder et endorder sont vus comme
preorder, inorder, et postorder : avant de visiter le noeud 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 noeud, 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 noeud. 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 noeud 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.
Pour twalk(), postorder signifie « après le sous-arbre de gauche, mais
avant le sous-arbre de droite ». Certains préféreraient appeler ceci
« inorder », et réserver « postorder » pour indiquer « après les deux
sous-arbres ».
tdelete() libère la mémoire nécessaire au stockage du noeud 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 noeud 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 regroupé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 = (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.23 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
Cette page de manuel a été traduite et mise à jour par Christophe
Blaess <http://www.blaess.fr/christophe/> entre 1996 et 2003, puis par
Alain Portal <aportal AT univ-montp2 DOT fr> jusqu’en 2006, et mise à
disposition sur http://manpagesfr.free.fr/.
Les mises à jour et corrections de la version présente dans Debian sont
directement gérées par Nicolas François
<nicolas.francois@centraliens.net> et l’équipe francophone de
traduction de Debian.
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> ».