1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
.\"
.\" 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 <mpi79470@alu.um.es> 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 <search.h>
.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 <search.h>
.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<search.h>\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 <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;
}
.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)
|
