TSEARCH

Index

NOM
SYNOPSIS
DESCRIPTION
VALEUR RENVOYÉE
ATTENTION
EXEMPLE
CONFORMITÉ
VOIR AUSSI
TRADUCTION

NOM

tsearch, tfind, tdelete, twalk, tdestroy - Manipuler un arbre binaire

SYNOPSIS

#include <search.h>

void *tsearch(const void *clé, void **racptr,
 int(*compare)(const void *, const void *));

void *tfind(const void *clé, const void **racptr,
 int(*compare)(const void *, const void *));

void *tdelete(const void *clé, void **racptr,
 int(*compare)(const void *, const void *));

void twalk(const void *racine, void(*action)(const void *noeudp,
 const VISIT type,
 const int prof));

#define _GNU_SOURCE


#include <search.h>

void tdestroy (void *racine, void (*liberer_noeud)(void *noeudp));

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 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. clé pointe sur l'élément à chercher. Si l'arbre est vide, alors racptr 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. racine 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 racine, libérant toutes les ressources allouées par la fonction tsearch(). Pour libérer les données de chaque noeud, la fonction liberer_noeud est invoquée. Le pointeur sur les données est passé en argument à cette fonction. Si aucune libération n'est nécessaire, liberer_noeud 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 racptr 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 « 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 SysV.

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.

    #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
");
      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 *noeudp, const VISIT type, const int prof) {
      int *datap;
    
      switch(type) {
        case preorder:
          break;
        case postorder:
          datap = *(int **)noeudp;
          printf("%6d
", *datap);
          break;
        case endorder:
          break;
        case leaf:
          datap = *(int **)noeudp;
          printf("%6d
", *datap);
          break;
      }
    }
    
    int main() {
      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, &racine, compare);
          if (val == NULL) exit(1);
      }
      twalk(racine, action);
      return 0;
    }

CONFORMITÉ

SVr4, POSIX.1-2001. La fonction tdestroy() est une extension GNU.

VOIR AUSSI

bsearch(3), hsearch(3), lsearch(3), qsort(3)

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.
La traduction de cette page de manuel est basée sur les traductions disponibles sur http://manpagesfr.free.fr/, mais est gérée par l'équipe francophone de traduction de Debian au travers de la liste de discussion debian-l10n-french.
Veuillez signaler toute erreur de traduction 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> ».

Création : octobre 2007