Provided by:
manpages-es_1.55-3_all 
NOMBRE
tsearch, tfind, tdelete, twalk - manejan un árbol 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ÓN
tsearch, tfind, twalk y tdelete manejan un árbol binario. Son una
generalización del algoritmo T de Knuth (6.2.2). El primer campo de
cada nodo del árbol es un puntero al correspondiente elemento de datos.
(El programa llamante debe almacenar los datos actuales). compar
apunta a la rutina de comparación, 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 árbol. key apunta al elemento buscado.
rootp apunta a la variable que apunta a la raíz del árbol. Si el árbol
está vacío la variable a la que apunta rootp debería estar a NULL. Si
se encuentra el elemento dentro del árbol tsearch devuelve un puntero
al elemento. Si no lo encuentra, tsearch lo añade y devuelve un
puntero al nuevo elemento.
tfind es como tsearch, sólo que si no encuentra el elemento tfind
devuelve NULL.
tdelete borra un elemento del árbol. Sus argumentos son los mismos que
los de tsearch.
twalk realiza un recorrido en profundidad o en anchura de un árbol
binario. root apunta al nodo de comienzo del recorrido. Si el nodo no
es la raíz sólo se visitará parte del árbol. twalk llama a la función
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 está 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 única vez que
se visita la hoja. (Estos símbolos están definidos en <search.h>). El
tercer argumento es la profundidad del nodo, siendo la profundidad de
la raíz cero.
(Más comúnmente, preorder, postorder, y endorder son conocidos como
preorder, inorder, and postorder: antes de visitar los hijos, después
del primero y antes del segundo, y después de visitar los hijos. Así,
la elección del nombre postorder es bastante confusa.)
tdestroy elimina el árbol entero apuntado por rootp, liberando todos
los recursos reservados por la función tsearch. Para los datos en cada
nodo del árbol se llama a la función free_node. El puntero a los datos
es pasado como argumento a la función. Si esta tarea no es necesaria
free_node debe apuntar a una función que no haga nada.
VALOR DEVUELTO
tsearch devuelve un puntero al elemento igual del árbol, o al elemento
añadido, o NULL si no hubo suficiente memoria para añadir el elemento.
tfind devuelve un puntero al elemento, o NULL si no se encuentra
ninguno igual. Si hay múltiples 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 encontró el elemento.
tsearch, tfind, y tdelete devuelven NULL si rootp es NULL en la entrada
a la función.
ADVERTENCIAS
twalk toma un puntero a la raíz, mientra que las otras funciones toman
un puntero a una variable que apunta a la raíz.
twalk usa postorder con el significado "depués del subárbol izquierdo y
antes del subárbol derecho". Algunas autoridades llamana a esto
"inorden" y reservan "postorden" con el significado "después de ambos
subárboles".
tdelete libera la memoria necesaria para el elemento en el árbol. 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 después de llamar a la función de usuario con el
argumento "endorder" o "leaf". Esto funciona con la biblioteca de GNU,
pero no está en la documentación SysV.
EJEMPLO
El ejemplo siguiente inserta doce números aleatorios en un árbol
binario, donde los números duplicados se meten hacia abajo, e imprime
los números 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 función tdestroy() es una extensión de GNU.
VÉASE TAMBIÉN
qsort(3), bsearch(3), hsearch(3), lsearch(3)