#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() 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 nœud 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 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 est un pointeur sur le nœud rencontré. Le second est un entier prenant l'une des valeurs suivantes : preorder, postorder et endordersuivant qu'il s'agisse de la première, deuxième ou troisième rencontre du nœud, ou encore 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, zéro correspondant à la racine.
(Plus généralement, preorder, postorder et endorder sont vus comme preorder, inorder et postorder : 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.
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 root valait NULL.
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 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 glibc, mais n'est pas spécifié sous System V.
#include <search.h> #include <stdlib.h> #include <stdio.h> #include <time.h> 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(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 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: break; case leaf: datap = *(int **) nodep; printf("%6d\n", *datap); break; } return; } int main(void) { int i, *ptr; void *val; 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); } twalk(root, action); exit(EXIT_SUCCESS); }
Ce document est une traduction réalisée par Christophe Blaess <http://www.blaess.fr/christophe/> le 11 décembre 1996 et révisée le 17 juillet 2008.
L'équipe de traduction a fait le maximum pour réaliser une adaptation française de qualité. La version anglaise la plus à jour de ce document est toujours consultable via la commande : « LANG=C man 3 tsearch ». N'hésitez pas à signaler à l'auteur ou au traducteur, selon le cas, toute erreur dans cette page de manuel.
Dernière mise à jour : 17 juillet 2008