NOME¶
tsearch, tfind, tdelete, twalk - gerencia uma árvore binária
SINOPSE¶
#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));
DESCRIÇÃO¶
tsearch,
tfind,
twalk, e
tdelete gerenciam uma
árvore binária. Eles são gerados a partir do Algoritmo T
de Knuth (6.2.2). O primeiro campo em cada nó da árvore é
um ponteiro para o item correspondente de dados. ( O programa solicitante
precisa armazenar os dados atuais).
compar aponta para uma rotina de
comparação, que pega ponteiros para dois itens. Ele deve
retornar um inteiro que é negaivo, ou zero, ou positivo, dependendo se
o primeiro item é menor, igual ou maior que o segundo.
tsearch busca um item na árvore.
key aponta para o item a
ser buscado.
rootp aponta para uma variável que aponta para a
raiz da árvore. Se a árvore está vazia, então a
variável apontada por
rootp deve ser setada para
NULL. Se
o item é encontrado na árvore, então
tsearch
retorna um ponteiro para ele. Se não é encontrado, então
tsearch o acrescenta, e retorna um ponteiro para o novo item
acrescentado.
tfind é como
tsearch, exceto pelo fato de que, se o item
não é encontrado, então
tfind retorna
NULL.
tdelete apaga um item da árvore. Seus argumentos são os
mesmos de
tsearch.
twalk realiza uma travessia de uma árvore binária por
profundidade, da esquerda para a direita.
root aponta para o nó
inicial da travessia. Se aquele nó não é a raiz,
então apenas parte da árvore será visitada.
twalk
chama a função de usuário
action cada vez que um
nó é visitado (ou seja, três vezes para um nó
interno, e uma vez para uma folha).
action, por sua vez, leva
três argumentos. O primeiro é um ponteiro para o nó que
está sendo visitado. O segundo é um inteiro que recebe os
valores
preorder,
postorder e
endorder, dependendo se
este é a primeira, a segundo ou a terceira visita ao nó interno,
ou
leaf se é uma visita única a um nó-folha.
(Estes símbolos são definidos em
<search.h>.) O
terceiro argumento é a profundidade do nó, com zero sendo a
raiz.
VALOR DE RETORNO¶
tsearch retorna um ponteiro para um item encontrado na árvore, ou
para o novo item acrescentado, ou
NULL se havia memória
insuficiente para acrescentar o item.
tfind retorna um ponteiro para o
item, ou
NULL se nada foi encontrado. Se haviam múltiplos
elementos que casaram com a chave, o elemento retornado não é
especificado.
tdelete retorna um ponteiro para o pai do item apagado, ou
NULL se
o item não foi encontrado.
tsearch,
tfind, e
tdelete também retornam
NULL se
rootp era
NULL na entrada.
ALERTAS¶
twalk pega um ponteiro para a raiz, enquanto as outras
funções pegam um ponteiro para uma variável que aponta
para a raiz.
twalk usa
pós-ordem para dizer "depois da
sub-árvore da esquerda, mas antes da sub-árvore da
direita". Algumas autoridades chamariam isto de "em-ordem", e
reservariam "pós-ordem" para dizer "depois de ambas as
sub-árvores".
tdelete libera a memória requerida para o nó na
árvore. O usuário é responsável para liberar a
memória dos dados correspondentes.
O programa exemplo depende do fato de que
twalk não faz
referência adicional a um nó depois de chamar a
função de usuário com o argumento "endorder" ou
"leaf". Isto funciona com a implementação da
biblioteca GNU, mas não está na documentação SysV.
EXEMPLO¶
O programa a seguir insere doze números aleatórios em uma
árvore binária, e então imprime os números em
ordem. Os números são removidos da árvore e seus
armazenamentos são liberados durante a travessia.
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
void *root=NULL;
void *xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if(p) return p;
fprintf(stderr, "memória insuficiente\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;
void *val;
switch(which)
{
case preorder:
break;
case postorder:
datap = *(int **)nodep;
printf("%6d\n", *datap);
break;
case endorder:
datap = *(int **)nodep;
(void)tdelete(datap, &root, compare);
free(datap);
break;
case leaf:
datap = *(int **)nodep;
printf("%6d\n", *datap);
val = tdelete(datap, &root, compare);
free(datap);
break;
}
return;
}
int main()
{
int i, *ptr;
void *val;
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
VEJA TAMBÉM¶
qsort(3),
bsearch(3),
hsearch(3),
lsearch(3)
TRADUZIDO POR LDP-BR EM 03/08/2000¶
RUBENS DE JESUS NOGUEIRA <darkseid99@usa.net> (tradução)
XXXXXX XX XXXXX XXXXXXXX <xxxxxxxxxx@xxx.xxx> (revisão)