NOME¶

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 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¶

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 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¶

    #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¶

VEJA TAMBÉM¶

TRADUZIDO POR LDP-BR EM 03/08/2000¶