AEDII-aula07

Prévia do material em texto

1
Aula 07 – Árvores binárias: algoritmos 
de varredura
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Árvores
São estruturas não 
lineares.
Representação natural 
para dados aninhados.
Muito úteis para 
resolver uma enorme 
variedade do problema 
envolvendo algoritmos.
Não é uma árvore
3
Árvores de pesquisa
A árvore de pesquisa é uma estrutura muito eficiente para 
armazenar informação.
Apropriada quando existe necessidade de considerar todos 
ou alguma combinação de:
Acesso direto e sequencial eficientes.
Facilidade de inserção e retirada de elementos.
Boa taxa de utilização de memória.
Utilização de memória principal e secundária.
4
Árvores binárias
5
Árvores binárias
Uma árvore é uma estrutura de dados mais geral que uma 
lista ligada.
Nessa aula examinaremos operações “mais simples” sobre 
árvores binárias.
6
Nós e filhos
Uma árvore binária (=binary trees) é um conjunto de registros 
que satisfaz certas condições.
7
Nós e filhos
Uma árvore binária (=binary trees) é um conjunto de registros 
que satisfaz certas condições.
Os registros serão chamados de nós (poderiam também ser 
chamadas de células)
Cada nó tem um endereço.
Suporemos que por enquanto cada nó tem 3 campos:
Um número inteiro.
Dois ponteiros para nós.
8
Nós e filhos
9
Nós e filhos
“Carga útil”
Campos que dão
estrutura à árvore
10
Nós e filhos
“Carga útil”
Campos que dão
estrutura à árvore
→ O nó folha (=leaf) é um nó que não tem filho algum.
→ Se x tiver um pai, essa árvore é uma subárvore de alguma árvore maior.
11
Nós e filhos
“Carga útil”
Campos que dão
estrutura à árvore
→ O nó folha (=leaf) é um nó que não tem filho algum.
→ Se x tiver um pai, essa árvore é uma subárvore de alguma árvore maior.
12
Varredura
13
Varredura
Muitos algoritmos sobre árvores ficam mais simples 
quando escritos de forma recursiva.
14
Varredura
Ao contrário de uma lista encadeada, uma árvore binária 
pode ser percorrida de muitas maneiras diferentes.
Uma maneira particularmente importante é a ordem 
esquerda-raiz-direita (e-r-d)
(=inorder traversal =percurso em inorder ) 
A subárvore esquerda da raiz, em ordem e-r-d;
depois a raiz;
depois a subárvore direita da raiz, em ordem e-r-d.
15
Varredura
Na figura abaixo, os nós estão numeradas na ordem da 
varredura e-r-d. 
16
Varredura
Uma função recursiva que faz a varredura e-r-d de uma 
árvore binária r:
17
Varredura
Uma função recursiva que faz a varredura e-r-d de uma 
árvore binária r:
 Exercício: escrever uma versão iterativa desta função
18
Varredura
19
Varredura
20
Varredura
A versão usa uma pilha p[0..t-1] de endereços e mais um 
endereço x que é candidato a entrar na pilha; é como se a pilha 
fosse
p[0], p[1], . . . , p[t-1], x .
A sequência x, p[t-1], . . . , p[0] é uma espécie de "roteiro" daquilo 
que ainda precisa ser feito: 
x representa a instrução "imprima a árvore x" e 
cada p[i] representa a instrução "imprima o nó p[i] e em seguida 
a árvore p[i]->dir". 
Para dimensionar a pilha, suporemos que nossa árvore não tem 
mais que 100 nós. 
21
Varredura
P
I
L
H
A
Dados impressos
22
Varredura
Exercício: Verifique que o código abaixo é equivalente ao 
da função e-r-d.
23
Exercícios
(1) Escreva uma função que calcule o número de nós de uma 
árvore binária.
(2) Escreva uma função que imprima, em ordem e-r-d, os 
conteúdos das folhas de uma árvore binária.
(3) Dada uma árvore binária, encontrar um nó da árvore cujo 
conteúdo tenha um certo valor k.
(4) Crie uma função para encontrar o endereço do primeiro 
no na órdem e-r-d.
24
Primeiro e último nó
25
Altura de uma árvore
A altura de um nó x em uma árvore binária é a distância entre x e 
o seu descendente mais afastado. 
A altura de uma árvore é a altura da raiz da árvore. 
Uma árvore com um único nó tem altura 0. 
A árvore da figura tem altura 3.
Crie uma função que calcule a altura de uma árvore.
26
Altura de uma árvore
27
Exercícios-Problema (EPs) para esta semana
UVA 12406 – Help Dexter 
UVA 195 – Anagram 
Data: 25/Julho (sexta-feira) até às 23h50.
Arquivos: 
Para cada exercício-problema deverá submeter:
O código fonte: nome do arquivo → RA_nroDoProblema.cpp
O comprovante de aceitação (Uva) → RA_nroDoProblema.pdf
Exemplo: 10123456_11567.cpp
 10123456_11567.pdf
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27