Árvore Binária Genérica 1ª Parte

Como feito anteriormente com a lista encadeada e tabela de dispersão, é apresentado aqui uma versão genérica para árvore binária, seguindo o mesmo padrão de dividir o código em rotinas primitivas, dependentes da aplicação e o programa exemplo, recomenda-se ler as postagens sobre noções de árvore, árvore binária, e fica como requisito ler o exemplo de árvore binária da postagem anterior, nas rotinas aqui utilizadas é feita a correção quanto ao uso de globais, mantendo o enfoque sempre em montar módulos.

O arquivo de cabeçalho btgen.h, declara  o tipo nó que simbolizam cada elemento dentro da arvore, cada nó possui um tipo de dado e dois ponteiros usados para apontar para o elemento direito e esquerdo. Tipo de dado usado é o ponteiro void que consiste no ponteiro genérico de C, que permite ser moldado através do operador cast para qualquer tipo de dado sem erros, mais a declaração de SLINK como um tipo ponteiro para o nó.

#define RIGHT     0 #define LEFT      1 //  tipo de dados abstrato arvoreh typedef struct tagSNODE {     struct tagSNODE     *sLink[2];  // ligacaoh das subarvores     void                *pData;     // ponteiro generico de dados } SNODE; // define um tipo ponteiro para o noh typedef SNODE *      SLINK;

Dentro do mesmo cabeçalho se inclui o TAD (tipo abstrato de dado) para árvore binária BINTREE,  temos o contador de nós e apontamentos para rotinas especificas, semelhante a maneira feita para lista encadeada,  a estrutura ainda contem um nó raiz falso (slkDummyRoot) cujo filho direito é a verdadeira raiz da árvore, facilita a lógica de programação das rotinas utilizadas quando o nó raiz tem um pai, vide os problemas relativos a atualizar o nó raiz na postagem anterior que mostrava um exemplo simples de árvore binária.

typedef struct tagSBINTREE {       SLINK             slkDummyRoot;       unsigned int      uiCount;       void *  ( * fCreateData )       ( void * );       BOOL    ( * fDeleteData )       ( void * );       int     ( * fDuplicatedNode )   ( SLINK, SLINK );       int     ( * fNodeDataCmp )      ( void *, void * );       int   iMaxDepth;       char  *pPath;       int   ( * fTraversal )      ( void *, void *, int ); } SBINTREE;

Por mais abrangente e genérica que se possa criar uma função, a árvore binária genérica consegue manipular apenas as conexões do nó, esse tipo de operação não precisa saber como os dados se parecem, restando quatro tipos de operações que manipulam os dados diretamente e dependem do tipo definido. Criar, apagar, comparar e tratar duplicado são funções que fazem parte do arquivo btapp.c de rotinas especificas da aplicação e passam a integrar a estrutura de dados lista através dos ponteiros da estrutura mostrada acima.

Foi incluído ainda para parte especifica uma rotina de travessia para os algoritmos de percorrer a árvore recursivamente, junto de um indicador da profundidade MaxDepth e o ponteiro pPath para indicar a percurso , um exemplo de seu uso pode ser visto na rotina PrintForest que imprime a árvore resultante  para auxilio de testes, o uso desta rotina pode ser descartado.

FUNÇÕES ESPECIFICAS PARA ÁRVORE BINÁRIA
Nome	Descrição
fCreateData	Recebe um ponteiro do objeto definido para a aplicação, espera-se o retorno de um ponteiro para o que venha a ser o dado armazenado na lista.
fDeleteData	Recebe um ponteiro do objeto definido para a aplicação que deve estar armazenado na lista ligada. fDeleteData deve destruir o objeto
fDuplicateNode	São passados dois ponteiros. O primeiro ponteiro é o nó que deve ser adicionado e o segundo é o nó que já se encontra na lista, mas que é igual(duplicada) a informação do primeiro ponteiro, retornando:   0 -> destruir duplicada                   1 -> adicionar duplicada
fNodeDataCmp	São passados dois ponteiros do objeto definido para o dado e deve compara-lo, retornando um numero que é < 0, zero, ou > 0, dependendo da relação entre o primeiro e segundo objeto.
fTraversal	São passados dois ponteiros, um para saída de dados e outro com a entrada de dados, e a indicação de em que nível a rotina se encontra.

Para permitir maior legibilidade foram feitas as seguintes redefinições:

#define BTRoot               (BT->slkDummyRoot) #define NodeCount            (BT->uiCount) #define CreateData           (*(BT->fCreateData)) #define DeleteData           (*(BT->fDeleteData)) #define DuplicatedNode       (*(BT->fDuplicatedNode)) #define NodeDataCmp          (*(BT->fNodeDataCmp)) #define Path                 (BT->pPath) #define MaxDepth             (BT->iMaxDepth) #define Traversal            (*(BT->fTraversal))

