AULA 4 PPT - OTIM DE SISTEMAS DE TRANS GST0311

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

OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 4 – ÁRVORES BINÁRIAS
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
 Árvores Binárias
Objetivos:
Identificar os conceitos iniciais para a varredura de uma Árvore Binária.
Conhecer exemplos de aplicação de varredura de uma Árvore Binária. 
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
ÁRVORE BINÁRIA - DEFINIÇÃO
Árvore Binária T é um conjunto finito de elementos denominados nós ou vértices, tal que: 
 T = 0 e a árvore é dita vazia ou
 Existe um nó r, chamado raiz de T, e os nós restantes podem ser divididos em dois subconjuntos disjuntos, Tre e Trd, que são as subárvores esquerda e direita de r, respectivamente e as quais, por sua vez, também são árvores binárias. 
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
 Possuem um número constante de subárvores em cada nó
 Limitação do número de ponteiros usados
 Algoritmos eficientes para o tratamento
 A forma de armazenar os nós surge naturalmente de sua definição:
 Ponteiro para o nó raiz (como nas listas lineares) 
 Ponteiros para os filhos: esq e dir 
 Necessita de 2n+1 ponteiros para representar n nós.
Exemplo: Para operacionalizar uma Árvore Binária com 5 nós, são necessários 2*5 + 1 = 11 ponteiros.
VANTAGENS
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
 A busca nada mais é do que um percurso em uma árvore.
O percurso em uma árvore visitando cada nó uma única vez gera uma sequência linear de nós.
Assim, passa a ter sentido falar em sucessor e predecessor de um nó segundo um determinado percurso.
Há três maneiras recursivas de se percorrer árvores. binárias:
Percurso em pré-ordem
Percurso em pós-ordem
Percurso em ordem 
 PERCURSOS EM ÁRVORES BINÁRIAS
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
  Percurso em Pré-Ordem
Neste caso a visita aos nós acontecem de cima para baixo da esquerda para a direita, Passando pelo nó raiz antes de visitar os nós a ela ligados. 
 Algoritmo básico:
Se árvore vazia  fim 
Visitar o nó raiz 
Percorrer em pré-ordem a sub-árvore esquerda 
Percorrer em pré-ordem a sub-árvore direita 
 PERCURSOS EM ÁRVORES BINÁRIAS
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
 PERCURSOS EM ÁRVORES BINÁRIAS
A – B – C – D – E – F – G – H - I
Percurso em “Pré-Ordem” (Raiz – TRE – TRD)
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
 PERCURSOS EM ÁRVORES BINÁRIAS
Percurso em “Em Ordem”
Neste caso a visita aos nós acontecem de baixo para cima da esquerda para a direita.
Algoritmo básico:
Se árvore vazia  fim 
percorrer em ordem a sub-árvore esquerda 
visitar o nó raiz 
percorrer em ordem a sub-árvore direita 
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Percurso em “Em Ordem” (TRE – Raiz –TRD)
C – B – A – E – F – D – H – G - I
 PERCURSOS EM ÁRVORES BINÁRIAS
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
 PERCURSOS EM ÁRVORES BINÁRIAS
Percurso em Pós-Ordem
Neste caso a visita aos nós acontecem da esquerda para a direita de baixo para cima, visitando por último a raiz.
Algoritmo básico:
 Se árvore vazia  fim 
 percorrer em pós-ordem a sub-árvore esquerda 
 percorrer em pós-ordem a sub-árvore direita 
 visitar o nó raiz 
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Percurso em “Pós-Ordem” (TRE –TRD – Raiz)
 PERCURSOS EM ÁRVORES BINÁRIAS
C – B – F – E – H – I – G – D - A
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
 PERCURSOS EM ÁRVORES BINÁRIAS
1 – 3 – 2 – 4 – 5 – 6 – 7
Exercício de Percurso em “Pré-Ordem” (Raiz – TRE – TRD)
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
3 – 1 – 4 – 5 – 2 – 6 – 7
 PERCURSOS EM ÁRVORES BINÁRIAS
Exercício de Percurso em “Em ordem” (TRE – Raiz –TRD)
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
3 – 5 – 4 – 7 – 6 – 2 – 1
 PERCURSOS EM ÁRVORES BINÁRIAS
Exercício de Percurso em “Pós-Ordem” (TRE –TRD – Raiz) 
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
1 – É correto afirmar sobre Arvore Binária que:
É um conjunto finito de elementos denominados nós ou vértices
É um conjunto infinito de elementos denominados nós ou vértices
É um conjunto finito de elementos denominados arestas ou vértices
É um conjunto infinito de elementos denominados nós ou arestas
É um conjunto finito de elementos denominados nós ou arestas
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
1 – É correto afirmar sobre Arvore Binária que:
É um conjunto finito de elementos denominados nós ou vértices
É um conjunto infinito de elementos denominados nós ou vértices
É um conjunto finito de elementos denominados arestas ou vértices
É um conjunto infinito de elementos denominados nós ou arestas
É um conjunto finito de elementos denominados nós ou arestas
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
2 – É correto afirmar que está entre as vantagens das árvores binárias:
Possuem um número constante de sub-árvores em cada nó.
Algoritmos ineficientes para o tratamento.
A forma de armazenar os nós não surge naturalmente de sua definição.
Possuem um número inconstante de sub-árvores em cada nó.
Possuem um número constante de sub-árvores em cada raiz.
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
2 – É correto afirmar que está entre as vantagens das árvores binárias:
Possuem um número constante de sub-árvores em cada nó.
Algoritmos ineficientes para o tratamento.
A forma de armazenar os nós não surge naturalmente de sua definição.
Possuem um número inconstante de sub-árvores em cada nó.
Possuem um número constante de sub-árvores em cada raiz.
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
AULA 4 – ÁRVORES BINÁRIAS
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
BONS ESTUDOS E ATÉ A PRÓXIMA