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;
}
SVID. La función
tdestroy() es una extensión de GNU.
VÉASE TAMBIÉN¶
qsort(3),
bsearch(3),
hsearch(3),
lsearch(3)