Provided by:
manpages-pt-dev_20040726-4_all 
NOME
tsearch, tfind, tdelete, twalk - gerencia uma arvore binaria
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,C~AO
tsearch, tfind, twalk, e tdelete gerenciam uma arvore binaria. Eles
sao gerados a partir do Algoritmo T de Knuth (6.2.2). O primeiro campo
em cada no da arvore e um ponteiro para o item correspondente de dados.
( O programa solicitante precisa armazenar os dados atuais). compar
aponta para uma rotina de comparacao, que pega ponteiros para dois
itens. Ele deve retornar um inteiro que e negaivo, ou zero, ou
positivo, dependendo se o primeiro item e menor, igual ou maior que o
segundo.
tsearch busca um item na arvore. key aponta para o item a ser buscado.
rootp aponta para uma variavel que aponta para a raiz da arvore. Se a
arvore esta vazia, entao a variavel apontada por rootp deve ser setada
para NULL. Se o item e encontrado na arvore, entao tsearch retorna um
ponteiro para ele. Se nao e encontrado, entao tsearch o acrescenta, e
retorna um ponteiro para o novo item acrescentado.
tfind e como tsearch, exceto pelo fato de que, se o item nao e
encontrado, entao tfind retorna NULL.
tdelete apaga um item da arvore. Seus argumentos sao os mesmos de
tsearch.
twalk realiza uma travessia de uma arvore binaria por profundidade, da
esquerda para a direita. root aponta para o no inicial da travessia. Se
aquele no nao e a raiz, entao apenas parte da arvore sera visitada.
twalk chama a funcao de usuario action cada vez que um no e visitado
(ou seja, tres vezes para um no interno, e uma vez para uma folha).
action, por sua vez, leva tres argumentos. O primeiro e um ponteiro
para o no que esta sendo visitado. O segundo e um inteiro que recebe os
valores preorder, postorder e endorder, dependendo se este e a
primeira, a segundo ou a terceira visita ao no interno, ou leaf se e
uma visita unica a um no-folha. (Estes simbolos sao definidos em
<search.h>.) O terceiro argumento e a profundidade do no, com zero
sendo a raiz.
VALOR DE RETORNO
tsearch retorna um ponteiro para um item encontrado na arvore, ou para
o novo item acrescentado, ou NULL se havia memoria insuficiente para
acrescentar o item. tfind retorna um ponteiro para o item, ou NULL se
nada foi encontrado. Se haviam multiplos elementos que casaram com a
chave, o elemento retornado nao e especificado.
tdelete retorna um ponteiro para o pai do item apagado, ou NULL se o
item nao foi encontrado.
tsearch, tfind, e tdelete tambem retornam NULL se rootp era NULL na
entrada.
ALERTAS
twalk pega um ponteiro para a raiz, enquanto as outras funcoes pegam um
ponteiro para uma variavel que aponta para a raiz.
twalk usa p'os-ordem para dizer "depois da sub-arvore da esquerda, mas
antes da sub-arvore da direita". Algumas autoridades chamariam isto de
"em-ordem", e reservariam "pos-ordem" para dizer "depois de ambas as
sub-arvores".
tdelete libera a memoria requerida para o no na arvore. O usuario e
responsavel para liberar a memoria dos dados correspondentes.
O programa exemplo depende do fato de que twalk nao faz referencia
adicional a um no depois de chamar a funcao de usuario com o argumento
"endorder" ou "leaf". Isto funciona com a implementacao da biblioteca
GNU, mas nao esta na documentacao SysV.
EXEMPLO
O programa a seguir insere doze numeros aleatorios em uma arvore
binaria, e entao imprime os numeros em ordem. Os numeros sao removidos
da arvore e seus armazenamentos sao 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, "memoria 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;
}
CONFORME
SVID
VEJA TAMB'EM
qsort(3), bsearch(3), hsearch(3), lsearch(3)
TRADUZIDO POR LDP-BR EM 03/08/2000
RUBENS DE JESUS NOGUEIRA <darkseid99@usa.net> (traducao) XXXXXX XX
XXXXX XXXXXXXX <xxxxxxxxxx@xxx.xxx> (revisao)