Para a implementação e uma árvore binária há duas estratégias de alocação de memória, estática ou dinâmica
A mais utilizada é a dinâmica, nela, cada nó da árvore é tratado como um ponteiro alocado dinamicamente a medida que os dados são inseridos
Não precisa saber o tamanho da árvore, os nós são criados a medida que a árvore vai crescendo
Como vamos utilizar a ferramenta VisuAlg para implementação da árvore, não vamos poder utilizar ponteiro, com isso, utilizaremos como estratégia a alocação estática de memória.
Na alocação estática de memória é utilizado um vetor para guardar os dados
Para saber o filho da esquerda ou da direita utilizamos a seguinte operação:
filho esq=2*pai (Filho da esquerda é igual a pai vezes dois)
filho dir=2*pai+1 (Filho da direita é igual a pai vezes dois mais um)
Utilizamos desta forma devido o nosso vetor iniciar com 1 (um), se iniciasse com 0 (zero) ficaria desta forma:
filho esq=2*pai+1 (Filho da esquerda é igual a pai vezes dois mais um )
filho dir=2*pai+2 (Filho da direita é igual a pai vezes dois mais dois)
É uma implementação interessante quando a árvore é completa, pois ocupa bem os espaços, quando a árvore possui um lado maior que o outro, o vetor fica com diversos locais vagos, tendo desperdício de memória.
Exemplo de alocação estática sequencial
Para representar a árvore binária da imagem anterior, o vetor ficaria desta forma:
Então, vamos ver com fica o código de uma árvore binária com inclusão, busca, exclusão e percurso no VisuAlg
Algoritmo "arvore_binaria"
// Descrição : implentação de uma árvore binária
// Autor(a) : Cléuber José
// Data atual : 9/1/2022
Const
TAM_VETOR=10
Var
// Seção de Declarações das variáveis
vet :vetor[1..TAM_VETOR] de inteiro
i,aux, elemento, opcao: inteiro
procedimento adicionar()
inicio
limpatela
repita
escreval("=========Adicinar elemento=====")
escreva("Informe o elemento, 0 (zero) para sair:")
leia(elemento)
se elemento<>0 entao
adicionar_com_posicao(1,elemento)
mostrar_vetor()
fimse
ate elemento=0 faca
fimprocedimento
procedimento adicionar_com_posicao(posicao, elemento: inteiro)
inicio
se elemento=vet[posicao] entao
escreval("Elemento já adiconado anteriormente")
senao
se vet[posicao]=0 entao
vet[posicao]<-elemento
escreval("Elemento adicionado com sucesso")
senao
se elemento <vet[posicao] entao
aux<-2*posicao
se aux>TAM_VETOR entao
escreval("Vetor já está cheio")
senao
adicionar_com_posicao(aux,elemento)
fimse
senao
aux<-2*posicao+1
se aux>TAM_VETOR entao
escreval("Vetor já está cheio")
senao
adicionar_com_posicao(aux,elemento)
fimse
fimse
fimse
fimse
fimprocedimento
procedimento buscar()
inicio
limpatela
repita
escreval("============Buscar Elemento=======")
escreva("Informe o elemento, 0 (zero) para sair:")
leia(elemento)
se elemento<>0 entao
aux<- buscar_com_posicao(1,elemento)
se aux<>0 entao
escreval("Elemento encontrato na posição: ",aux)
senao
escreval("Elemento não encontrado")
fimse
mostrar_vetor()
fimse
ate elemento=0 faca
fimprocedimento
funcao buscar_com_posicao(posicao, elemento:inteiro): inteiro
inicio
se vet[posicao]=0 entao
retorne 0
senao
se vet[posicao]=elemento entao
retorne posicao
senao
se elemento< vet[posicao] entao
aux <-posicao*2
se aux>TAM_VETOR entao
retorne 0
senao
retorne buscar_com_posicao(aux,elemento)
fimse
senao
aux<-posicao*2+1
se aux> TAM_VETOR entao
retorne 0
senao
retorne buscar_com_posicao(aux,elemento)
fimse
fimse
fimse
fimse
fimfuncao
procedimento remover()
inicio
limpatela
repita
escreval("============Remover Elemento=======")
escreva("Informe o elemento, 0 (zero) para sair:")
leia(elemento)
se elemento<>0 entao
aux<-buscar_com_posicao(1,elemento)
se aux=0 entao
escreval("Elemento não encontrado!")
senao
remover_com_posicao(aux)
escreval("Elemento excluído com sucesso")
fimse
mostrar_vetor()
fimse
ate elemento=0 faca
fimprocedimento
procedimento remover_com_posicao(posicao:inteiro)
var
filho_esquerda, filho_direita, qtde_filho:inteiro
inicio
filho_esquerda<-posicao*2
filho_direita<-posicao*2+1
se filho_esquerda> TAM_VETOR entao
filho_esquerda<-0
senao
se vet[filho_esquerda]=0 entao
filho_esquerda<-0
senao
qtde_filho<-qtde_filho+1
fimse
fimse
se filho_direita> TAM_VETOR entao
filho_direita<-0
senao
se vet[filho_direita]=0 entao
filho_direita<-0
senao
qtde_filho<-qtde_filho+1
fimse
fimse
se qtde_filho=0 entao
vet[posicao]<-0
senao
se qtde_filho=1 entao
se filho_esquerda>0 entao
vet[posicao]<- vet[filho_esquerda]
arrastar_arvore(filho_esquerda,posicao)
senao
vet[posicao]<- vet[filho_direita]
arrastar_arvore(filho_direita, posicao)
fimse
senao
elemento<-minimo_com_posicao(filho_direita)
aux<-buscar_com_posicao(filho_direita, elemento)
vet[posicao]<-vet[aux]
remover_com_posicao(aux)
fimse
fimse
fimprocedimento
procedimento arrastar_arvore(posicao_anterior, posicao_atual:inteiro)
inicio
vet[posicao_anterior]<-0
aux<-posicao_anterior*2
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
vet[posicao_atual*2]<-vet[aux]
arrastar_arvore(aux, posicao_atual*2)
fimse
fimse
aux<-posicao_anterior*2+1
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
vet[posicao_atual*2+1]<-vet[aux]
arrastar_arvore(aux, posicao_atual*2+1]
fimse
fimse
fimprocedimento
procedimento pre_ordem()
inicio
escreval("============Pré Ordem=======")
mostrar_vetor()
escreval("")
escreva("Sequência: ")
pre_ordem_com_posicao(1)
escreval()
repita
escreva("Informe 0 (zero) para sair: ")
leia(aux)
ate aux=0 faca
fimprocedimento
procedimento pre_ordem_com_posicao(posicao:inteiro)
inicio
escreva(vet[posicao]," ")
aux<-posicao*2
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
pre_ordem_com_posicao(aux)
fimse
fimse
aux<-posicao*2+1
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
pre_ordem_com_posicao(aux)
fimse
fimse
fimprocedimento
procedimento em_ordem()
inicio
escreval("============Em-Ordem=======")
mostrar_vetor()
escreval("")
escreva("Sequência: ")
em_ordem_com_posicao(1)
escreval()
repita
escreva("Informe 0 (zero) para sair: ")
leia(aux)
ate aux=0 faca
fimprocedimento
procedimento em_ordem_com_posicao(posicao:inteiro)
inicio
aux<-posicao*2
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
em_ordem_com_posicao(aux)
fimse
fimse
escreva(vet[posicao]," ")
aux<-posicao*2+1
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
em_ordem_com_posicao(aux)
fimse
fimse
fimprocedimento
procedimento pos_ordem()
inicio
escreval("============Pós-Ordem=======")
mostrar_vetor()
escreval("")
escreva("Sequência: ")
pos_ordem_com_posicao(1)
escreval()
repita
escreva("Informe 0 (zero) para sair: ")
leia(aux)
ate aux=0 faca
fimprocedimento
procedimento pos_ordem_com_posicao(posicao:inteiro)
inicio
aux<-posicao*2
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
pos_ordem_com_posicao(aux)
fimse
fimse
aux<-posicao*2+1
se aux<=TAM_VETOR entao
se vet[aux]<>0 entao
pos_ordem_com_posicao(aux)
fimse
fimse
escreva(vet[posicao]," ")
fimprocedimento
procedimento menu_principal()
inicio
repita
limpatela
escreval("=======Árvore binária===========")
escreval("---Informe uma opção----")
escreval("1 - Adicionar elemento")
escreval("2 - Buscar elemento")
escreval("3 - Mínimo")
escreval("4 - Máximo")
escreval("5 - Remover")
escreval("6 - Pré-ordem")
escreval("7 - Em-ordem")
escreval("8 - Pós-ordem")
escreval("0 - Sair")
escreva("Informe: ")
leia(opcao)
escolha (opcao)
caso 1
adicionar()
caso 2
buscar()
caso 3
minimo()
caso 4
maximo()
caso 5
remover()
caso 6
pre_ordem()
caso 7
em_ordem()
caso 8
pos_ordem()
fimescolha
ate opcao=0 faca
fimprocedimento
procedimento mostrar_vetor()
inicio
escreval("")
escreval("--------Dados do Vetor----")
para i de 1 ate TAM_VETOR faca
escreva(vet[i], " ")
fimpara
escreval("")
escreval("")
fimprocedimento
funcao vazio():logico
inicio
retorne vet[1]=0
fimfuncao
procedimento minimo()
inicio
limpatela
escreval("-------Menor Elemento da Árvore---")
se vazio() entao
escreval("Árvore vazia")
senao
aux <- minimo_com_posicao(1)
escreval("Menor elemento da árvore é: ",aux )
fimse
repita
escreva("Informe 0 (zero) para sair: ")
leia(aux)
ate aux=0 faca
fimprocedimento
funcao minimo_com_posicao(posicao: inteiro):inteiro
inicio
aux<-posicao*2
se (aux> TAM_VETOR) entao
retorne vet[posicao]
senao
se vet[aux]=0 entao
retorne vet[posicao]
senao
se vet[aux]<vet[posicao] entao
retorne minimo_com_posicao(aux)
fimse
fimse
fimse
fimfuncao
procedimento maximo()
inicio
limpatela
escreval("-------Maior Elemento da Árvore---")
se vazio() entao
escreval("Árvore vazia")
senao
aux <- maximo_com_posicao(1)
escreval("Maior elemento da árvore é: ",aux )
fimse
repita
escreva("Informe 0 (zero) para sair: ")
leia(aux)
ate aux=0 faca
fimprocedimento
funcao maximo_com_posicao(posicao: inteiro):inteiro
inicio
aux<-posicao*2+1
se (aux> TAM_VETOR) entao
retorne vet[posicao]
senao
se vet[aux]=0 entao
retorne vet[posicao]
senao
se vet[aux]>vet[posicao] entao
retorne maximo_com_posicao(aux)
fimse
fimse
fimse
fimfuncao
Inicio
// Seção de Comandos, procedimento, funções, operadores, etc...
menu_principal()
Fimalgoritmo
Nenhum comentário:
Postar um comentário