Árvores binárias

Para começarmos a falar sobre árvores e sua manipulação temos que entender primeiramente o seu funcionamento e a sua estrutura, uma árvore binária nada mais é do que uma estrutura de dados, a diferença de uma estrutura de dados normal seriam as suas outras características, uma árvore binária além de ser uma struct seu primeiro elemento recebe o nome de nó raiz, e os demais nós também são conhecidos como nós internos ou sub-árvores, de onde se originam mais nós, e onde não temos nós filhos ficam conhecidos como folhas, para cada raiz temos uma sub-árvore a sua direita e outra sub-árvore a sua esquerda,ou não possuímos nenhum nó, tornando essa árvore nula. Os nós pais são aqueles nós que vem antes do próximo nó, como por exemplo, o nó 8 na imagem abaixo, é pai do nó de elemento número 9, na mesma representação abaixo da árvore binária, podemos ver que nessa árvore a raiz é o nó onde se encontra o elemento de número 6, de onde se originam os demais nós, contendo os demais elementos.

Na arvore acima podemos observar seus nós claramente representados, é importante perceber que para chegar em determinado nó, seguimos um único caminho sempre, ou seja, não temos nada além de UM ÚNICO caminho em uma árvore binária, para mais informações sobre a árvore, podemos classificá-la em altura, profundidade e nível.

Para visualizarmos esses aspectos é necessário fazermos algumas verificações, por exemplo, para analisarmos a altura da árvore contamos quantas ligações temos até o seu elemento mais distante, sempre partindo do ponto de partida (raiz) da árvore. Abaixo a demonstração gráfica da contagem de profundidade da árvore apresentada acima. Que por sua vez é uma árvore de profundidade 3.

Podemos também a partir dessa imagem visualizar o nível dos elementos, os elementos no nível 1 nesse caso seriam os elementos 3 e 8, de nível 2 os elementos 1 e 9, e de nível 3 nesse caso somente teríamos o elemento 7.

Transpassando a árvore para um código em C.

A seguir montaremos uma árvore binária em um algoritmo em C, para isso vamos utilizar o programa DEV C++, que também funciona como um compilador de C (com alguns BUGs as vezes, mas viável para trabalhar) o código completo de montagem e preenchimento de uma árvore binária fica da seguinte maneira:

#included <iostream>

#included <stdlib.h>

#included <stdio.h>

int main ()

{

struct Noarvore{

    int numero;

    struct No *esquerda;

    struct No *direita;

};

typedef struct Noarvore No;

}

void criarArvore(Noarvore **pRaiz){

    *pRaiz = NULL;

}

void inserir(Noarvore **pRaiz, int numero){

    if(*pRaiz == NULL){

        *pRaiz = (Noarvore *) malloc(sizeof(No));

        (*pRaiz)->esquerda = NULL;

        (*pRaiz)->direita = NULL;

        (*pRaiz)->numero = numero;

    }else{

        if(numero < (*pRaiz)->numero)

            inserir(&(*pRaiz)->esquerda, numero);

        if(numero > (*pRaiz)->numero)

            inserir(&(*pRaiz)->direita, numero);

    }

}

No *MaiorDireita(No **no){

    if((*no)->direita != NULL) 

       return MaiorDireita(&(*no)->direita);

    else{

       No *aux = *no;

       if((*no)->esquerda != NULL)

          *no = (*no)->esquerda;

       else

          *no = NULL;

       return aux;

       }

}

No *MenorEsquerda(No **no){

    if((*no)->esquerda != NULL) 

       return MenorEsquerda(&(*no)->esquerda);

    else{

       No *aux = *no; 

       if((*no)->direita != NULL) 

          *no = (*no)->direita;

       else

          *no = NULL;

       return aux;

       }

}

void remover(Noarvore **pRaiz, int numero){

    if(*pRaiz == NULL){   

       printf("O numero que voce esta procurando nao existe na arvore");

       getch();

       return;

    }

    if(numero < (*pRaiz)->numero)

       remover(&(*pRaiz)->esquerda, numero);

    else 

       if(numero > (*pRaiz)->numero)

          remover(&(*pRaiz)->direita, numero);

       else{    

          Noarvore *pAux = *pRaiz;     

          if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){ 

                free(pAux);

                (*pRaiz) = NULL; 

               }

          else{     

             if ((*pRaiz)->esquerda == NULL){

                (*pRaiz) = (*pRaiz)->direita;

                pAux->direita = NULL;

                free(pAux); pAux = NULL;

                }

             else{           

                if ((*pRaiz)->direita == NULL){

                    (*pRaiz) = (*pRaiz)->esquerda;

                    pAux->esquerda = NULL

                    free(pAux); pAux = NULL;

                    }

                else{      

                   pAux = MaiorDireita(&(*pRaiz)->esquerda); 

                   pAux->esquerda = (*pRaiz)->esquerda;        

                   pAux->direita = (*pRaiz)->direita;

                   (*pRaiz)->esquerda = (*pRaiz)->direita = NULL;

                   free((*pRaiz));  *pRaiz = pAux;  pAux = NULL;   

                   }

                }

             }

          }

}

Criamos o código acima que insere dados na arvore, remove e também cria a nova árvore.