02. Arvores

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

Árvores
Estrutura de Dados II
Introdução
Em diversas aplicações necessita-se de estruturas mais complexas que as estruturas sequenciais de listas, filas e pilhas
6
2
7
Topo
6
2
7
Início
Fim
ptlista
λ
7
6
2
Introdução
Por exemplo, como representar um sistema de arquivos, pastas e discos de um computador usando uma lista linear?
C:\
Docs
Imgs
Topo
Docs
Imgs
C:\
Início
Fim
ptlista
λ
C:\
Docs
Imgs
Introdução
Árvores são estruturas de dados apropriadas para representar hierarquias
Sistema de arquivos
C:\
Softs
Docs
Imgs
Sys
Prog
Com
Geral
Aulas
C++
ED
Introdução
Árvores são estruturas de dados apropriadas para representar hierarquias
Expressões aritméticas
/
e
*
b
+
-
c
d
a
((a+b) * (c-d)) / e
Introdução
Estruturas hierárquicas aparecem em muitos problemas computacionais:
Gramática das linguagens de programação e de marcação como XML/HTML
O formato de vários tipos de arquivos: doc, pdf, etc. 
As possibilidades de movimento em jogos de xadrez
As relações nas redes sociais
Animação de objetos/esqueletos na computação gráfica
Árvore de decisão é uma técnica de IA bastante utilizada
Árvores
Das estruturas não sequenciais, as árvores são as mais importantes:
Existem diversos problemas práticos que podem ser modelados por árvores
Elas admitem um tratamento computacional simples e eficiente
Para usar árvores é necessário:
Criar uma representação computacional
Construir os algoritmos de manipulação
Esse é nosso objetivo final, mas para alcança-lo vamos primeiro estudar os conceitos básicos.
7
Árvores
Definição: uma árvore T é um conjunto de nós (vértices) interligados por linhas (arestas), sem formar ciclos:
Árvore
Não é árvore
Árvore
Árvores
Uma árvore T:
Se não contem nós, é chamada de árvore vazia
Se possui apenas um nó, este é chamado de nó raiz
Possui um nó raiz e os demais são subdivididos em sub-árvores do nó raiz, de forma que cada sub-árvore também é uma árvore
r
Terminologia
Se no caminho da raiz para um vértice w, o vértice v precede imediatamente o vértice w, então v é chamado pai de w, e w é filho de v
w
r
v
pai
filho
Terminologia
Vértices com o mesmo pai são chamados de irmãos
w
r
v
irmãos
y
x
pai
Terminologia
Um vértice w é descendente de um vértice v, se v está no caminho da raiz ao vértice w (v é ancestral de w)
r
v
descendente
ancestral
w
Terminologia
Uma folha é um nó que não possui filhos
Um ramo é um nó com todos os seus descendentes
Se uma folha ou ramo é removido de uma árvore, o resultado continua 
sendo uma árvore
y
x
v
z
w
folha
ramo
Remoção de um ramo
x
v
Árvore
Terminologia
Designando-se uma raiz para um árvore, impõe-se uma hierarquia nos vértices, de acordo com as distâncias até a raiz:
O nível de um vértice é o número de vértices no caminho até a raiz
A altura é o número de vértices no caminho mais longo até seus descendentes
v
u
t
r
w
y
x
Nível 1
Nível 2
Nível 3
Nível 4
Altura da árvore é a altura da raiz
Árvore com altura 4
14
Terminologia
Um vértice interno é qualquer vértice que tenha pelo menos um filho
A raiz é um vértice interno, a não ser que a árvore seja trivial
v
r
x
Vértices internos:
r, v, x
trivial = possua apenas um vértice
15
EXERCÍCIO
1) Encontre a altura da árvore, vértices internos e folhas. 
2) Mostre exemplos de irmãos, ancestrais e descendentes.
r
c
b
a
f
g
d
j
e
h
i
Altura: 4
Internos: r, a, b, c, d
Folhas: e, f, g, h, i, j
Irmãos: g, h, i
a é ancestral de j
j é descendente de a
trivial = possua apenas um vértice
16
Tipos de árvores
Uma árvore m-ária é uma árvore enraizada em que todo vértice tem no máximo m filhos
r
Árvore 3-ária 
(ternária)
r
Árvore 2-ária 
(binária)
As árvores binárias são especialmente importantes para a computação e será nosso foco daqui para frente.
17
Árvores Binárias
As árvores binárias estão entre as estruturas de dados mais utilizadas na computação
Definição: uma árvore binária é uma árvore 2-ária em que cada filho é 
classificado como filho esquerdo 
ou filho direito.
r
Árvore binária 
com altura 3
18
Visão Recursiva
Uma árvore binária consiste de uma raiz e uma sub-árvore esquerda e direita, que são também árvores binárias.
r
sub-árvore 
esquerda
sub-árvore 
direita
Tipos de Árvores Binárias
Uma árvore estritamente binária é uma árvore binária em que cada nó possui zero ou dois filhos.
r
Árvore Binária
Árvore Estritamente
Binária
r
Tipos de Árvores Binárias
Uma árvore binária completa é aquela em que se um nó possui alguma 
sub-árvore vazia, ele se encontra no último ou penúltimo nível da árvore
Árvore Binária 
Completa
r
Árvore Estritamente
Binária
r
Tipos de Árvores Binárias
Uma árvore binária cheia é aquela em que se um nó possui alguma 
sub-árvore vazia, ele se encontra no último nível da árvore
Árvore Binária 
Completa
r
Árvore Binária 
Cheia
r
Não existe uma padronização destes termos na literatura. Drozdek chama a árvore cheia de completa. Tabenbaum chama a completa de quase completa e a cheia de completa.
22
Tipos de Árvores Binárias
Em uma árvore binária ziguezague todos os nós tem exatamente um filho
r
r
r
Representação Computacional
O armazenamento de árvores pode utilizar alocação sequencial ou encadeada
Sendo uma árvore uma estrutura intrinsecamente não sequencial, a solução mais natural é com alocação encadeada
Com alocação encadeada, cada nó deve conter ponteiros para seus filhos
a
b
c
b
Exercício 3.30 do livro do Jayme possui uma proposta para armazenamento sequencial de árvores.
24
Representação Computacional
Em uma árvore binária cada nó deve possuir dois ponteiros: esq e dir
O ponteiro ptraiz indica a raiz da árvore
A
B
C
D
G
ptraiz
λ
λ
E
λ
λ
H
λ
λ
I
λ
λ
F
λ
λ
λ
Lambda representa um valor nulo para o ponteiro, nullptr em C++.
25
Percurso em Árvore Binária
Um percurso na árvore é uma visita sistemática à cada vértice da árvore
Um percurso estabelece uma ordem aos vértices da árvore
São quatro os principais tipos de percurso em árvores binárias:
Nível
Pré-ordem	
Pós-ordem
Simétrico
Percurso em Nível
O percurso em nível obtém uma listagem dos vértices por nível da árvore 
Ele é feito de cima para baixo e da esquerda para a direita
r
b
a
e
j
f
g
c
d
h
i
k
Percurso em nível:
r a b c d e f g h i j k
Implementação
Algoritmo: Percurso em nível (usando filas)
 enfileirar raiz
 enquanto fila não estiver vazia faça
 | desenfileirar vértice v
 | visitar vértice v
 | enfileirar filhos de v (da esquerda para direita)
