.\" Hey Emacs! This file is -*- nroff -*- source. .\" Copyright 1995 by Jim Van Zandt .\" .\" Permission is granted to make and distribute verbatim copies of this .\" manual provided the copyright notice and this permission notice are .\" preserved on all copies. .\" .\" Permission is granted to copy and distribute modified versions of this .\" manual under the conditions for verbatim copying, provided that the .\" entire resulting derived work is distributed under the terms of a .\" permission notice identical to this one. .\" .\" Since the Linux kernel and libraries are constantly changing, this .\" manual page may be incorrect or out-of-date. The author(s) assume no .\" responsibility for errors or omissions, or for damages resulting from .\" the use of the information contained herein. The author(s) may not .\" have taken the same level of care in the production of this manual, .\" which is licensed free of charge, as they might when working .\" professionally. .\" .\" Formatted or processed versions of this manual, if unaccompanied by .\" the source, must acknowledge the copyright and authors of this work. .\" .TH TSEARCH 3 "24 de setembro de 1995" "GNU" "Manual do Programador Linux" .SH NOME tsearch, tfind, tdelete, twalk \- gerencia uma árvore binária .SH SINOPSE .nf .B #include .sp .BI "void *tsearch (const void *" key ", void **" rootp , .BI " int (*" compar ")(const void *, const void *));" .sp .BI "void *tfind (const void *" key ", const void **" rootp , .BI " int (*" compar ")(const void *, const void *));" .sp .BI "void *tdelete (const void *" key ", void **" rootp , .BI " int (*" compar ")(const void *, const void *));" .sp .BI "void twalk (const void *" root ", void (*" action ") (const void *" nodep , .BI " const VISIT " which , .BI " const int " depth "));" .RE .fi .SH DESCRIÇÃO \fBtsearch\fP, \fBtfind\fP, \fBtwalk\fP, e \fBtdelete\fP 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). \fIcompar\fP 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. .PP \fBtsearch\fP busca um item na árvore. \fIkey\fP aponta para o item a ser buscado. \fIrootp\fP aponta para uma variável que aponta para a raiz da árvore. Se a árvore está vazia, então a variável apontada por \fIrootp\fP deve ser setada para \fBNULL\fP. Se o item é encontrado na árvore, então \fBtsearch\fP retorna um ponteiro para ele. Se não é encontrado, então \fBtsearch\fP o acrescenta, e retorna um ponteiro para o novo item acrescentado. .PP \fBtfind\fP é como \fBtsearch\fP, exceto pelo fato de que, se o item não é encontrado, então \fBtfind\fP retorna \fBNULL\fP. .PP \fBtdelete\fP apaga um item da árvore. Seus argumentos são os mesmos de \fBtsearch\fP. .PP \fBtwalk\fP realiza uma travessia de uma árvore binária por profundidade, da esquerda para a direita. \fIroot\fP aponta para o nó inicial da travessia. Se aquele nó não é a raiz, então apenas parte da árvore será visitada. \fBtwalk\fP chama a função de usuário \fIaction\fP cada vez que um nó é visitado (ou seja, três vezes para um nó interno, e uma vez para uma folha). \fIaction\fP, 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 \fBpreorder\fP, \fBpostorder\fP e \fBendorder\fP, dependendo se este é a primeira, a segundo ou a terceira visita ao nó interno, ou \fBleaf\fP se é uma visita única a um nó-folha. (Estes símbolos são definidos em \fI\fP.) O terceiro argumento é a profundidade do nó, com zero sendo a raiz. .SH "VALOR DE RETORNO" \fBtsearch\fP retorna um ponteiro para um item encontrado na árvore, ou para o novo item acrescentado, ou \fBNULL\fP se havia memória insuficiente para acrescentar o item. \fBtfind\fP retorna um ponteiro para o item, ou \fBNULL\fP se nada foi encontrado. Se haviam múltiplos elementos que casaram com a chave, o elemento retornado não é especificado. .PP \fBtdelete\fP retorna um ponteiro para o pai do item apagado, ou \fBNULL\fP se o item não foi encontrado. .PP \fBtsearch\fP, \fBtfind\fP, e \fBtdelete\fP também retornam \fBNULL\fP se \fIrootp\fP era \fBNULL\fP na entrada. .SH ALERTAS \fBtwalk\fP pega um ponteiro para a raiz, enquanto as outras funções pegam um ponteiro para uma variável que aponta para a raiz. .PP \fBtwalk\fP usa \fBpós-ordem\fP 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". .PP \fBtdelete\fP libera a memória requerida para o nó na árvore. O usuário é responsável para liberar a memória dos dados correspondentes. .PP O programa exemplo depende do fato de que \fBtwalk\fP 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. .SH 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. .sp .nf #include #include #include 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; } .fi .SH "CONFORME" SVID .SH "VEJA TAMBÉM" .BR qsort "(3), " bsearch "(3), " hsearch "(3), " lsearch "(3)" .SH TRADUZIDO POR LDP-BR EM 03/08/2000 \&\fR\&\f(CWRUBENS DE JESUS NOGUEIRA (tradução)\fR \&\fR\&\f(CWXXXXXX XX XXXXX XXXXXXXX (revisão)\fR