Árvore Binária Genérica 2ª Parte

No primeiro passo para montar a aplicação através das primitivas apresentadas para árvore binária, cria a estrutura SBINTREE como mostrado a seguir, que será referenciado no código pelo ponteiro BT.

int main(int argc, char *argv[]) {       SBINTREE *BT;       // configura a estrutura de dados da arvore binaria       BT = CreateBinTree(     CreateData,                              DeleteData,                              DuplicatedNode,                              NodeDataCmp,                              PrintData); . . .

                Na lista abaixo de primitivas genéricas, exceto pela rotina CreateBinTree (responsável por iniciar a árvore), todas as rotinas recebem como primeiro parâmetro o endereço (ponteiro BT) da estrutura que abriga os itens pertinentes à árvore.

Primitivas Genéricas:	SBINTREE *CreateBinTree(     void *( * fCreateData )    ( void * ),   BOOL ( * fDeleteData )     ( void * ),           int  ( * fDuplicatedNode ) ( SLINK, SLINK ),   int  ( * fNodeDataCmp )    ( void *, void *),    int  ( * fTraversal )    ( void *, void *, int));
	BOOL AddNode( SBINTREE *, void *);
	BOOL DeleteNode( SBINTREE *, void * );
	SLINK FindNode( SBINTREE *, void * );
	BOOL DestroyBinTree( SBINTREE * );
	BOOL TraversalTree(void *, SBINTREE *, ETRAVERSAL );
	BOOL PrintForest(FILE *, SBINTREE *);

Com a lógica da árvore concluída, basta incluir o tratamento dos especifico dos dados a serem utilizados, as primitivas FindNode, DeleteNode e AddNode precisam saber como comparar dados, pois dependem de tal mecanismo para percorrer a arvore, DeleteNode precisa tratar a liberação de memória do nó e AddNode, precisa saber o quanto reservar de memória como também o que fazer com informação duplicada.

Com isso fica claro entender o porquê das primitivas sempre receber como parâmetro a estrutura SBINTREE, através dela será possível acessar rotinas especificas para o tratamento dos dados.

Por exemplo, a função AddNode(), precisa ser capaz de comparar os dados do nó a ser incluído com o nó que já se encontra na árvore,  para isto, chama a rotina de comparação indicada por fNodeDataCmp em BT, BT é um ponteiro para a estrutura SBINTREE que estamos acessando, portanto, BT->fNodeDataCmp é o atual ponteiro de função. Para chamar a função se utiliza o símbolo * de referencia.

BT = CreateBinTree( CreateData,                            DeleteData,                            DuplicatedNode,                            NodeDataCmp,                            PrintData); . . .        *(BT->fNodeDataCmp)(slkNew, slkCurr);

A sintaxe para chamar a rotina através do ponteiro foi simplificada pelo uso de macro de (*(L->fNodeDataCmp)) para NodeDataCmp. Portanto, ao usar a macro NodeDataCmp(a, b), tem o efeito de chamar a função e passar os argumentos a e b. Todas as rotinas especificas da aplicação seguem esse modelo.

#define CreateData                (*(BT->fCreateData)) #define DeleteData                (*(BT->fDeleteData)) #define DuplicatedNode            (*(BT->fDuplicatedNode)) #define NodeDataCmp               (*(BT->fNodeDataCmp))

Todas as funções que seguem com o destaque em branco, se referem às mascaras criadas pela macro para indicar o momento em que o trabalho dependente do tipo de informação é incluso no código de tratamento da árvore.

PRIVATE SLINK CreateNode(SBINTREE *BT, void *pData) { . . .        // agora chama a aplicacaoh especifica para alocacah de dados        slkNewNode->pData = CreateData(pData); . . . BOOL AddNode(SBINTREE *BT, void *pData) { . . .        slkNew = CreateNode(BT, pData);   // cria o noh . . .              // Decide qual direcaoh seguir              iCompare = NodeDataCmp(slkNew->pData, slkCurr->pData);                   if (iCompare == 0)         // noh duplicado              {                     // o que fazer com noh duplicado                     iAction = DuplicatedNode(slkNew, slkCurr); . . . BOOL DeleteNode( SBINTREE *BT, void *pData ) { . . .        while (slkCurr != NULL &&              (iCompare = NodeDataCmp(slkTmp->pData, slkCurr->pData)))        { . . .        DeleteData(slkDel->pData);        // apaga o dado do noh        free(slkDel);                     // libera a memoria do noh . . . SLINK FindNode( SBINTREE *BT, void *pData ) { . . .        while (slkCurr != NULL &&              (iCompare = NodeDataCmp(slkTmp->pData, slkCurr->pData))) . . .

Toda a parte dependente dos dados fica nos arquivos btapp.h e btapp.c, onde fica declarada que tipo de dados será tratado e como suas rotinas funcionam, para o aplicativo exemplo será utilizado uma estrutura para armazenar uma palavra e um contador de duplicados, serve ao propósito de mostrar o armazenamento e tratamento de copias, além de ser simples de adaptar para outras soluções, portanto no arquivo cabeçalho temos:

// noh consiste em: typedef struct tagSNODEDATA {     char *pWord;           // ponteiros para palavras     unsigned int uCont;    // e a contagem de ocorrencias }SNODEDATA; typedef SNODEDATA *      pND; void *CreateData( void * ); BOOL  DeleteData( void * ); int   DuplicatedNode( SLINK, SLINK ); int   NodeDataCmp( void *, void * ); int   PrintData(FILE *, SLINK, int);

                Todo o trabalho que for necessário para gerenciar e tratar a informação dentro do nó fica no arquivo btapp.c, neste arquivo se encontram todas as rotinas utilizadas pelas primitivas.

                NodeDataCmp deve retornar o resultado da comparação entre dois strings, basta retornar o resultado da comparação dos dados através do da função strcmp.

int NodeDataCmp(void *first, void *second) {     return (strcmp( ((pND) first)->pWord, ((pND) second)->pWord)); }

                DuplicateNode define o tratamento da árvore para dados duplicados, a função deve retornar um dos seguintes valores, zero apagar o nó duplicado ou um inserir o nó duplicado. Neste caso estamos contando as palavras, se uma palavra duplicada é encontrada, incrementa-se o contador e não inclui o dado duplicado.

int DuplicatedNode(SLINK slkNewNode, SLINK slkListNode) {     pND pnd;     // transforma o ponteiro de dados do noh, no da aplicacaoh     pnd = slkListNode->pData;     // adiciona-se uma ocorrencia para a palavra existente     pnd->uCont += 1;     return 0; }

                Todo o processo de adicionar um nó passa por três alocações de memória, na primeira AddNode reserva o nó genérico de uma árvore, que consiste nos ponteiros esquerdo e direito da subarvore, mais um ponteiro genérico para os dados, CreateData irá montar a informação desejada e retornar o endereço para o nó genérico.

SNODE
LEFT	RIGHT
POINTER		à	SNODEDATA
			INT
			POINTER		à	STRING

CreateData aloca memória para a estrutura SNODEDATA que consiste em um ponteiro e um inteiro, e para a string que foi copiada através da rotina _strdup que aloca e copia a informação de apontada por data retornando o endereço para pWord.

void *CreateData(void *data) {     SNODEDATA *pNewData;     // aloca sua estrutura de dados     pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));     if (pNewData == NULL)         return (NULL);     // move os valores para a estrutura de dados     pNewData->uCont = 1;     pNewData->pWord = _strdup((char *) data);     if (pNewData->pWord == NULL)   // erro copiando a string     {         free(pNewData);         return (NULL);     }     else     {         return (pNewData); // retorna o endereco da estrutura     } }

DeleteData tem de lidar com as duas reservas de memória que foram criadas por CreateData, uma para a estrutura SNODEDATA e a outra para a string, neste caso SNODEDATA consiste em: um ponteiro e um inteiro como o ponteiro que indica a string estão armazenados na estrutura apontada por pND, é obrigatório liberar a string antes da estrutura de tipo SNODEDATA.

BOOL  DeleteData(void *data) {        // duas reservas de memoria foram criadas        // uma para a estrutura SNODEDATA,        // outra para a string        // SNODEDATA consiste em: 1 ponteiro e 1 inteiro.        // O inteiro junto do ponteiro retorna para a memoria        // quando a estrutura for liberada        // nescessario liberar a string antes do ponteiro        free( ((pND) data)->pWord );        free(data);        return TRUE; }

                PrintData será utilizada como a função recursiva utilizada pelas rotinas que percorrem e imprimem a árvore, nela quando solicitado, imprime as informações dos dados na saída desejada.

int PrintData(FILE *fOut, SLINK slkNode, int iLevel) {       return fprintf(   fOut,                         "(%i) %s %u",                         iLevel,                         ((pND) slkNode->pData)->pWord,                         ((pND) slkNode->pData)->uCont); }

                Fica assim completa as rotinas de especificas para árvore binária genérica, faltando agora o aplicativo em si, para facilitar o exemplo, nos arquivos btdriver.h e btdriver.c foram incluídas toda a interface com o usuário, assim quando for o núcleo do programa rodar teremos o seguinte código:

int main(int argc, char *argv[]) {        SBINTREE *BT;        // configura a estrutura de dados da arvore binaria        BT = CreateBinTree( CreateData,                                         DeleteData,                                         DuplicatedNode,                                         NodeDataCmp,                                         PrintData);        if (BT == NULL)        {              fprintf(stderr, "Erro criando arvore binaria\n");              exit(EXIT_FAILURE);        }        // controla as opcoes para teste        // na arvore criada        // possui um loop interno que serah finalizado        // quando o usuario escolher a opcaoh        Menu(BT);        // libera toda a memoria utilizada pela arvore binaria        DestroyBinTree(BT);        return (EXIT_SUCCESS); }

                É criada a arvore BT, e passada para a rotina Menu() que irá permitir ao usuário escolher que operações deseja realizar na árvore indicada por BT.

void Menu( SBINTREE *BT )       {       char cTmp[10];       int iChoice;       BOOL bLoop = TRUE;       while (bLoop)       {             printf("\n\n( 1 ) Inserir\n");             printf(    "( 2 ) Apagar\n");             printf(    "( 3 ) Busca\n");             printf(    "( 4 ) Imprime\n");             printf(    "( 5 ) Carrega arquivo\n");             printf(    "( 6 ) Salva\n");             printf(    "( 0 ) Sair\n\n");             Input("Escolha umas das alternativas: " , cTmp, 10);             if ( cTmp[0] != '\0' && (isdigit(*cTmp)) )             {                   iChoice = atoi(cTmp) ;                   switch ( iChoice ) {                         case 1:     Insert(BT);       break;                         case 2:     Delete(BT);       break;                         case 3:     Search(BT);       break;                         case 4:     Display(BT);      break;                         case 5:     LoadFile(BT);     break;                         case 6:     SaveLog(BT);      break;                         case 0:     bLoop = FALSE;    break;                   }             }       } }

                Dentre as rotinas Insert (inserir), Delete (Apagar) e Search (Procurar) serve como chamada para as primitivas da arvore binária.

PRIVATE void Insert( SBINTREE *BT ) {        char strWord[STR_SIZE];        for ( ; ; ) {              Input("Incluir palavra : " , strWord, STR_SIZE );              if ( strWord[0] == '\0' ) break;              // insere na arvore              if (AddNode( BT, strWord ) == FALSE)                     fprintf(stderr, "ERRO! naoh adicionou noh.\n");        } } PRIVATE void Delete( SBINTREE *BT ) {        char strWord[STR_SIZE] ;        Input("Excluir palavra : " , strWord, STR_SIZE );        // apaga        if (DeleteNode( BT, strWord ))              printf("\nNoh removido.");        else              printf("\nNaoh encontrou noh para remover."); } PRIVATE void Search( SBINTREE *BT ) {        char strWord[STR_SIZE] ;        Input("Procurar palavra : " , strWord, STR_SIZE );        // apaga        if (FindNode( BT, strWord ))              printf("\nEncontrou noh.");        else              printf("\nNaoh encontrou noh."); }

                Para as rotinas de Display (Imprime) e SaveLog (Arquivo) usam a rotina que desenha a árvore resultante PrintForest, a diferença fica por conta dos parâmetros de entrada aonde Display utiliza a tela através de stdout e SaveLog passa o arquivo o ponteiro para o arquivo log.txt, como é esperado, stdout direciona a saída para a tela enquanto fLog salva em arquivo.

PRIVATE void Display( SBINTREE *BT ) {        PrintForest(stdout, BT); } PRIVATE void SaveLog( SBINTREE *BT ) {        FILE *fLog;        fLog = fopen("log.txt", "at");        if (fLog)        {              PrintForest(fLog, BT);              fclose(fLog);        }        else              fprintf(stderr, "ERRO AO CRIAR LOG\n"); }

                Por fim, ainda está anexa a possibilidade de utilizar um arquivo texto para adicionar palavras na árvore, semelhante ao utilizado para testar a tabela de dispersão encadeada, a rotina LoadFile (Carrega arquivo) cuida de percorrer a entrada escolhida pelo usuário.

PRIVATE void LoadFile( SBINTREE *BT ) {        FILE *fin;                 // arquivo de entrada        char strWord[STR_SIZE] ;        char *ptrStr;        int iChar;        int i = 0;        Input("Nome do arquivo : " , strWord, STR_SIZE );        fin = fopen(strWord, "rt");        if (fin)        {              // comecah a processar o arquivo              while (!feof(fin))              {                     // percorre pulando espacosh e pontuncaoesh                     do {                            iChar = getc(fin);                     } while ( iChar != EOF &&                           (isspace(iChar) || ispunct(iChar)));                                                      // tendo um caracter valido                     // comecah a montar a palavra                     ptrStr = strWord;                     do {                            *ptrStr++ = iChar;                            iChar = getc(fin);                     } while (    iChar != EOF &&                                   !isspace(iChar) &&                                  !ispunct(iChar) );                     // fim do arquivo, sai do loop                     if (iChar == EOF)                            break;                     // fecha a palavra com o terminador nulo                     *ptrStr = '\0';                     // todos os caracteres em maiuscula                     ptrStr = strupr(strWord);                     // insere na tabela                     AddNode( BT, ptrStr);                     i++;                     if ((i %1000) == 0)                            fprintf(stdout, "Tratou palavras %u\n", i);              }      // while (!feof(fin))              fclose(fin);        } }

                A interface, mesmo sendo em modo texto é bem simples e permite salvar a árvore no arquivo log.txt, o tratamento da rotina faz com que as impressões sejam sempre anexadas no arquivo, assim cada vez que incluir ou excluir dados, peça para salvar a árvore e será possível visualizar a movimentação dos nós dentro da árvore.

( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 1 Incluir palavra : 5 Incluir palavra : 3 Incluir palavra : 1 Incluir palavra : 4 Incluir palavra : 2 Incluir palavra : 0 Incluir palavra : 7 Incluir palavra : 9 Incluir palavra : 6 Incluir palavra : 8 Incluir palavra : ( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 4     +-(2) 9 1     | +-(3) 8 1   +-(1) 7 1   | +-(2) 6 1 +-(0) 5 1   | +-(2) 4 1   +-(1) 3 1     | +-(3) 2 1     +-(2) 1 1       +-(3) 0 1 Total de nohs: 10 Profundidade: 3 ( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 2 Excluir palavra : 5 Noh removido. ( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 4     +-(2) 9 1     | +-(3) 8 1   +-(1) 7 1 +-(0) 6 1   | +-(2) 4 1   +-(1) 3 1     | +-(3) 2 1     +-(2) 1 1       +-(3) 0 1 Total de nohs: 9 Profundidade: 3

Novamente deixo como sugestão para o teste que acesse o Projeto Gutenberg, um esforço voluntário para arquivar e distribuir obras culturais através da digitalização de livros. Nele é possível encontrar obras que estão em domínio publico em vários formatos, para teste utilize a obra de Luis Vaz de Camões, Os Lusíadas cujo arquivo texto pode ser encontrado neste LINK.

Os arquivos do projeto se encontram neste LINK compactados com 7z.