O objetivo dessa unidade é apresentar o conteúdo relacionado à Árvore Binária. Será feita uma abordagem focando na linguagem C.
Diferentemente das estruturas de dados vistas nas últimas aulas (listas, pilhas e filas), as estruturas de dados do tipo árvore não apresentam uma forma linear, ou seja, os elementos não estão armazenados de maneira sequencial. .
Uma arvore binária é uma estrutura de dados com capacidade de armazenar finitos elementos e que pode ser representada como uma hierarquia onde cada elemento é chamado de nó. O nó inicial ou o primeiro elemento é chamado de raiz.
Uma árvore pode estar vazia ou pode ser particionada em três subconjuntos:
A) Os nós da sub-árvore esquerda são menores que os nós da sub-árvore direita e também menores que o nó raiz.
B) Os nós da sub-árvore direita são maiores que os nós da sub-árvore esquerda e também maiores que o nó raiz.
C) Nomenclatura dos nós:
D) Nós ancestrais são os nós que estão acima de um nó e possuem ligação direta ou indireta;
E) Nós descendentes são os nós que estão abaixo de um nó e possuem ligação direta ou indireta;
F) Em uma árvore binária um nó pai pode ter no máximo dois nós filhos
G) O grau de um nó representa seu número de sub-árvores (nós filhos). Em uma árvore binária, o grau máximo de um nó é 2 e o menor 0.
H) O nível de um nó representa a sua distância do nó raiz, logo o nível do nó raiz é 0;
I) O número máximo de nós em um nível é dado pela expressão 2^n, sendo n o nível da árvore;
J) Árvore estritamente binária: todos os nós da árvore tem 0 ou 2 filhos
K) Árvore completa: todos os nós com menos de dois filhos ficam no último e penúltimo nível da árvore
L) Árvore cheia: árvore estritamente binária e completa.
M) Em consultas em árvores binárias todos os nós da ávore são listados, mudando-se apenas a ordem da listagem de acordo com o tipo de consulta realizada.
Temos três tipo de consultas:
Para representarmos um elemento da árvore (um nó), será definido um registro da seguinte maneira:
/*definição da estrutura que representará cada elemento da árvore binária*/ struct No{ int num; /*será uma árvore que armazenará inteiros*/ struct No *esq, *dir; /*ponteiros para fazer a ligação entre nós a esquerda e a direita*/ }; typedef struct No No;
Para melhor controlar a árvore utilizamos uma estrutura do tipo Árvore. Ela contém um ponteiro do tipo No, o ponteiro raiz, que irá armazenar o endereço de memória do nó que for a raiz da árvore.
struct Arvore{ struct No *raiz; /*ponteiro que irá apontar para a raiz da árvore*/ }; typedef struct Arvore Arvore;
Para o auxílio em algumas operações, vamos utilizar também uma estrutura do tipo pilha. Assim conforme a aula sobre pilha definimos:
/*definição do estrutura que irá representar cada elemento da árvore em um pilha*/ struct Elemento{ struct No *num; struct Elemento *prox; }; typedef struct Elemento Elemento; /*registro do tipo Pilha contento um ponteiro "topo" do tipo Elemento para controlar a pilha*/ struct Pilha{ struct Elemento *topo; /*aponta para o elemento qu esta no topo da pilha*/ }; typedef struct Pilha Pilha;
Vamos utilizar alguns ponteiros auxiliares durante as operações. Serão estes
/*ponteiros auxiliares*/
No *aux;
No *aux1;
No *novo;
No *anterior;
Elemento *aux2;
Nesse ponto definiremos também uma função cria_arvore( ). Ela será utilizada para alocar dinamicamente o espaço necessário para armazenar seu ponteiro "topo" e irá inicializá-lo com NULL, indicando que inicialmente a árvore está vazia. Não podemos nos esquecer também da função cria_pilha().
Arvore* cria_arvore(){
/*alocação do ponteiro arv para controlar a árvore*/
Arvore* arv = (Arvore*) malloc(sizeof(Arvore));
if(arv != NULL){
arv->raiz= NULL; /*a pilha inicia-se vazia, portanto seu topo é igual a NULL*/
}
return arv;
}
Pilha* cria_pilha(){
/*alocação do ponteiro pi para controlar a pilha*/
Pilha* pi = (Pilha*) malloc(sizeof(Pilha));
if(pi != NULL){
pi->topo= NULL; /*a pilha inicia-se vazia, portanto seu topo é igual a NULL*/
}
return pi;
}
Na função main, devemos definir um ponteiro do tipo Arvore e outro do tipo Pilha. Eles receberão os endereços do espaço alocado pelas funções cria_arvore( ) e cria_pilha( ) respectivamente. Além disso servirão de parâmetro para as demais funções seguintes.
int main(){ Arvore *arv = cria_arvore(); Pilha *pi = cria_pilha(); ...blocos de chamada de função... return 0; }
Serão realizadas as seguintes operações com árvores binárias:
Esta é a implementação da função que utilizaremos para inserir um elemento na árvore.
void insere_elemento(Arvore *arv){ /*a cada inserção alocamos dinamicamente um espaço para um novo elemento*/ No *novo =(No*) malloc(sizeof(No)); printf("Digite o numero a ser inserido na arvore: "); scanf("%d",&novo->num); novo->esq = NULL; novo->dir = NULL; /*caso a árvore esteja vazia, o elemento inserido será a raiz */ if(arv->raiz == NULL){ arv->raiz = novo; /*caso a árvore já contenha algum elemento*/ }else{ /*variável para verificação*/ int achou; /*aux aponta para o mesmo endereço de raiz*/ aux = arv->raiz; achou = 0; /*é feita uma busca em toda árvore para saber onde novo deve ser enserido*/ while(achou == 0){ /*caso o novo numero a ser inserido seja menor que aux-> num*/ if(novo->num < aux->num){ /*caso não aja nenhum elemento a esquerda de aux, novo será inserido a esquerda dele*/ if(aux->esq == NULL){ aux->esq = novo; achou = 1; /*caso já exista um elemento a esquerda de aux, aux aponta para este elemento e uma nova iteração será realizada*/ }else{ aux = aux->esq; } /*caso o novo numero a ser inserido seja maior ou igual a aux-> num*/ }else if(novo->num >= aux->num){ /*caso não aja nenhum elemento a direita de aux, novo será inserido a direita dele*/ if(aux->dir == NULL){ aux->dir = novo; achou = 1; }else{ /*caso já exista um elemento a direita de aux, aux aponta para este elemento e uma nova iteração será realizada*/ aux = aux->dir; } } } } printf("\nNumero inserido na arvore!"); getch(); }
Na prática isso aconteceria da seguinte maneira:
Inicialmente temos o ponteiro raiz apontado para null:
Agora vamos as inserções:
Inserção do número 37 na árvore:
Inserção do número 20 na árvore:
Inserção do número 10 na árvore:
Inserção do número 30 na árvore:
Inserção do número 80 na árvore:
Inserção do número 100 na árvore:
Inserção do número 180 na árvore:
Inserção do número 90 na árvore:
Inserção do número 5 na árvore:
Será feita uma busca pela árvore com o objetivo de encontrar determinado dado armazenado. A cada nó visitado verifica-se primeiramente se este contém o dado procurado. Caso não contenha, é verificado se o dado procurado é maior ou menor que o dado do nó em questão. Se for maior, a busca irá para a sub-árvore direita deste nó e , se for menor, para a sub-árvore esquerda.
void consulta_no(Arvore *arv){ /*caso a árvore esteja vazia*/ if(arv->raiz == NULL){ printf("\nArvore Vazia!!"); }else{ int numero, achou; printf("Digite o numero a ser consultado: "); scanf("%d", &numero); achou = 0; /*aux aponta para o mesmo endereço de raiz*/ aux = arv->raiz; /*enquanto aux não apontar para NULL e achou for igual a 0 será feita uma busca na árvore*/ while(aux != NULL && achou == 0){ /*caso aux-> seja igual o número buscado*/ if(aux->num == numero){ printf("Numero %d encontrado!", numero); achou = 1; /*do contrário verificamos se o número está a direita ou a esquerda de aux->num e atualizamos aux*/ }else if(numero < aux->num){ aux = aux->esq; }else{ aux = aux->dir; } } if(achou == 0) printf("Número não encontrado!"); } getch(); }
Para realizarmos a consulta em ordem na árvore utilizaremos a seguinte implementação:
/*consulta em ordem mostra os nós na seguinte ordem 1° ramo da esquerda 2° raiz 3° ramo da direita */ void consulta_arvore_ordem(Arvore *arv, Pilha *pi){ /*caso a árvore esteja vazia*/ if(arv->raiz == NULL){ printf("\nArvore Vazia!!"); /*caso a árvore contenha elementos*/ }else{ /*aux aponta para o endereço de raiz*/ aux = arv->raiz; /*como aqui utilizaremos uma pilha, incializamos seu topo com null*/ pi->topo = NULL; do{ /*caminha pela árvore pelo ramo da esquerda até NULL, colocando cada elemento visitado na pilha */ while(aux != NULL){ /*alocamos um espaço para inserir o elemento a ser mostrado na pilha*/ Elemento *aux_pilha =(Elemento*) malloc(sizeof(Elemento)); /*a pilha recebe o elemento apontado por auix*/ aux_pilha->num = aux; /*para encadear os elementos da pilha, aux_pilha->prox aponta para o topo da pilha*/ aux_pilha->prox = pi->topo; /*o topo da pilha apontará para o elemento que está sendo inserido na pilha*/ pi->topo = aux_pilha; /*aux aponta para o elemento a esquerda do aux atual*/ aux = aux->esq; } /*imprimiremos aos elementos empilhados no momento a partir do topo */ if(pi->topo != NULL){ aux2 = pi->topo; printf("%d ", aux2->num->num); /*caso aja um elemento a direita do elemento apontado por topo na árvore, seu prox será NULL, portanto ao encontrar um elemento a direita do elemento impresso retornaremos ao while anterior antes de imprimir o restante da pilha*/ aux = pi->topo->num->dir; pi->topo = pi->topo->prox; } }while(pi->topo != NULL || aux != NULL); } getch(); }
Com base na árvore final apresentada nos processos de inserção teremos o seguinte resultado da consulta:
Para realizarmos a consulta em pré-ordem na árvore utilizaremos a seguinte implementação:
/*consulta em pré-ordem mostra os nós na seguinte ordem 1° raiz 2° ramo da esquerda 3° ramo da direita */ void consulta_arvore_pre_ordem(Arvore *arv, Pilha *pi){ /*caso a árvore esteja vazia*/ if(arv->raiz == NULL){ printf("\nArvore Vazia!!"); /*caso a árvore contenha elementos*/ }else{ /*aux aponta para o endereço de raiz*/ aux = arv->raiz; /*como aqui utilizaremos uma pilha, incializamos seu topo com null*/ pi->topo = NULL; do{ /*caminha pela árvore mostrando cada elemento visitado, e também coloca cada elemento visitado na pilha */ while(aux != NULL){ /*alocamos um espaço para inserir um elemento na pilha*/ Elemento *aux_pilha =(Elemento*) malloc(sizeof(Elemento)); /*impressão do elemento apontado por aux*/ printf("%d ", aux->num); /*colocamos na pilha o elemento impresso*/ aux_pilha->num = aux; aux_pilha->prox = pi->topo; pi->topo = aux_pilha; /*fazemos com que aux aponte para o elemento a sua esquerda*/ aux = aux->esq; } if(pi->topo != NULL){ aux_pilha = pi->topo; pi->topo = pi->topo->prox; /*aux aponta para o elemento a direita de topo na árvore*/ aux = aux_pilha->num->dir; } }while(pi->topo != NULL || aux != NULL); } getch(); }
Com base na árvore final apresentada nos processos de inserção teremos o seguinte resultado da consulta:
Para realizarmos a consulta em pós-ordem na árvore utilizaremos a seguinte implementação:
/*consulta em pós-ordem mostra os nós na seguinte ordem 1° ramo da esquerda 2° ramo da dreita 3° raiz */ void consulta_arvore_pos_ordem(Arvore *arv, Pilha *pi){ /*caso a árvore esteja vazia*/ if(arv->raiz == NULL){ printf("\nArvore Vazia!!"); /*caso a árvore contenha elementos*/ }else{ /*aux aponta para o endereço de raiz*/ aux = arv->raiz; /*como aqui utilizaremos uma pilha, incializamos seu topo com null*/ pi->topo = NULL; do{ do{ /*caminha pela árvore pelo ramo da esquerda até NULL, colocando cada elemento visitado na pilha*/ while(aux != NULL){ /*alocamos um espaço para inserir um elemento na pilha*/ Elemento *aux_pilha = (Elemento*) malloc(sizeof(Elemento)); /*a pilha recebe o elemento apontado por aux*/ aux_pilha->num = aux; /*para encadear os elementos da pilha, aux_pilha->prox aponta para o topo da pilha*/ aux_pilha->prox =pi-> topo; /*o topo da pilha apontará para o elemento que está sendo inserido na pilha*/ pi->topo = aux_pilha; /*aux aponta para o elemento a esquerda do aux atual*/ aux = aux->esq; } /*caso o exista um elemento a direita do endereço apontado por topo na árvore, aux aponta para esse elemento*/ if(pi->topo->num->dir != NULL){ aux = pi->topo->num->dir; } }while(aux != NULL); if(pi->topo!= NULL){ /*imprime o elemento apontado por topo*/ printf("%d ", pi->topo->num->num); /*se ainda existirem elementos na pilha além de topo*/ if(pi->topo->prox != NULL){ /*caso exista um elemento a direta do prox da pilha na árvore e esse elemento seja diferente do topo, aux apontara para esse elemento e topo apontará para o próximo elemento da pilha*/ if(pi->topo->prox->num->dir != NULL && pi->topo->prox->num->dir != pi->topo->num){ aux = pi->topo->prox->num->dir; pi->topo = pi->topo->prox; /*caso o exista um elemento a direita do endereço apontado por topo na árvore e esse elemento seja igual a topo, topo apontará para o próximo elemento da pilha e este será impresso*/ }else{ /*caso exista um elemento a direta do prox da pilha na árvore e esse elemento seja igual ao topo, o topo apontará receberá prox e será impresso até que essa igualdade exista ou não existerem mais elementos na pilha, isso será feito através do while*/ while(pi->topo->prox != NULL && pi->topo->prox->num->dir == pi->topo->num){ pi->topo = pi->topo->prox; printf("%d ", pi->topo->num->num); } /*topo apontará para o próximo elemento da pilha*/ pi->topo = pi->topo->prox; /*se topo não for null aux aponta para o elemento a direita do endereço apontado por topo na árvore*/ if(pi->topo != NULL){ aux = pi->topo->num->dir; /*caso contrário aux recebe NULL*/ }else{ aux = NULL; } } /*se topo igual a NULL*/ }else{ pi->topo = pi->topo->prox; aux = NULL; } } }while(pi->topo != NULL || aux != NULL); } getch(); }
Com base na árvore final apresentada nos processos de inserção teremos o seguinte resultado da consulta:
Para removermos um elemento da árvore, utilizaremos a seguinte função:
void remove_elemento(Arvore *arv){ /*caso a árvore esteja vazia*/ if(arv->raiz == NULL){ printf("\nArvore Vazia!!"); /*caso a árvore contenha elementos*/ }else{ int numero, achou; printf("Digite o numero a ser removido da arvore: "); scanf("%d", &numero); /*aux aponta para o endereço de raiz*/ aux = arv->raiz; achou = 0; /*varre toda a árvore a procura do número a ser removido*/ while(aux != NULL && achou == 0){ if(aux->num == numero){ achou = 1; }else if(aux->num > numero){ aux = aux->esq; }else{ aux = aux->dir; } /*caso o número não seja encontrado*/ if(achou == 0){ printf("Numero nao encontrado!"); /*caso o número seja encontrado*/ }else{ /*caso o número a ser removido não seja a raiz*/ if(aux != arv->raiz){ anterior = arv->raiz; /*aqui procura-se o número anterior(pai) ao número a ser removido, o endereço deste será armazenado em anterior*/ while(anterior->dir != aux && anterior->esq != aux){ if(anterior->num > numero){ /*o número esta a esqueda da árvore*/ anterior = anterior->esq; }else{ /*o número esta a direita da árvore*/ anterior = anterior->dir; } } /*se o nó a ser removido for um nó folha*/ if(aux->dir == NULL && aux->esq == NULL){ /*se o nó a ser removido esta a direita de aux*/ if(anterior->dir == aux){ anterior->dir = NULL; /*se o nó a ser removido esta a esquerda de aux*/ }else{ anterior->esq = NULL; } free(aux); /*se o nó a ser removido for um nó não folha*/ }else{ /*se o nó a ser removido tiver apenas filho a direita*/ if(aux->dir != NULL && aux->esq == NULL){ /*se o nó a ser removido estiver a esquerda de anterior*/ if(anterior->esq == aux){ anterior->esq = aux->dir; /*se o nó a ser removido estiver a direita de anterior*/ }else{ anterior->dir = aux->dir; } free(aux); /*se o nó a ser removido tiver apenas filho a esquerda*/ }else if(aux->esq != NULL && aux->dir == NULL){ /*se o nó a ser removido estiver a esquerda de anterior*/ if(anterior->esq == aux){ anterior->esq = aux->esq; /*se o nó a ser removido estiver a direita de anterior*/ }else{ anterior->dir = aux->esq; } free(aux); /*se o nó a ser removido tiver filho a direita e a esquerda*/ }else if(aux->esq != NULL && aux->dir != NULL){ /*se o nó a ser removido estiver a direita de anterior*/ if(anterior->dir == aux){ anterior->dir = aux->dir; /*o nó a esquerda do nó a ser removido fica apontado por aux1*/ aux1 = aux->esq; /*se o nó a ser removido estiver a esquerda de anterior*/ }else{ anterior->esq = aux->dir; /*o nó a direita do nó a ser removido fica apontado por aux1*/ aux1 = aux->esq; } free(aux); /*aux aponta para anterior*/ aux = anterior; /*realocando o pedaço da árvore*/ while(aux != NULL){ /*caso aux seja menor, que aux1*/ if(aux->num < aux1->num){ /*caso aux não tenha filho a direita*/ if(aux->dir == NULL){ aux->dir = aux1; aux = NULL; /*caso aux tenha filho a direita*/ }else{ aux = aux->dir; } /*caso aux seja maior, que aux1*/ }else if(aux->num > aux1->num){ /*caso aux não tenha filho a esquerda*/ if(aux->esq == NULL){ aux->esq = aux1; aux = NULL; /*caso aux tenha filho a esquerda*/ }else{ aux = aux->esq; } } } } } /*caso o número a ser removido não seja a raiz*/ }else{ /*se o nó a ser removido for raiz e folha*/ if(aux->dir == NULL && aux->esq == NULL){ free(aux); arv->raiz = NULL; }else{ /*se o nó a ser removido tiver apenas filho a direita*/ if(aux->dir != NULL && aux->esq == NULL){ arv->raiz = aux->dir; free(aux); /*se o nó a ser removido tiver apenas filho a esquerda*/ }else if(aux->esq != NULL && aux->dir == NULL){ arv->raiz = arv->raiz->esq; free(aux); /*se o nó a ser removido tiver filho a direita e a esquerda*/ }else if(aux->dir != NULL && aux->esq != NULL){ arv->raiz = aux->dir; aux1 = aux->esq; free(aux); aux = arv->raiz; /*realocando o pedaço da árvore*/ while(aux != NULL){ /*caso aux seja menor, que aux1*/ if(aux->num < aux1->num){ /*caso aux não tenha filho a direita*/ if(aux->dir == NULL){ aux->dir = aux1; aux = NULL; /*caso aux tenha filho a direita*/ }else{ aux = aux->dir; } /*caso aux seja maior, que aux1*/ }else if(aux->num > aux1->num){ /*caso aux não tenha filhos a esquerda*/ if(aux->esq == NULL){ aux->esq = aux1; aux = NULL; /*caso aux tenha filhos a esquerda*/ }else{ aux = aux->esq; } } } } } } printf("Numero excluido da Arvore!"); } } getch(); }
Agora vamos às remoções:
Remoção do número 180 da árvore:
Remoção do número 80 da árvore:
Remoção do número 10 da árvore:
Remoção do número 20 da árvore:
Remoção do número 37 da árvore:
Nesta última operação esvaziaremos a nossa árvore, ou seja, removeremos todos os seus elementos restantes. Esta é a implementação utilizada:
void esvaziar_arvore(Arvore *arv, Pilha *pi){ /*caso a árvore esteja vazia*/ if(arv->raiz == NULL){ printf("\nArvore Vazia!!"); /*caso a árvore contenha elementos*/ }else{ /*aux aponta para o endereço de raiz*/ aux = arv->raiz; /*como aqui utilizaremos uma pilha, incializamos seu topo com null*/ pi->topo = NULL; do{ while(aux != NULL){ Elemento *aux_pilha =(Elemento*) malloc(sizeof(Elemento)); /*impressão do elemento apontado por aux*/ printf("%d ", aux->num); /*colocamos na pilha o elemento impresso*/ aux_pilha->num = aux; aux_pilha->prox = pi->topo; pi->topo = aux_pilha; /*fazemos com que aux aponte para o elemento a sua esquerda*/ aux = aux->esq; } if(pi->topo != NULL){ aux2 = pi->topo; pi->topo = pi->topo->prox; /*aux aponta para o elemento a direita de topo na árvore*/ aux = aux2->num->dir; } }while(pi->topo != NULL || aux != NULL); aux2 = pi->topo; /*passagem por todos os elementos da pilha e removendo cada um deles*/ while(aux2 != NULL){ pi->topo = pi->topo->prox; free(pi->topo->num); free(aux2); aux2 = pi->topo; } arv->raiz = NULL; printf(("\nArvore esvaziada"); } getch(); }
O resultado final após essa operação seria esse:
