Provided by:
manpages-es_1.55-10_all 
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)