r
b
a
e
j
f
g
c
d
h
i
k
Percurso em nível:
r a b c d e f g h i j k
Percurso Pré, Pós e Simétrico
O percurso em pré-ordem, pós-ordem e simétrico utilizam a visão recursiva da árvore para percorrê-la
r
sub-árvore 
esquerda
sub-árvore 
direita
Percurso em Pré-ordem
O percurso em pré-ordem é definido recursivamente na árvore:
Visita a raiz de T
Faz o percurso em pré-ordem da sub-árvore esquerda de T
Faz o percurso em pré-ordem da sub-árvore direita de T
Percurso em pré-ordem:
r a c g d h i k b e j f
r
b
a
e
j
f
g
c
d
h
i
k
Percurso em Pós-ordem
O percurso em pós-ordem é definido recursivamente na árvore:
Faz o percurso em pós-ordem da sub-árvore esquerda de T
Faz o percurso em pós-ordem da sub-árvore direita de T
Visita a raiz de T
Percurso em pós-ordem:
g c h k i d a j e f b r
r
b
a
e
j
f
g
c
d
h
i
k
Percurso em Ordem Simétrica
O percurso em ordem simétrica é definido recursivamente na árvore:
Faz o percurso em ordem simétrica da sub-árvore esquerda de T
Visita a raiz de T
Faz o percurso em ordem simétrica da sub-árvore direita de T
Percurso em ordem simétrica:
c g a h d k i r j e b f
r
b
a
e
j
f
g
c
d
h
i
k
Resumo
Árvores são estruturas de dados hierárquicas composta por um conjunto de vértices interligados por arestas, sem formar ciclos
As árvores binárias possuem várias aplicações
e estão entre as estruturas de dados mais utilizadas da computação
As árvores binárias podem ser percorridas de diferentes formas:
Nível
Pré-ordem	
Pós-ordem
Simétrico