Provided by: manpages-pt-dev_20040726-4_all bug

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)