As rotinas abaixo fazem parte das primitivas genéricas para árvore binária, tais funções manipulam somente as ligações do nó, sendo completamente independentes da aplicação e não devem ser alteradas.

Função	CreateBinTree
Propósito	Cria e inicia uma estrutura de gerenciamento de uma árvore binária
Parâmetros	ponteiro para as funções especifica da lista void *(*fCreateData)(void *) cria dado int   (*fDeleteData)(void *) apaga dado int   (*fDuplicatedNode)(SLINK, SLINK) tratar dado duplicado. int   (*fNodeDataCmp)(void *, void *)  compara nós int   (*fTraversal)( void *, void *, int) percorre a arvore
Retorno	ponteiro SBINTREE        pBT  - ponteiro para uma estrutura do tipo árvore binária inicializada        NULL - não conseguiu criar a árvore binária
Descrição	Cria uma estrutura de árvore binária e retorna um ponteiro da mesma. Em erro, retorna NULL.Esta função aceita ponteiros para as cinco funções especificas de uma árvore e inicializa a estrutura com elas, aloca o nó que irá apontar para a raiz da árvore.

SBINTREE *CreateBinTree(          void * ( * fCreateData )          ( void * ),        BOOL   ( * fDeleteData )          ( void * ),        int    ( * fDuplicatedNode )      ( SLINK, SLINK ),        int    ( * fNodeDataCmp )         ( void *, void *),        int    ( * fTraversal )           ( void *, void *, int)) {        SBINTREE *pBT;        // aloca uma estrutura que gerencia uma arvore binaria        pBT = (SBINTREE *) malloc(sizeof(SBINTREE));        if (pBT) {   //  caso fracasse em alocar memoria              // tendo alocado, inicializa as variaveis              pBT->slkDummyRoot = (SLINK) malloc(sizeof(SNODE));              // naoh criou o noh raiz falso              if (pBT->slkDummyRoot == NULL) {                     // libera a estrutura de dados arvore                     free(pBT);                     return (NULL);      // indicando o erro              }              // tendo sucesso na alocacaoh, inicializa as variaveis              pBT->slkDummyRoot->sLink[RIGHT] = NULL;              pBT->slkDummyRoot->sLink[LEFT]  = NULL;              pBT->slkDummyRoot->pData = NULL;              pBT->uiCount = 0;               // funcoesh especificas p/ tratamento da arvore              pBT->fCreateData = fCreateData;              pBT->fDeleteData = fDeleteData;              pBT->fDuplicatedNode = fDuplicatedNode;              pBT->fNodeDataCmp = fNodeDataCmp;              pBT->fTraversal = fTraversal;              return (pBT);            // devolve o enderecoh        }        else   //  caso fracasse em alocar memoria              return NULL; // retorna a indicacaoh }

Função	DestroyBinTree
Propósito	Libera toda a memória de uma arvore binária previamente criada
Parâmetros	SBINTREE *BT -> Árvore a ser destruída
Retorno	TRUE - memória da estrutura da arvore e todos os nós liberados FALSE - árvore inválida
Descrição	Ponto de entrada para a rotinas de travessia recursiva, executa a rotina DelTree para eliminar nós individualmente, terminado o processo de atravessar e liberar os nós, libera o nó raiz falso e a estrutura de dados que gerencia a arvore.

BOOL DestroyBinTree( SBINTREE *BT ) {        if (BT) {              // percorre a arvore em pos ordem,              // apagando cada noh              DelTree(BT, BTRoot->sLink[RIGHT] );              // libera a raiz falsa              free(BT->slkDummyRoot);              // libera a estrutura arvore              free(BT);              return TRUE;        }        else              return FALSE; }

Função	DelTree
Propósito	Libera nós de uma arvore binária em pós-ordem
Parâmetros	SBINTREE *BT -> estrutura de dados da arvore c/ a rotina de exclusão do nó SLINK slk -> nó atual da arvore sendo percorrida recursivamente
Retorno	Nenhum
Descrição	Acessa os nós da árvore em sequencia pós-ordenada, eliminando o nó da posição atual, por ser uma travessia pós-ordenada, o nó liberado  não será referenciado novamente durante o resto do percurso

void DelTree( SBINTREE *BT, SLINK slk ) {        if (slk) {              DelTree(BT, slk->sLink[LEFT]);              DelTree(BT, slk->sLink[RIGHT]);              DeleteData(slk->pData);    // apaga o dado do noh              free(slk);                 // libera a memoria do noh              --NodeCount;               // subtrai o noh do total        } }

Busca

A rotina de busca se inicia a partir de um nó e procura pela incidência desejada, encerra ao encontrar, do contrario, continua a esquerda se for menor que o nó atual,  ou a direita se maior, no código abaixo se faz uso da vantagem de utilizar um vetor de dois ponteiros para os filhos onde o valor de comparação iCompare decide qual direção prosseguir através da variável iDir.

Função	FindNode
Propósito	Encontra um nó da árvore binária
Parâmetros	SBINTREE *BT -> ponteiro para estrutura de dados que trata a arvore com a função para comparação de dados void *pData -> informação que devera ser encontrada na árvore
Retorno	slkCurr - ponteiro para o nó NULL    - não encontrou um nó equivalente
Descrição	Realiza uma formatação nos dados apontados por pData, para poder realizar a comparação necessária durante o percurso de busca do nó equivalente.

SLINK FindNode( SBINTREE *BT, void *pData ) {        SLINK slkTmp;       // noh temporario com o dado de busca        SLINK slkCurr;      // posicao atual na arvore        int iCompare;       // resultado da comparacaoh        int iDir;           // seguir direita/esquerda        // formata os dados dentro do noh temporario        slkTmp = CreateNode(BT, pData);        if (slkTmp == NULL) // naoh conseguiu alocar o noh              return NULL; // retorna indicando fracasso        // inicia com o noh falso da raiz        slkCurr = BTRoot->sLink[RIGHT];          // desce a arvoreh em busca de uma ramo vazio.        while (slkCurr != NULL &&        (iCompare = NodeDataCmp(slkTmp->pData, slkCurr->pData)))        {              // corrige -1 e 0(<=) para 1(LEFT) e 1(>) para 0(RIGHT)              iDir = iCompare < 0;              slkCurr = slkCurr->sLink[iDir];   // atualiza atual        }        // apaga o dado do noh        DeleteData(slkTmp->pData);        // libera a memoria do noh temporario        free(slkTmp);        return slkCurr; }

Inserir Nó

Inserção de nó é simples, basta descer a árvore como se estivesse procurando o nó que se deseja adicionar, quando encontrar um nó sem filhos, isto é, nó NULO, insere o novo nó como filho do ultimo nó, aqui temos um dos motivos pelo qual se declarou um nó pai (BT->slkDummyRoot) para a raiz da árvore.

Função	CreateNode
Propósito	Criar um nó para a árvore binária
Parâmetros	SBINTREE *BT -> estrutura árvore c/ ponteiro para a função CreateData void *data -> ponteiro genérico c/ o dado do nó
Retorno	slkNewNode - ponteiro para uma estrutura do tipo nó NULL - não conseguiu criar um nó
Descrição	Cria um nó e então chama a função especifica da aplicação CreateData() para criar o dado da estrutura do nó. Em caso de falha retorna NULO

PRIVATE SLINK CreateNode(SBINTREE *BT, void *pData) {        SLINK slkNewNode;        // aloca os ponteiros para seguinte, anterior e dado para o noh        slkNewNode = (SLINK) malloc(sizeof(SNODE));        if (slkNewNode == NULL) // caso fracasse em alocar memoria              return (NULL);   // retorna indicacaoh de NULO        // tendo sucesso na alocacaoh, inicializa as variaveis        slkNewNode->sLink[RIGHT] = NULL;        slkNewNode->sLink[LEFT]  = NULL;        // agora chama a aplicacaoh especifica para alocacah de dados        slkNewNode->pData = CreateData(pData);        // caso naoh consiga alocar memoria para o dado do noh        if (slkNewNode->pData == NULL) {              free(slkNewNode); // libera a memoria previamente alocada              return (NULL);    // retorna NULO para indicar falha        }        // alocou toda a memoria nescessaria        else {              return (slkNewNode);    // retorna o noh criado        } }

Função	AddNode
Propósito	Adiciona um nó na árvore
Parâmetros	SBINTREE *BT  -> ponteiro para estrutura de dados que trata a arvore c/ ponteiros paras funções de comparação e tratamento de duplicados void *pData -> nó a ser inserido na árvore
Retorno	TRUE  - adicionou na lista o nó, caso seja duplicata, remove, adiciona ou ignora, depende da configuração da árvore FALSE - não conseguiu criar um nó para inserir na arvore
Descrição	Adiciona um nó numa árvore binária

BOOL AddNode(SBINTREE *BT, void *pData) {        SLINK slkNew;       // aponta para o noh a ser inserido na lista        SLINK slkPrev;      // link anterior da lista durante a busca        SLINK slkCurr;      // link atual da lista durante a busca        int iAction;        // acaoh em caso de nohs duplicados        int iCompare;       // resultado da comparacaoh        int iDir;           // seguir direita/esquerda        slkNew = CreateNode(BT, pData);   // cria o noh        if (slkNew == NULL)               // naoh alocou o noh              return FALSE;              // indica fracasso        // ignora o tratamento especial que se        // faz para a raiz da arvoreh        // utiliza um noh falso como raiz da arvore        // e passa a tratar o noh inicial(raiz)        // como um noh igual aos demais        // simplificando a logica de tratamento        slkPrev = BTRoot;        // a raiz falsa utiliza apenas a ramificacaoh direita        iDir = RIGHT;        // igual ao slkCurr = BTRoot->sLink[RIGHT]        slkCurr = slkPrev->sLink[RIGHT];         // desce a arvoreh em busca de uma ramo vazio.        while (slkCurr != NULL)        {              // avanca a posicaoh 1 - atualiza anterior              slkPrev = slkCurr;              // 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);                     // fDuplicateNode retorna:                     //     1 -> adicionar duplicada                     if (iAction)                     {                            // nada faz                     }                     // fDuplicateNode retorna:                     //     0 -> destruir duplicada                     else //      if (iAction == 0)                     {                            // naoh inclui o duplicado                            // apagamos os dados que dependem da                            // da implementacaoh do objeto                            DeleteData(slkNew->pData);                            // desalocamos o noh                            free(slkNew);                                                return FALSE;                     }              }              // comparacaoh retorna -1(menor), 0(igual) e 1(maior)              iDir = iCompare < 0;                                        // corrige <= (-1 e 0) para 1(LEFT) e >(1) para 0(RIGHT)              // avanca a posicaoh 2 - atualiza atual               slkCurr = slkCurr->sLink[iDir];                }        // adiciona novo noh        slkPrev->sLink[iDir] = slkNew;        // soma o novo noh no total        ++NodeCount;        return TRUE; }

Excluir nó

Dentre as 3 primitivas básicas (Inserir, excluir e procurar), excluir apresenta maior complexidade devido a necessidade de manter os nós respeitando a posição relativa entre eles, mantendo a chave de ordenação, como feito para inserir, desce a arvore procurando o nó que se deseja apagar.

O modelo de exclusão do nó mostrado anteriormente era simplificado e tinha fim didático, substituindo o nó a ser eliminado pelo elemento compatível mais próximo, para este código de exclusão,  o remanejamento dos nós mantém balanceamento da árvore, ideal para manter as operações de busca eficientes, tratando os três possíveis casos:

1. Não tem filhos direito, substitui com o filhos esquerdo, atende também quando não tem ambos os filhos.

2. Filho direito não tem descendente esquerdo, substitui o nó pai com o filho direito e coloca o nó irmão esquerdo como filho esquerdo

3. Pior caso, nó a ser excluído tem os dois filhos, coloca em seu lugar pelo menor nó da ramificação direita, ou seja, substitui o nó pai pelo  menor descendente  do filho direito,  a busca é feita sempre seguindo a subárvore esquerda, por ser o menor não terá filho esquerdo, caso o menor tenha um filho direito, este assume sua posição.

Função	DeleteNode
Propósito	Apaga um nó da árvore binária
Parâmetros	SBINTREE *BT -> ponteiro para estrutura de dados que trata a arvore c/ ponteiros paras funções de comparação e excluir dados void *pData -> informação que devera ser excluída da árvore
Retorno	TRUE  - exclui o nó e atualizou a arvore FALSE - não encontrou um nó equivalente p/ exclusão
Descrição	Apaga um nó que tenha os dados indicado por pData.Verifica se o nó se encontra na arvore, Elimina o nó e atualiza a referencia aos demais nós.

BOOL DeleteNode( SBINTREE *BT, void *pData ) {        SLINK slkTmp;       // noh temporario com o dado de busca        SLINK slkPrev;      // posicao anterior na arvore        SLINK slkCurr;      // posicao atual na arvore        SLINK slkDel;       // noh da arvore a ser excluido        int iCompare;       // resultado da comparacaoh entre dois nohs        int iDir;           // seguir direita/esquerda        slkTmp = CreateNode(BT, pData);   // formata noh tmp        if (slkTmp == NULL)        // naoh conseguiu alocar o noh              return FALSE;       // retorna indicando fracasso        // inicia com o noh falso da raiz        slkPrev = BTRoot;        iDir = RIGHT;       // a raiz falsa utiliza ramo direito        slkCurr = slkPrev->sLink[RIGHT];         // desce a arvoreh em busca de uma ramo vazio.        while (slkCurr != NULL &&              (iCompare = NodeDataCmp(slkTmp->pData, slkCurr->pData)))        {              // comparacaoh retorna -1(menor), 0(igual) e 1(maior)              iDir = iCompare < 0;                    // corrige <= (-1 e 0) para 1(LEFT) e >(1) para 0(RIGHT)              slkPrev = slkCurr;                // atualiza anterior              slkCurr = slkCurr->sLink[iDir];   // atualiza atual        }        DeleteData(slkTmp->pData); // apaga o dado do noh        free(slkTmp);              // libera o noh temporario        if (slkCurr == NULL)    // naoh encontrou o noh        return FALSE;        // salva a posicaoh do noh a ser excluido        slkDel = slkCurr;        // primeiro caso        if (slkCurr->sLink[RIGHT] == NULL)        {              slkCurr = slkCurr->sLink[LEFT];        }        // segundo caso        else if (slkCurr->sLink[RIGHT]->sLink[LEFT] == NULL)        {              slkCurr = slkCurr->sLink[RIGHT];              slkCurr->sLink[LEFT] = slkDel->sLink[LEFT];        }        // ultimo caso        else {              // aponta para o pai do menor noh esquerdo              SLINK slkSmallFather;              // procura o menor noh              slkSmallFather = slkCurr->sLink[RIGHT];              while (slkSmallFather->sLink[LEFT]->sLink[LEFT])                     slkSmallFather = slkSmallFather->sLink[LEFT];              //  aponta para o menor noh da ramificacaoh              // 'slkCurr' ira ocupar a posicaoh do noh a ser              // excluido              slkCurr = slkSmallFather->sLink[LEFT];              // o neto direito substitui a posicaoh do filho              slkSmallFather->sLink[LEFT] = slkCurr->sLink[RIGHT];              // coloca a referencia dos filhos do noh a ser excluido              // no noh que irah substitui-lo.              slkCurr->sLink[LEFT] = slkDel->sLink[LEFT];                        slkCurr->sLink[RIGHT] = slkDel->sLink[RIGHT];        }        // atualiza a informacaoh do pai do noh excluido        slkPrev->sLink[iDir] = slkCurr;        DeleteData(slkDel->pData); // apaga o dado do noh        free(slkDel);              // libera a memoria do noh        --NodeCount;               // subtrai o noh do total        return TRUE; }

Travessia

Graças a topologia da árvore binária, uma importante característica é a ordem de travessia, frequentemente surgirá a necessidade de visitar todos os nós em uma árvore, assegurando que cada nó somente será acessado uma única vez e de forma consistente, existem três maneiras de percorrer uma árvore, todas recursivas, pré-ordem, ordem e pós-ordem, de grande importância compreender que visitar um filho implica em recursivamente visitar todos os seus descendentes, mesmo tendo definições simples, todas as três travessias asseguram visitar todos os nós na árvore e podem ser utilizadas para diversos propósitos em diferentes ocasiões.

Função	TraversalTree
Propósito	Percorrer uma arvore binária executando rotinas em ordem especifica
Parâmetros	void *pOut -> aponta a saída dos dados, usada pela função que percorre a arvore SBINTREE *BT -> Árvore a ser atravessada e rotina de travessia ETRAVERSAL eType -> tipo de travessia, ordenada, pós-ordenada ou pré-ordenada
Retorno	TRUE - Travessia de árvore completada FALSE - Arvore vazia
Descrição	Ponto de entrada para as rotinas ( InOrder, PreOrder e PostOrder )de travessia recursivas.

typedef enum tagETRAVERSAL {        INORDER,        PREORDER,        POSTORDER } ETRAVERSAL; . . . BOOL TraversalTree(void *pOut, SBINTREE *BT, ETRAVERSAL eType ) {        if (BTRoot->sLink[RIGHT]) {              switch (eType) {                  default:                  case INORDER:                       InOrder(pOut, BT, BTRoot->sLink[RIGHT], 0);                          break;                  case PREORDER:                            PreOrder(pOut, BT, BTRoot->sLink[RIGHT], 0);                         break;                  case POSTORDER:                           PostOrder(pOut, BT, BTRoot->sLink[RIGHT], 0);                        break;              }              return TRUE;        }        else              return FALSE; }

Funções	InOrder PreOrder PostOrder
Propósito	Percorrer uma arvore binária em sequência pré-ordenada,  ordenada ou em pós-ordem.
Parâmetros	void *pOut -> aponta a saída dos dados, usada pela função que percorre a arvore SBINTREE *BT -> estrutura de dados da arvore c/ a rotina de travessia SLINK slk -> nó atual da arvore sendo percorrida recursivamente   int iLevel -> profundidade na arvore em que a rotina se encontra
Retorno	Nenhum
Descrição	Acessa os nós da árvore recursivamente em sequencia ordenada,  pré-ordenada ou pós-ordenada, executando a rotina  apontada por fTraversal para tratar o nó

void InOrder(void *pOut, SBINTREE *BT, SLINK slk, int iLevel) {        if (slk) {              InOrder(pOut, BT, slk->sLink[LEFT], iLevel + 1);              Traversal(pOut, slk, iLevel);              InOrder(pOut, BT, slk->sLink[RIGHT], iLevel + 1);        } } void PreOrder(void *pOut, SBINTREE *BT, SLINK slk, int iLevel) {        if (slk) {              Traversal(pOut, slk, iLevel);              PreOrder(pOut, BT, slk->sLink[LEFT], iLevel + 1);              PreOrder(pOut, BT, slk->sLink[RIGHT], iLevel + 1);        } } void PostOrder(void *pOut, SBINTREE *BT, SLINK slk, int iLevel) {        if (slk) {              PostOrder(pOut, BT, slk->sLink[LEFT], iLevel + 1);              PostOrder(pOut, BT, slk->sLink[RIGHT], iLevel + 1);              Traversal(pOut, slk, iLevel);        } }

Gráfico

                Um aspecto interessante da árvore é poder visualizar e conseguir observar como as operações de adicionar e apagar altera o formato da mesma, em termos práticos, dificilmente uma aplicação terá utilidade com a impressão da árvore que não se seja para testes e validações.

                As rotinas de impressão apresentada abaixo, servem apenas para mostrar toda a ramificação de uma árvore criada, peço tolerância quanto a qualidade visual, uma vez que para manter o código estritamente no padrão C, sem o uso de bibliotecas de terceiros, foi utilizada a saída através do console, que implica em desenhar uma árvore usando caracteres e imprimindo uma linha por vez de forma lateral.

Função	PrintForest
Propósito	Imprime em um arquivo de saída a árvore resultante
Parâmetros	FILE *fOut -> arquivo em que a árvore será impressa. SBINTREE *BT -> Árvore a ser desenhada                 Path - buffer com o caminho percorrido pela função recursiva                 MaxDepth - indica a profundidade(altura) da arvore impressa
Retorno	TRUE - Impressão concluída FALSE - Árvore vazia
Descrição	Ponto de entrada para a rotina de impressão recursiva, reserva um buffer para manter registro do caminho percorrido pela função, inicia a variável de profundidade da árvore.

BOOL PrintForest(FILE *fOut, SBINTREE *BT) {        if (BTRoot->sLink[RIGHT])        {              // impossivel saber a altura da arvore              // aloca esperando o pior caso              Path = malloc(NodeCount);              if (Path)              {                     // comecah no nivel 0, logo profundidade 0                     MaxDepth = 0;                     PrintTree(fOut, BT, BTRoot->sLink[RIGHT], 0);                      // naoh mais necessarioh, libera                     free(Path);                     // informacoesh da arvore                     fprintf(fOut, "\nTotal de nohs: %u\n", NodeCount);                     fprintf(fOut, "Profundidade: %u\n", MaxDepth);                     return TRUE;              }        }        else {              fprintf(fOut, "Arvoreh vazia\n");        }        return FALSE; }

Função	PrintTree
Propósito	Imprime o nó da árvore e linhas de ramificação
Parâmetros	FILE *fOut -> arquivo em que a árvore será impressa. SBINTREE *BT -> Árvore a ser desenhada                 Path - buffer com o caminho percorrido pela função recursiva                 MaxDepth - indica a profundidade(altura) da arvore impressa SLINK slk -> nó atual da arvore sendo percorrida recursivamente int iLevel -> profundidade na árvore em que a rotina se encontra
Retorno	Nenhum
Descrição	Acessa os nós da árvore em sequência ordenada da direita para a esquerda, durante a impressão da nó na linha, verifica as ramificações anteriores através do buffer Path, sempre que ocorre desvio da esquerda p/ direita ou vice-versa, deve incluir '|' como indicação de linha horizontal de uma ramificação.

void PrintTree(FILE *fLog, SBINTREE *BT, SLINK slk, int iLevel) {        if (slk)        {              // verifica a profundidade da arvore              if (iLevel > MaxDepth)                     MaxDepth = iLevel;              // Segue a ramificacaoh direita              Path[iLevel] = 'R';              PrintTree(fLog, BT, slk->sLink[RIGHT], iLevel + 1);              // imprime o noh atual              {                     char *pDraw;                     int iX;                     // aloca o tamanho necessario para                     // montar a linha ser desenhada                     // utiliza memoria do heap ao inves da pilha(stack)                     pDraw = malloc(iLevel * 2 + 3);                     if (pDraw)                     {                            pDraw[0] = ' ';                            pDraw[1] = ' ';                            for (iX = 1; iX < iLevel; ++iX)                            {                                   // ex: Path = RRRRLRRRL                                   // sequencia RL(direita/esquerda)                                   // OU LF(esquerda/direita)                                   if (Path[iX-1] != Path[iX])                                   {                                         // desenha linha horizontal de                                         // uma ramificacaoh anterior                                         pDraw[iX * 2    ] = '|';                                         pDraw[iX * 2 + 1] = ' ';                                   }                                   // sequencia LL(esquerda/esquerda)                                   // ou RR(direita/direita)                                   else                                   {                                         // naoh tem linha de                                         // ramificaoh acima                                         pDraw[iX * 2    ] = ' ';                                         pDraw[iX * 2 + 1] = ' ';                                   }                            }                            // desenha o noh na linha atual                            pDraw[iLevel * 2    ] = '+';                            pDraw[iLevel * 2 + 1] = '-';                            pDraw[iLevel * 2 + 2] = '\0';                            fprintf(fLog, pDraw);                            free(pDraw);                     }              }              Traversal(fLog, slk, iLevel);              fprintf(fLog, "\n");              // Segue ramificacaoh esquerda              Path[iLevel] = 'L';              PrintTree(fLog, BT, slk->sLink[LEFT], iLevel + 1);        } }

                Mais uma vez tenho de dividir o assunto em duas partes devido a extensão, na próxima postagem todas as primitivas aqui apresentadas serão utilizadas em um aplicativo exemplo.

Exemplo de Árvore Binária

Tendo a introdução à árvore e o conceito de árvore binária apresentados nas postagens anteriores, adiciona agora uma implementação, para o exemplo será incluído um código bastante simplificado e que faz uso de variáveis globais para diminuir o numero de redirecionamentos dos ponteiros e permitir uma fácil legibilidade, relembrando que sempre se deve evitar está pobre pratica de programação, entretanto para pequenos programas didáticos se podem tolerar a escolha aqui feita, futuramente será apresentada um modelo completo de árvore binária genérica da mesma forma que foi apresentada lista encadeada.

Semelhante a uma lista ligada a declaração do nó que será utilizado na árvore binária consiste em dois ponteiros para outros nós, mais a informação a ser armazenada junto ao nó.

NÓ INFORMAÇÃO
PONTEIRO ESQUERDO	PONTEIRO DIREITO

A declaração no código da estrutura pode seguir o seguinte e mais comum modelo:

typedef struct tagSTREENODE {        char cData;        struct tagSTREENODE *sRight;        struct tagSTREENODE *sLeft; } STREENODE;

Entretanto, a opção escolhida para representar utiliza uma pequena variação em relação ao modelo apresentado acima, que também fornece dois ponteiros para os nós através de um vetor.

#define RIGHT 0 #define LEFT 1 typedef struct tagSTREENODE {        char cData;        struct tagSTREENODE *sLink[2]; } STREENODE;

Esta declaração de nó com vetor será utilizado nos demais exemplos de árvore binária a serem publicados, apesar de parecer no momento uma afetação desnecessária que aumenta o tamanho da declaração, quando forem incluídas as rotinas de balanceamento de árvore, ficará visível o motivo da escolha, por enquanto considere as duas formas abaixo como equivalente:

pTree->sLink[RIGHT] = NULL;       // variavel c/ vetor pTree->sRight = NULL;             // declaracaoh comum

INCLUIR NÓ

Uma árvore não precisa ser ordenado, como alguns casos podem exigir, e sua implementação depende da forma em que está árvore será percorrida, o exemplo apresentado assume a forma ordenada, com a subárvore da esquerda contendo nó menor que a raiz e o da direita maior ou igual à raiz.

INFO

< INFO

>= INFO

Antes de mostrar como é feita a inserção de um nó na árvore, será apresentada uma rotina que procura a posição de um dado na árvore binária ordenada, apesar de não ser utilizada no código final, a seguinte função permite compreender como percorrer uma árvore recursivamente, caso tenha duvidas quanto à recursividade, siga o link para a postagem que trata do assunto.

void Find(STREENODE *pSubTree, char cData) {        if (cData < pSubTree->cData)              Find(pSubTree->sLink[LEFT], cData);        else if (cData > pSubTree->cData)              Find(pSubTree->sLink[RIGHT], cData);        else              printf("Achou"); }

Uma vez tenha compreendido o mecanismo de busca pela posição desejada, o próximo passo no esboço da rotina que irá incluir um nó, consiste em descer a árvore até encontrar um subárvore vazia.

void InsTree(STREENODE *pSubTree, char cData) {        if (pSubTree == NULL) { // encontrou a posicao              // subarvore naoh foi criada, aloca o noh              pSubTree = (STREENODE *) malloc(sizeof(STREENODE));              // carrega os dados              pSubTree->sLink[RIGHT] = NULL;              pSubTree->sLink[LEFT] = NULL;              pSubTree->cData = cData;        }        // pesquisa binariah        if (cData < pSubTree->cData)              InsTree(pSubTree->sLink[LEFT], cData);        else              InsTree(pSubTree->sLink[RIGHT], cData); }

Este primeiro esboço encontra a posição desejada e inicializar o novo nó da árvore, falta apenas uma atualizar o apontamento esquerdo ou direito do nó pai, para isso tem que incluir além do nó filho, também o nó pai, resultando em:

void InsTree(STREENODE *pTree, STREENODE *pSubTree, char cData) {        if (pSubTree == NULL)      {              pSubTree = (STREENODE *) malloc(sizeof(STREENODE));              pSubTree->sLink[RIGHT] = NULL;              pSubTree->sLink[LEFT] = NULL;              pSubTree->cData = cData;              // pega a noh pai              // e atualiza o ponteiro para o novo filho              if (cData < pTree->cData)                     pTree->sLink[LEFT] = pSubTree;              else                     pTree->sLink[RIGHT] = pSubTree;        } . . .

Para usar tal função será preciso uma variável global que contenha a referencia a raiz da árvore, essa variável deve ser inicializada com NULL e um ponteiro da raiz será definido na primeira chamada a InsTree.

STREENODE *stROOT = NULL;  // raiz como global . . .        stROOT = InsTree(stROOT, stROOT, ); . . .

O resultado final da rotina ainda inclui a inicialização da raiz da árvore caso a mesma esteja vazia, com isto a função quando executada com a árvore vazia, retornará o endereço para atualizar o nó raiz, chamadas subsequentes não precisam redefinir a raiz.

STREENODE *InsTree(STREENODE *pTree, STREENODE *pSubTree, char cData) {        if (pSubTree == NULL) {              pSubTree = (STREENODE *) malloc(sizeof(STREENODE));              pSubTree->sLink[RIGHT] = NULL;              pSubTree->sLink[LEFT] = NULL;              pSubTree->cData = cData;              // arvore vazia ? entaoh inicia              if (pTree == NULL)                     return pSubTree; . . .

EXCLUIR NÓ

Para apagar um nó da árvore exige um processo mais trabalhoso, que necessita verificar cada situação possível:

1)      Remover um nó folha: o caso mais simples, basta atualizar o nó pai para nulo.

2)      Remover nó que tem um filho: o nó pai aponta para o descendente

3)      Remover um nó com dois filhos:

a.       Nó filho da subárvore direita ocupa a posição do nó pai.

b.      Toda a ramificação esquerda será referenciada pela primeira subárvore esquerda livre da subárvore direita.

O processo de rearranjar os ponteiros leva a um novo algoritmo recursivo semelhante ao de inclusão para percorrer, ao encontrar o elemento a ser excluído deverá tratar cada possível caso.

STREENODE *DelTree(STREENODE *pTree, char cData) { . . .        if (pTree->cData == cData)        {              // eh uma folha              if (pTree->sLink[LEFT] == NULL &&                     pTree->sLink[RIGHT] == NULL)              {                     free(pTree);                     return NULL;              }              // subarvore esquerda nula              else if (pTree->sLink[LEFT] == NULL)              {                     sTmp = pTree->sLink[RIGHT];                     free(pTree);                     return sTmp;              }              // subarvore direita nula              else if (pTree->sLink[RIGHT] == NULL)              {                     sTmp = pTree->sLink[LEFT];                     free(pTree);                     return sTmp;              }              // ambas subarvores presentes              else              {                     sTmp = pTree->sLink[RIGHT];                     sTraverse = pTree->sLink[RIGHT];                     while (sTraverse->sLink[LEFT])                            sTraverse = sTraverse->sLink[LEFT];                     sTraverse->sLink[LEFT] = pTree->sLink[LEFT];                     free(pTree);                     return sTmp;              }        } . . .

Como feito anteriormente, deve-se atualizar o ponteiro global para a raiz da árvore, caso seja justamente ele o nó a ser excluído, bastando utilizar o valor de retorno de DelTree.

                PERCORRER A ÁRVORE

                Para atravessar a árvore de forma ordenada, pré-ordenada e pós-ordenada foram incluídas tais rotinas, junto de outra que irá apresentar a árvore resultante de forma lateral, todo o código de impressão é visto a seguir junto do programa completo.

                Ao executar o programa, a interface fornece toda a descrição para criar, apagar e visualizar a árvore binária resultante.

Inserir  ( 1 ) Apagar   ( 2 ) Listar   ( 3 ) Sair     ( 0 ) Escolha umas das alternativas anteriores : 1 Digite o caractere : 5 Digite o caractere : 3 Digite o caractere : 1 Digite o caractere : 4 Digite o caractere : 2 Digite o caractere : 0 Digite o caractere : 7 Digite o caractere : 9 Digite o caractere : 6 Digite o caractere : 8 Digite o caractere : Inserir  ( 1 ) Apagar   ( 2 ) Listar   ( 3 ) Sair     ( 0 ) Escolha umas das alternativas anteriores : 3       9          8    7       6 5       4    3          2       1          0 Ordem    : 0 1 2 3 4 5 6 7 8 9 Pre-Ordem: 5 3 1 0 2 4 7 6 9 8 Pos-Ordem: 0 2 1 4 3 6 8 9 7 5 Inserir  ( 1 ) Apagar   ( 2 ) Listar   ( 3 ) Sair     ( 0 ) Escolha umas das alternativas anteriores : 2 Digite o caractere que deseja excluir da arvore : 3 Inserir  ( 1 ) Apagar   ( 2 ) Listar   ( 3 ) Sair     ( 0 ) Escolha umas das alternativas anteriores : 3       9          8    7       6 5    4          2       1          0 Ordem    : 0 1 2 4 5 6 7 8 9 Pre-Ordem: 5 4 1 0 2 7 6 9 8 Pos-Ordem: 0 2 1 4 6 8 9 7 5

Existe uma grande extensão de assunto sobre árvores binárias, ao inserir e excluir dados de forma aleatória, será possível notar como a árvore se degenera (forma não balanceada) e por consequência aumenta o tempo de acesso para determinado elemento, para as próximas postagens teremos as rotinas de uma árvore binária declarada como uma biblioteca para suporte a qualquer programa que o utilize, e tendo como base essas rotinas, iremos incluir suporte a diferentes técnicas de balanceamento e pesquisa.