TSEARCH(3) Manuel du programmeur Linux TSEARCH(3)
NOM
tsearch, tfind, tdelete, twalk - Manipulation d'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));
DESCRIPTION
tsearch, tfind, twalk, et tdelete permettent de manipuler
un arbre binaire. Ces fonctions implémentent une générali
sation 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). 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. 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é, alors 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, 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
GNU 11 Decembre 1996 1
TSEARCH(3) Manuel du programmeur Linux TSEARCH(3)
pointeur sur le noeud rencontré. Le second est un entier
prenant l'une des valeurs suivantes : preorder, postorder,
et 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.
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.
ATTENTION
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 "pos
torder" 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 bib
liothèque GNU, mais n'est pas spécifié sous SysV.
EXEMPLE
Le programme suivant insère douze nombres aléatoires dans
un arbre binaire, puis affiche les nombres classés. Les
nombres sont supprimés de l'arbre et la mémoire libérée
durant le balayage.
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
GNU 11 Decembre 1996 2
TSEARCH(3) Manuel du programmeur Linux TSEARCH(3)
void *root=NULL;
void *xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if(p) return p;
fprintf(stderr, "pas assez de mémoire\n");
exit(1);
}
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 which, const int depth)
{
int *datap;
void *val;
switch(which)
{
case preorder:
break;
case postorder:
datap = *(int **)nodep;
printf("%6d\n", *datap);
break;
case endorder:
datap = *(int **)nodep;
(void)tdelete(datap, &root, compare);
free(datap);
break;
case leaf:
datap = *(int **)nodep;
printf("%6d\n", *datap);
val = tdelete(datap, &root, compare);
free(datap);
break;
}
return;
}
int main()
{
int i, *ptr;
void *val;
for (i = 0; i < 12; i++)
{
ptr = (int *)xmalloc(sizeof(int));
GNU 11 Decembre 1996 3
TSEARCH(3) Manuel du programmeur Linux TSEARCH(3)
*ptr = rand()&0xff;
val = tsearch((void *)ptr, &root, compare);
if(val == NULL) exit(1);
}
twalk(root, action);
return 0;
}
CONFORMITÉ
SVID
VOIR AUSSI
qsort(3), bsearch(3), hsearch(3), lsearch(3)
TRADUCTION
Christophe Blaess, 1997.
GNU 11 Decembre 1996 4