árvorebinaria (1).pptx

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

ÁRVORE BINÁRIA
ALEXANDRE
CARLA
DRYELLE 
INARA
THIAGO HENRIQUE 
1
CONCLUSÃO
INTRODUÇÃO
FUNDAMENTOS
PROPRIEDADES
TIPOS
    IMPLEMENTAÇÃO
APLICAÇÕES
ÍNDICE
1
2
3
7
5
4
6
2
		
INTRODUÇÃO
Estruturas de dados  do tipo árvore são NÃO-LINEAR constituída de nós;
Existe um nó r, denominado RAIZ, com zero ou mais sub-árvores, cujas raízes estão ligadas a r.
CADA NÓ e rotulado como sendo um filho da direita ou filho da esquerda
3
RAIZ
SUB ARVORE ESQUERDA
SUB ARVORE DIREITA
INTRODUÇÃO
4
4
		
FUNDAMENTOS
GRAU: Números de sub-árvores de um nó.
 FOLHA: Um nó que possui grau zero, ou seja, não possui sub-árvores.
 FILHOS: São as raízes das sub-árvores de um nó .
 ALTURA: 
Uma árvore nula tem altura 0.
A altura de uma árvore é o comprimento do caminho mais longo da raiz ate uma das folhas
CAMINHO:
Existe um único caminho entre a raiz e qualquer outro nó. 
Todos os nós são acessíveis a partir da raiz. 
5
6
PROPRIEDADES
A = Raiz;
B = Subárvore Esquerda;
C = Subárvore Direita;
D, G, H, I = Folhas;
A é pai de B e C.
Os nós nos mesmos níveis são chamados irmãos;
	
EXEMPLOS
B
A
A
B
RAIZ DA ÁRVORE T1
FILHO DIREITO OU SUB-ÁRVORE DIREITA DE T2
FILHO ESQUERDO OU SUB-ÁRVORE ESQUERDA DE T1
A
B
C
A
RAIZ DA ÁRVORE T2
NOTE QUE AS ÁRVORES BINÁRIAS T1 E T2 SÃO DIFERENTES, POIS, APESAR DE TEREM O MESMO CONTEÚDO NA RAIZ, O CONTEÚDO DE SEUS RESPECTIVOS NÓS FILHOS DIREITO E ESQUERDO SÃO DIFERENTES.
T1  T2
7
TIPOS
A
C
B
E
F
D
I
G
H
NÍVEL 0
NÍVEL 1
NÍVEL 2
NÍVEL 3
A profundidade ou altura de uma árvore binária é determinada pelo seu maior nível.
PROFUNDIDADE
8
A
C
B
D
E
F
G
TODO NÓ NÃO-FOLHA DEVE TER SUB-ÁRVORES ESQUERDA E DIREITA NÃO VAZIAS.
TIPOS
ESTRITAMENTE BINARIA
9
9
A
C
B
E
D
H
I
F
G
TIPOS
QUASE COMPLETA
1: Todas as folhas estão no último ou penúltimo níveis.
2: Para cada nó com descendente direito no último nível, todos os descendentes esquerdos folhas também estiverem no último nível
10
: 
É UMA ÁRVORE ESTRITAMENTE BINÁRIA EM QUE TODAS AS FOLHAS ESTÃO NO MESMO NIVEL DA ÁRVORE.
TIPOS
ÁRVORE CHEIA
A
C
B
F
G
D
E
11
12
CONSULTAS EM-ORDEM
TIPOS
Percorrer a sub-árvore esquerda em-ordem
Visitar a raiz
Percorrer a sub-árvore direita em em-ordem
                                                      
                                                                     Percurso: 1, 2, 3, 4, 6, 8
6
2
4
1
8
3
12
Visitar a raiz
Percorrer a sub-árvore esquerda em pré-ordem
Percorrer a sub-árvore direita em pré-ordem
13
CONSULTAS PRÉ-ORDEM
TIPOS
Percurso: 6, 2, 1, 4, 3, 8 
6
2
4
1
8
3
13
Percorrer a sub-árvore esquerda em pós-ordem
Percorrer a sub-árvore direita em pós-ordem 
Visitar a raiz
14
6
2
4
1
8
3
CONSULTAS PÓS-ORDEM
TIPOS
Percurso: 1,4, 2, 3, 8, 6
14
IMPLEMENTAÇÃO
15
15
APLICAÇÕES
AS ÁRVORES DE DECISÃO USADAS NA INTELIGÊNCIA ARTIFICIAL
 REPRESENTAÇÃO DE EXPRESSÕES ARITMÉTICAS
 ESTRUTURA DE DIRETÓRIOS E ARQUIVOS DE UM SISTEMA OPERACIONAL
16
CONCLUSÃO
17
Tem uma implementação muito fácil, inserção e remoção muito rápidas, mas a nível de pesquisa pode nos levar a casos muito desfavoráveis.
Não podemos falar que a árvore binária seja melhor ou pior, e sim verificar que melhor convém ao problema que nos é apresentado. 
17
REFERÊNCIAS
18
ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos de. Estruturas de dados: algoritmos, análise da complexidade e implementações em JAVA e C/C++. São Paulo - Sp: Pearson Education - Br, 2011. 432 p.
ESTRUTURA DE DADOS; Disponível em http://cic.unb.br/~alchieri/disciplinas/graduacao/ed/arvores.pdf Acesso em 29 de dezembro 2016