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

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;
           }

CONFORME

       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)