Provided by: manpages-es_1.55-10_all bug

NOMBRE

       tsearch, tfind, tdelete, twalk - manejan un arbol binario

SINOPSIS

       #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));

DESCRIPCI'ON

       tsearch,  tfind,  twalk  y  tdelete  manejan un arbol binario.  Son una
       generalizacion del algoritmo T de Knuth (6.2.2).  El  primer  campo  de
       cada nodo del arbol es un puntero al correspondiente elemento de datos.
       (El programa llamante  debe  almacenar  los  datos  actuales).   compar
       apunta  a  la  rutina  de  comparacion,  que  toma  punteros  a los dos
       elementos.   Debe  devolver  un  entero  negativo,  cero   o   positivo
       dependiendo  de  si  el  primer elemento es menor, igual o mayor que el
       segundo.

       tsearch busca un elemento en el arbol.  key apunta al elemento buscado.
       rootp apunta a la variable que apunta a la raiz del arbol.  Si el arbol
       esta vacio la variable a la que apunta rootp deberia estar a NULL.   Si
       se  encuentra  el elemento dentro del arbol tsearch devuelve un puntero
       al elemento.  Si no lo  encuentra,  tsearch  lo  anade  y  devuelve  un
       puntero al nuevo elemento.

       tfind  es  como  tsearch,  solo  que  si no encuentra el elemento tfind
       devuelve NULL.

       tdelete borra un elemento del arbol.  Sus argumentos son los mismos que
       los de tsearch.

       twalk  realiza  un  recorrido  en  profundidad o en anchura de un arbol
       binario. root apunta al nodo de comienzo del recorrido.  Si el nodo  no
       es  la raiz solo se visitara parte del arbol.  twalk llama a la funcion
       de usuario action cada vez que se visita un nodo (esto es,  tres  veces
       para  un  nodo  interno  y  una  vez para una hoja).  action, toma tres
       argumentos.  El primero es un puntero al nodo que  se  esta  visitando.
       El  segundo  es  un  entero  cuyo  valor  toma  algundo  de los valores
       preorder, postorder o endorder dependiendo de si esta  es  la  primera,
       sregunda o tercera visita al nodo interno o leaf si es la unica vez que
       se visita la hoja.  (Estos simbolos estan definidos en <search.h>).  El
       tercer  argumento  es la profundidad del nodo, siendo la profundidad de
       la raiz cero.

       (Mas comunmente, preorder, postorder, y  endorder  son  conocidos  como
       preorder,  inorder,  and postorder: antes de visitar los hijos, despues
       del primero y antes del segundo, y despues de visitar los  hijos.  Asi,
       la eleccion del nombre postorder es bastante confusa.)

       tdestroy  elimina  el  arbol entero apuntado por rootp, liberando todos
       los recursos reservados por la funcion tsearch.  Para los datos en cada
       nodo del arbol se llama a la funcion free_node.  El puntero a los datos
       es pasado como argumento a la funcion. Si esta tarea  no  es  necesaria
       free_node debe apuntar a una funcion que no haga nada.

VALOR DEVUELTO

       tsearch  devuelve un puntero al elemento igual del arbol, o al elemento
       anadido, o NULL si no hubo suficiente memoria para anadir el  elemento.
       tfind  devuelve  un  puntero  al  elemento,  o  NULL si no se encuentra
       ninguno igual.  Si hay multiples elementos que concuerdan con la  clave
       el elemento devuelto es inespecificado.

       tdelete devuelve un puntero al padre del elemento borrado, o NULL si no
       se encontro el elemento.

       tsearch, tfind, y tdelete devuelven NULL si rootp es NULL en la entrada
       a la funcion.

ADVERTENCIAS

       twalk  toma un puntero a la raiz, mientra que las otras funciones toman
       un puntero a una variable que apunta a la raiz.

       twalk usa postorder con el significado "depues del subarbol izquierdo y
       antes  del  subarbol  derecho".   Algunas  autoridades  llamana  a esto
       "inorden" y reservan "postorden" con el significado "despues  de  ambos
       subarboles".

       tdelete  libera  la memoria necesaria para el elemento en el arbol.  El
       usuario es el responsable de liberar la memoria de los correspondientes
       datos.

       El  programa  de  ejemplo  depende  del  hecho de que twalk no vuelve a
       referenciar a un nodo despues de llamar a la funcion de usuario con  el
       argumento "endorder" o "leaf".  Esto funciona con la biblioteca de GNU,
       pero no esta en la documentacion SysV.

EJEMPLO

       El ejemplo siguiente  inserta  doce  numeros  aleatorios  en  un  arbol
       binario,  donde  los numeros duplicados se meten hacia abajo, e imprime
       los numeros en orden.

           #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, "insufficient memory\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;

             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() {
             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(1);
             }
             twalk(root, action);
             return 0;
           }

CONFORME A

       SVID.  La funcion tdestroy() es una extension de GNU.

V'EASE TAMBI'EN

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