Aula-03 (Árvores Binárias)

•

UNIT

0

Àlvaro Silva

28/05/2021

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

Árvores Binárias 
 
 
Prof. Ricardo Porto 
Contato: ricardo.aporto@souunit.com.br 
1 
Árvore Binária (AB) - Definições 
Por que estudar Árvores Binárias? 
• Inserção lenta em um vetor ordenado 
• Busca lenta em uma lista encadeada 
• Árvore 
• Inserção e remoção rápidas como da lista encadeada 
• Busca rápida como do vetor 
 
 
2 
Árvore Binária (AB) - Definições 
3 
Árvore Binária - Exemplo 
4 
Árvore Binária 
Observação: 
 
 Note que a árvore binaria não é um caso particular de árvore, mas 
um conceito diferente. Toda árvore binária é uma árvore, mas 
nem toda árvore é uma árvore binária. 
Tipos de árvores binárias 
Exemplo de árvores binárias 
Cheia 
Tipos de árvores binárias 
 Árvore binária Completa: Se um nó não possui pelo menos 
uma das subárvores (esquerda ou direita), ele deve estar no 
último ou no penúltimo nível. 
 
Tipos de árvores binárias 
 Árvore Binária Cheia: Uma árvore binária é cheia quando 
todas as suas folhas estão no último nível. 
Aplicação de árvores 
 Problemas de busca de dados armazenados na memória 
principal do computador: árvore binária de busca, árvores (quase) 
balanceadas como AVL, etc. 
 
 Problemas de busca de dados armazenados na memória 
secundária e principal do computador: B-árvores. 
 
Aplicação de árvores 
 
 Aplicações em Inteligência Artificial: árvores que representam o 
espaço de soluções, jogo de xadrez, resolução de problemas, etc. 
Caminhamentos em árvore binária 
 Um caminhamento, ou percurso, em uma árvore binária é o ato 
de percorrer sistematicamente todos os nós da árvore, sendo 
cada nó visitado exatamente uma vez. 
12 
Caminhamentos em árvore binária 
 
 Um caminhamento completo sobre uma árvore produz um 
sequência linear de nós, de maneira que cada nó tem um nó 
seguinte e um nó anterior. 
13 
Caminhamentos em árvore binária 
 No caso da árvore binária existem três tipos de 
caminhamento em profundidade mais frequentemente 
utilizados: 
 
 LRN (Left-Right-No) - (pós-ordem)‏ 
 
 NLR (No-Left-Right) - (pré-ordem)‏ 
 
 LNR (Left-No-Right) - (in-ordem) 
Caminhamento LRN (pós-ordem)‏ 
 O caminhamento LRN: 
1. Visitamos o ramo esquerdo de cada nó; 
2. em seguida o ramo direito; e, 
3. finalmente, o próprio nó. 
 
 Esse caminhamento é recursivo já que cada um dos ramos 
esquerdo e direito pode ser considerado uma subárvore. 
Caminhamento LRN (pós-ordem)‏ 
 
 
- 
* / 
A C + 
D E 
B 
Caminhamento LRN (pós-ordem)‏ 
(Left-Right-No) 
 A B * C D E + / - 
 - 
* / 
A C + 
D E 
B 
Caminhamento NLR (pré-ordem)‏ 
 O caminhamento NLR inicia pela raiz, como segue: 
 
1. primeiro é visitado o próprio nó; 
 
2. em seguida a subárvore esquerda; 
 
1. por último, a subárvore direita. 
 
Caminhamento NLR (pré-ordem)‏ 
- 
* / 
A C + 
D E 
B 
Caminhamento NLR (pré-ordem)‏ 
(No-Left-Right) 
 - * A B / C + D E 
 
- 
* / 
A C + 
D E 
B 
Caminhamento LNR (in- ordem)‏ 
Também conhecida como árvore simétrica. 
 
1. primeiro é visitada a subárvore esquerda; 
 
1. em seguida o nó; 
 
2. finalmente a subárvore direita. 
 
Caminhamento LNR (in-ordem)‏ 
- 
* / 
A C + 
D E 
B 
Caminhamento LNR (in-ordem)‏ 
(Left-No-Right) 
 A * B - C / D + E 
- 
* / 
A C + 
D E 
B 
Resumo 
Resumo 
Resumo 
Caminhamento em Largura 
 Os caminhamentos que vimos até aqui foram caminhamentos em 
profundidade. Há uma outra forma de caminhamento, não tão 
usada, denominada de caminhamento em largura. 
 
Caminhamento em Largura 
 
 No caminhamento em largura, visitamos os nós da árvore por 
níveis da árvore visitando todos os nós de um nível da árvore 
da esquerda para a direita e então partindo para o próximo 
nível. 
Caminhamento em Largura 
 CAMINHO: - * / A B C + D E 
 
- 
* / 
A C + 
D E 
B 
 
 
 
Exercício 
1) Dada a seguinte árvore, pede-se para percorrê-la usando os 
percursos pré-ordem, em ordem simétrica (in-ordem) e pós-ordem. 
 
D) O grau de cada nó 
E) A altura de cada nó 
F) A profundidade de cada nó 
G) Os níveis de cada nó 
H) As subárvores de cada nó 
 
Exercício Revisional 
32 
Exercício 
2) Para o slide anterior responda os seguintes itens: 
 A) PósOrdem 
 B) PréOrdem 
 C) InOndem 
 
 
 
Exercício 
3) Uma árvore binária tem 10 nós. Ao percorrer a árvore em pré-
ordem, o resultado é o seguinte: 
 Pré-ordem: J C B A D E F I G H 
 Sendo assim, desenhe a árvore correspondente. 
 
Exercício 
4) Uma árvore binária tem 8 nós. Ao se percorrer a árvore em 
pós-ordem, o resultado é o seguinte: 
 Pós-ordem: F E C H G D B A 
 Sendo assim, desenhe a árvore correspondente. 
 
 
Referências 
 Costa, Alberto. Árvores – Estrutura de Dados. Disponível em: 
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores.htm 
 Costa, Alberto. Árvores – Estrutura de Dados. Disponível em: 
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm 
 COSTA, Patrícia Dockhorn. Estruturas de Dados, Árvores. Slides. 
 Vanessa, Mai-ly. Árvores de Busca. 
 
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/arvores.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm
http://albertocn.sytes.net/2012-2/ed1/aulas/árvores_binarias.htm