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.