ÁRVORE BINÁRIA- Estrutura de Dados

Prévia do material em texto

ÁRVORE BINÁRIA
EM PYTHON 
ALUNA: Luana Carvalho
DISCIPLINA: Estrutura de Dados
Prof.: Marcus Aurelius De Oliveira Vasconcelos 
CURSO: ADS - IFS
O QUE 
SÃO
ÁRVORES 
BINÁRIAS
?
CARACTERÍSTICAS:
VERSÁTEIS
HIERÁRQUICAS
ARMAZENAM DADOS POR NÓS 
POSSUI NO MÁXIMO DOIS FILHOS
TORNAM O ACESSO MAIS RÁPIDO
ÁRVORES 
BINÁRIAS
ONDE
PODEMOS
ACHÁ-LAS
?
 Na representação da estrutura de 
diretórios do Sistema de Arquivos.
 Na otimização de consultas.
 Na indexação de banco de dados.
ÁRVORES 
BINÁRIAS
Árvore 
Binária 
de
BUSCA
Sendo válida para todas as sub árvores:
 Todos os nós da sub árvore esquerda de qualquer nó
possuem chave menor que a chave do mesmo.
 Todos os nós da sub árvore à sua direita possuem
chave maior que a chave do nó em questão.
ÁRVORES 
BINÁRIAS
_______ 200 ____
| |
___ 100 ___ ___ 300___
| | | | 
050 150 250 350 
MAIORMENOR
ESTUDO 
DE CASO
Sistema para cadastro e 
pesquisa para pastas de 
Sistemas de Arquivos 
Tradicionais 
ARQUIVO = ÁRVORE
COMO
VISUALIZAR
A ÁRVORE E O 
NÓ NO 
PROGRAMA
?
PASTA = NÓ
nome_pessoa: String
codigo: int
local: String
Pasta
registrar()
acessarRegistro()
QUAIS 
CLASSES 
SERÃO 
USADAS
?
cod: int
esq: int
dir: String
No
cod: int
esq: int
dir: String
Arvore
ÁRVORE 
BINÁRIA
vs
LISTA 
ENCADEADA 050 100 150 200 250
INICIO
300 350
E se... fosse 
procurado um numero 
inexistente, por 
exemplo “400”?
Ordem com estrutura 
de árvore binária
INICIO
100
200
50
NULL
300
150 250 350
NULL NULL NULL NULL NULL NULL NULL
Ordem crescente de 
lista encadeada
MENU
SAÍDA
Se 
OPÇÃO 
= 1
Se 
OPÇÃO 
= 2
Se 
OPÇÃO 
= 3
Se 
OPÇÃO 
= 4
Verdadeiro Verdadeiro Verdadeiro
Verdadeiro
Falso FalsoFalso Falso
senão
MENU DE OPÇÕES
1 – Cadastro
2 – Pesquisa
3 – Relatório
4 – Sair
É tipo 
inteiro
?
Falso
Verdadeiro
Código
cadastrado
?
Procurar dado
Verdadeiro
Falso
É aqui que está o
Sistema de Arquivos 
com a estrutura de
Árvore Binária
BANCO DE 
DADOS
Armazenar
ConsultarConsultar
FLUXOGRAMA DO SISTEMA
OBJETIVO  Identificar mais rápido a inexistência de 
dado durante uma pesquisa de cadastro
IMPLEMENTAÇÃO
PARTE 1/8
>>> CLASSE PASTA
IMPLEMENTAÇÃO
>>métodos de
acesso aos atributos 
da classe (get/set)
>>validação do 
codigo
PARTE 2/8
>>> CLASSE PASTA (continuação)
IMPLEMENTAÇÃO
>>método construtor
>>método especial
PARTE 3/8
>>> CLASSE NÓ 
class Arvore():
def __init__(self, chave, dir, esq):
self.raiz = No(None, None, None)
self.raiz = None
IMPLEMENTAÇÃO
>>método construtor
>>Encapsulamento do 
atributo com métodos 
de acesso e alteração 
(get e set)
PARTE 4 /8
>>> CLASSE ARVORE 
IMPLEMENTAÇÃO
>>registrarPasta()
PARTE 5 /8
>>> CLASSE ARVORE (continuação)
IMPLEMENTAÇÃO
>>procurarPasta()
PARTE 6/8
>>> CLASSE ARVORE (continuação)
IMPLEMENTAÇÃO
>>relatório()
(com dicionário)
PARTE 7/8
>>> CLASSE ARVORE 
IMPLEMENTAÇÃO
>>menu
PARTE 8/8
>>> MAIN (Programa Principal) 
OBRIGADA!
FONTES:
 https://pythonhelp.wordpress.com/2015/01/19/arvore-binaria-de-
busca-em-python/
 https://www.devmedia.com.br/trabalhando-com-arvores-
binarias-em-java/25749
 https://gist.github.com/divanibarbosa/a8662693e44ab9ee0d0e8c
2d74808929
https://pythonhelp.wordpress.com/2015/01/19/arvore-binaria-de-busca-em-python/
https://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
https://gist.github.com/divanibarbosa/a8662693e44ab9ee0d0e8c2d74808929