.\" Copyright 1995 by Jim Van Zandt .\" .\" Se concede autorización para hacer y distribuir copias literales de este .\" manual siempre que el aviso de copyright y esta autorización se conserven .\" en todas las copias. .\" .\" Se concede autorización para copiar y distribuir versiones modificadas de .\" este manual bajo las condiciones de copia literal, siempre que el resultado .\" completo del trabajo realizado se distribuya bajo los términos de una .\" autorización idéntica a esta. .\" .\" Como el núcleo y las bibliotecas de Linux están permanentemente cambiando .\" esta página del manual puede ser incorrecta o estar desactualizada. El .\" autor o autores no asumen ninguna responsabilidad sobre los errores u .\" omisiones, o por los daños que resulten del uso de la información contenida .\" aquí. Puede que el autor o los autores no hayan tenido el mismo cuidado en .\" escribir este manual, cuya licencia es libre de cargo, como el que puedan .\" tener cuando trabajan profesionalmente. .\" .\" Versiones formatadas o procesadas de este manual, si no van acommpañadas .\" por la fuente, deben dar a conocer el copyright y los autores de este .\" trabajo. .\" .\" Traducido por Carlos Gomez Romero (cgomez@databasedm.es) .\" Traducción revisada por Miguel Pérez Ibars el 1-enero-2005 .\" .TH TSEARCH 3 "24 septiembre 1995" "GNU" "Manual del Programador de Linux" .SH NOMBRE tsearch, tfind, tdelete, twalk \- manejan un árbol binario .SH SINOPSIS .nf .B #include .sp .BI "void *tsearch(const void *" key ", void **" rootp , .BI " int(*" compar ")(const void *, const void *));" .sp .BI "void *tfind(const void *" key ", const void **" rootp , .BI " int(*" compar ")(const void *, const void *));" .sp .BI "void *tdelete(const void *" key ", void **" rootp , .BI " int(*" compar ")(const void *, const void *));" .sp .BI "void twalk(const void *" root ", void(*" action ")(const void *" nodep , .BI " const VISIT " which , .BI " const int " depth "));" .sp .B #define _GNU_SOURCE .br .B #include .sp .BI "void tdestroy (void *" root ", void (*" free_node ")(void *" nodep )); .RE .fi .SH DESCRIPCIÓN \fBtsearch\fP, \fBtfind\fP, \fBtwalk\fP y \fBtdelete\fP 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). \fIcompar\fP 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. .PP \fBtsearch\fP busca un elemento en el árbol. \fIkey\fP apunta al elemento buscado. \fIrootp\fP apunta a la variable que apunta a la raíz del árbol. Si el árbol está vacío la variable a la que apunta \fIrootp\fP debería estar a \fBNULL\fP. Si se encuentra el elemento dentro del árbol \fBtsearch\fP devuelve un puntero al elemento. Si no lo encuentra, \fBtsearch\fP lo añade y devuelve un puntero al nuevo elemento. .PP \fBtfind\fP es como \fBtsearch\fP, sólo que si no encuentra el elemento \fBtfind\fP devuelve \fBNULL\fP. .PP \fBtdelete\fP borra un elemento del árbol. Sus argumentos son los mismos que los de \fBtsearch\fP. .PP \fBtwalk\fP realiza un recorrido en profundidad o en anchura de un árbol binario. \fIroot\fP apunta al nodo de comienzo del recorrido. Si el nodo no es la raíz sólo se visitará parte del árbol. \fBtwalk\fP llama a la función de usuario \fIaction\fP cada vez que se visita un nodo (esto es, tres veces para un nodo interno y una vez para una hoja). \fIaction\fP, 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 \fBpreorder\fP, \fBpostorder\fP o \fBendorder\fP dependiendo de si esta es la primera, sregunda o tercera visita al nodo interno o \fBleaf\fP si es la única vez que se visita la hoja. (Estos símbolos están definidos en \fI\fP). El tercer argumento es la profundidad del nodo, siendo la profundidad de la raíz cero. .PP (Más comúnmente, \fBpreorder\fP, \fBpostorder\fP, y \fBendorder\fP son conocidos como \fBpreorder\fP, \fBinorder\fP, and \fBpostorder\fP: 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 \fBpost\%order\fP es bastante confusa.) .PP \fBtdestroy\fP elimina el árbol entero apuntado por \fIrootp\fP, liberando todos los recursos reservados por la función \fBtsearch\fP. Para los datos en cada nodo del árbol se llama a la función \fIfree_node\fP. El puntero a los datos es pasado como argumento a la función. Si esta tarea no es necesaria \fIfree_node\fP debe apuntar a una función que no haga nada. .SH "VALOR DEVUELTO" \fBtsearch\fP devuelve un puntero al elemento igual del árbol, o al elemento añadido, o \fBNULL\fP si no hubo suficiente memoria para añadir el elemento. \fBtfind\fP devuelve un puntero al elemento, o \fBNULL\fP si no se encuentra ninguno igual. Si hay múltiples elementos que concuerdan con la clave el elemento devuelto es inespecificado. .PP \fBtdelete\fP devuelve un puntero al padre del elemento borrado, o \fBNULL\fP si no se encontró el elemento. .PP \fBtsearch\fP, \fBtfind\fP, y \fBtdelete\fP devuelven \fBNULL\fP si \fIrootp\fP es \fBNULL\fP en la entrada a la función. .SH ADVERTENCIAS \fBtwalk\fP toma un puntero a la raíz, mientra que las otras funciones toman un puntero a una variable que apunta a la raíz. .PP \fBtwalk\fP usa \fBpostorder\fP 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". .PP \fBtdelete\fP libera la memoria necesaria para el elemento en el árbol. El usuario es el responsable de liberar la memoria de los correspondientes datos. .PP El programa de ejemplo depende del hecho de que \fBtwalk\fP 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. .SH 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. .sp .nf #include #include #include #include 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; } .fi .SH "CONFORME A" SVID. La función .B tdestroy() es una extensión de GNU. .SH "VÉASE TAMBIÉN" .BR qsort (3), .BR bsearch (3), .BR hsearch (3), .BR lsearch (3)