Árvore Binária de Busca

Prévia do material em texto

UFPI - CCN - CIÊNCIA DA COMPUTAÇÃO
ESTRUTURA DE DADOS - Professor Dr. Raimundo Moura
Relatório Técnico
Eduardo Bezerra de Sousa
Ildefonso Amorim de Souza Braga Mury
Rodrigo do Nascimento Borges
Vicente Cleyton Gonçalves de Sousa Carvalho
Árvore Binária de Busca
- INTRODUÇÃO
Uma Árvore Binária de Busca (Binary Search Tree, em inglês) é uma estrutura
de dados baseada em nós. Cada nó armazena valores e pode estar associado a uma
sub-árvore à esquerda ou a uma sub-árvore à direita. O padrão define que os valores à
esquerda sejam menores que o do nó raiz, e os da direita sejam valores maiores que o
nó raiz. Os nós são onde ficam os itens armazenados na árvore. O nó mais ao topo é
chamado de raiz e os itens logo abaixo da raiz são os filhos, que vão até as folhas,
sendo esses os últimos itens da árvore.
(Fig.1: Representação gráfica de uma árvore binária de busca.)
- OBJETIVOS E SOLUÇÃO
Esta atividade prática tem objetivo de discutir aspectos relacionados ao
funcionamento da estrutura de dados Árvore Binária de Busca, bem como fornecer
resoluções para as questões propostas.
Descrição: Desenvolver uma aplicação (interface GUI) com opções para:
1) Criar uma Árvore Binária de Busca, considerando um arquivo de entrada com
nomes de pessoas.
(Fig.2: Menu principal da Interface GUI desenvolvida para o projeto.)
(Fig.3: Tela que solicita a entrada de dados a partir do usuário.)
Foram testados como entrada 2 arquivos de texto, cada um contendo um tipo de
itens a serem inseridos:
- Contendo nomes de pessoas(nomes.txt);
- Contendo letras maiúsculas do alfabeto(letras.txt);
(Fig.5: Tela ao realizar inserção com sucesso.)
2) Mostrar o tamanho da árvore, através de um método recursivo que devolva o
número de nós de uma árvore binária.
(Fig.6: Método recursivo que mostra o tamanho da árvore.)
(Fig.7: Tamanho da árvore gerada pelo arquivo com nomes.)
(Fig.8: Tamanho da árvore gerada pelo arquivo com letras.)
3) Mostrar a altura da árvore, através de um método (recursivo) que calcule a
altura de uma árvore binária.
(Fig.9: Método recursivo que mostra a altura da árvore.)
(Fig.10: Altura da árvore gerada pelo arquivo com nomes.)
(Fig.11: Altura da árvore gerada pelo arquivo com letras.)
4) Escrever um método internalPathLength para calcular e apresentar o
comprimento interno de uma BT (Árvore Binária).
(Fig.12: Método recursivo que mostra o comprimento interno da árvore.)
(Fig.13: Comprimento interno da árvore gerada pelo arquivo com nomes.)
(Fig.14: Comprimento interno da árvore gerada pelo arquivo com letras.)
5) Mostrar os três percursos (travessias) da árvore, através de métodos para
imprimir as chaves de uma BT:
I) em-ordem (ou seja, esquerda-raiz-direita);
II) pós-ordem (esquerda-direita-raiz);
III) pré-ordem (raiz-esquerda-direita).
(Fig.15: Os três percursos na árvore gerados pelo arquivo com nomes.)
(Fig.16: Os três percursos na árvore gerados pelo arquivo com letras.)
Foram implementadas mais duas funcionalidades no trabalho: o método depth
nos possibilita obter a profundidade (distância entre a raiz e a folha mais profunda) da
árvore, e o método get torna possível pesquisarmos por determinado item que pode ou
não estar contido na árvore e obter sua ordem de inserção.
(Fig.17: Profundidade da árvore gerada pelo arquivo com nomes.)
(Fig.18: Profundidade da árvore gerada pelo arquivo com letras.)
(Fig.19: Ordem de inserção na busca pelo nome Igor na árvore do arquivo nomes.txt.)
(Fig.20: Ordem de inserção na busca pelo nome Igor na árvore do arquivo letras.txt.)
- IMPLEMENTAÇÃO
As ferramentas utilizadas para a execução do trabalho consistem na IDE Eclipse
2019-6 com o Java instalado. O projeto possui 3 classes, sendo elas a classe GUI
(interface gráfica da aplicação), a classe BST contendo a parte lógica da estrutura e a
classe Queue, implementada para auxiliar o funcionamento da classe BST.
(Fig.21: Organização dos pacotes e classes contidos no projeto.)
- CONCLUSÃO
O trabalho foi realizado com sucesso, visto que as funções implementadas
atendem aos requisitos solicitados. Os integrantes do grupo conseguiram organizar-se
de forma que todos pudessem cooperar com a realização da atividade e extrair o
máximo de conhecimento possível sobre a estrutura de dados Árvore Binária de Busca.