tsearch(3) Library Functions Manual tsearch(3) NOM tsearch, tfind, tdelete, twalk, twalk_r, tdestroy - Manipuler un arbre binaire de recherche BIBLIOTHEQUE Bibliotheque C standard (libc, -lc) SYNOPSIS #include typedef enum { preorder, postorder, endorder, leaf } VISIT; void *tsearch(const void *key, void **rootp, int (*compar)(const void *, const void *)); void *tfind(const void *key, void *const *rootp, int (*compar)(const void *, const void *)); void *tdelete(const void *restrict key, void **restrict rootp, int (*compar)(const void *, const void *)); void twalk(const void *root, void (*action)(const void *nodep, VISIT which, int depth)); #define _GNU_SOURCE /* Consultez feature_test_macros(7) */ #include void twalk_r(const void *root, void (*action)(const void *nodep, VISIT which, void *closure), void *closure); void tdestroy(void *root, void (*free_node)(void *nodep)); DESCRIPTION tsearch(), tfind(), twalk() et tdelete() permettent de manipuler un arbre binaire de recherche. Ces fonctions implementent une generalisation de l'algorithme T de Knuth (6.2.2). Le premier membre de chaque noeud de l'arbre est un pointeur vers la donnee elle-meme (le programme appelant doit prendre en charge le stockage de ces donnees). compar pointe sur une routine de comparaison prenant en argument deux pointeurs sur ces donnees. Elle doit renvoyer un entier negatif, nul, ou positif suivant que le premier element est inferieur, egal ou superieur au second. tsearch() recherche un element dans l'arbre. key pointe sur l'element a chercher. rootp pointe vers une variable qui pointe vers la racine de l'arbre. Si l'arbre est vide, alors rootp doit pointer sur une variable devant etre reglee a NULL. Si l'element est trouve dans l'arbre, tsearch() renvoie un pointeur sur le noeud de l'arbre correspondant. (En d'autres termes, tsearch() retourne un pointeur sur un pointeur sur l'element.) Si l'element n'est pas trouve, tsearch() l'ajoute dans l'arbre et renvoie un pointeur sur le noeud de l'arbre correspondant. tfind() fonctionne comme tsearch(), sauf que si l'element n'est pas trouve, la fonction tfind() renvoie NULL. tdelete() supprime un element de l'arbre. Ses arguments sont les memes que ceux de tsearch(). twalk() execute un parcours en profondeur d'abord, de gauche a droite ensuite, de l'arbre binaire. root pointe sur le noeud de depart du parcours. S'il ne s'agit pas de la vraie racine de l'arbre, seule une partie de celui-ci sera balaye. twalk() appelle la fonction action chaque fois qu'un noeud est rencontre (c'est-a-dire trois fois pour un noeud interne et une seule fois pour une feuille de l'arbre). action doit accepter trois arguments. Le premier argument est un pointeur sur le noeud rencontre. La structure du noeud n'est pas specifiee, mais il est possible de transformer le pointeur sous forme de pointeur-vers-pointeur-vers-element afin d'acceder a l'element enregistre dans le noeud. L'application ne doit pas modifier la structure pointee par cet argument. Le deuxieme argument est un entier prenant l'une des valeurs suivantes : preorder, postorder ou endorder suivant qu'il s'agisse de la premiere, deuxieme ou troisieme rencontre du noeud, ou la valeur leaf s'il s'agit d'un noeud feuille (ces symboles sont definis dans ). Le troisieme argument est la profondeur du noeud dans l'arbre, le noeud racine ayant la profondeur zero. Ordinairement, preorder, postorder et endorder sont connus sous le nom preorder (prefixe), inorder (infixe), et postorder (postfixe) : avant de visiter le noeud fils, apres le premier et avant le second, apres avoir visite les enfants. Ainsi, le choix du nom postorder est un peu deroutant. twalk_r() est similaire a twalk(), mais a la place de l'argument depth, le pointeur argument closure est passe a chaque invocation de la fonction de rappel d'action, inchange. Ce pointeur peut etre utilise pour passer de l'information vers et depuis la fonction de rappel de facon sure pour les threads, sans utiliser de variables globales. tdestroy() supprime tout l'arbre pointe par root, liberant toutes les ressources allouees par la fonction tsearch(). Pour liberer les donnees de chaque noeud, la fonction free_node est invoquee. Le pointeur sur les donnees est passe en argument a cette fonction. Si aucune liberation n'est necessaire, free_node doit pointer vers une fonction ne faisant rien. VALEUR RENVOYEE tsearch() renvoie un pointeur sur un noeud correspondant de l'arbre, ou sur le noeud nouvellement ajoute, ou NULL s'il n'y avait pas assez de memoire pour ajouter le noeud. tfind() renvoie un pointeur sur le noeud recherche, ou NULL si aucune correspondance n'a ete trouvee. Si plusieurs elements correspondent a la cle, l'element dont le noeud est renvoye n'est pas specifie. tdelete() renvoie un pointeur sur le noeud pere de celui detruit, ou NULL si l'element n'a pas ete trouve. Si le noeud detruit etait le noeud racine, tdelete() renvoie un pointer ne pointant sur aucun objet valable et auquel il ne faut pas acceder. tsearch(), tfind() et tdelete() renvoient egalement NULL si rootp valait NULL. ATTRIBUTS Pour une explication des termes utilises dans cette section, consulter attributes(7). +----------------------+--------------------------+--------------------+ |Interface | Attribut | Valeur | +----------------------+--------------------------+--------------------+ |tsearch(), tfind(), | Securite des threads | MT-Safe race:rootp | |tdelete() | | | +----------------------+--------------------------+--------------------+ |twalk() | Securite des threads | MT-Safe race:root | +----------------------+--------------------------+--------------------+ |twalk_r() | Securite des threads | MT-Safe race:root | +----------------------+--------------------------+--------------------+ |tdestroy() | Securite des threads | MT-Safe | +----------------------+--------------------------+--------------------+ STANDARDS tsearch() tfind() tdelete() twalk() POSIX.1-2008. tdestroy() twalk_r() GNU. HISTORIQUE tsearch() tfind() tdelete() twalk() POSIX.1-2001, POSIX.1-2008, SVr4. twalk_r() glibc 2.30. NOTES twalk() utilise un pointeur sur la racine, alors que les autres fonctions utilisent un pointeur sur une variable pointant sur la racine. tdelete() libere la memoire necessaire au stockage du noeud dans l'arbre. Le programme appelant est responsable de la liberation de la memoire occupee par l'element de donnees correspondant. Le programme d'exemple s'appuie sur le fait que twalk() ne fait plus jamais reference a un noeud apres avoir appele la fonction utilisateur avec l'argument << endorder >> ou << leaf >>. Ceci fonctionne avec l'implementation de la bibliotheque GNU, mais n'est pas specifie sous System V. EXEMPLES Le programme suivant insere douze nombres aleatoires dans un arbre binaire, ou les doublons sont supprimes, puis affiche les nombres classes. #define _GNU_SOURCE /* Expose la declaration de tdestroy() */ #include #include #include #include #include static void *root = NULL; static void * xmalloc(size_t n) { void *p; p = malloc(n); if (p) return p; fprintf(stderr, "memoire insuffisante\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, VISIT which, int depth) { int *datap; 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; } } int main(void) { int *ptr; int **val; srand(time(NULL)); for (unsigned int i = 0; i < 12; i++) { ptr = xmalloc(sizeof(*ptr)); *ptr = rand() & 0xff; val = tsearch(ptr, &root, compare); if (val == NULL) exit(EXIT_FAILURE); if (*val != ptr) free(ptr); } twalk(root, action); tdestroy(root, free); exit(EXIT_SUCCESS); } VOIR AUSSI bsearch(3), hsearch(3), lsearch(3), qsort(3) TRADUCTION La traduction francaise de cette page de manuel a ete creee par Christophe Blaess , Stephan Rafin , Thierry Vignaud , Francois Micaux, Alain Portal , Jean-Philippe Guerard , Jean-Luc Coulon (f5ibh) , Julien Cristau , Thomas Huriaux , Nicolas Francois , Florentin Duneau , Simon Paillard , Denis Barbier , David Prevot , Jean-Baptiste Holcroft et Gregoire Scano Cette traduction est une documentation libre ; veuillez vous reporter a la GNU General Public License version 3 concernant les conditions de copie et de distribution. Il n'y a aucune RESPONSABILITE LEGALE. Si vous decouvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un message a . Pages du manuel de Linux 6.06 31 octobre 2023 tsearch(3)