03. Arvores Binarias

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

Árvores Binárias
Estrutura de Dados II
Aplicação
Uma árvore binária é a estrutura mais natural para a representação de uma expressão aritmética
Uma expressão aritmética pode ser representada recursivamente como:
O operador está na raiz
A sub-árvore esquerda é uma expressão representando o operando esquerdo
A sub-árvore direita é uma expressão representando o operando direito
Aplicação
Quando a árvore é percorrida, a expressão resultante aparecerá em notação prefixa, posfixa ou infixa
/
e
*
b
+
-
c
d
a
Expressão: ((a+b) * (c-d)) / e
Implementação
Algoritmo: Percurso em pré-ordem (recursivo)
 procedimento pre(pt)
 | visita(pt)
 | se ptesq ≠ λ então pre(ptesq)
 | se ptdir ≠ λ então pre(ptdir)
 se ptraiz ≠ λ então pre(ptraiz)
Ordem de visitas: 
/ * + a b – c d e
/
*
e
+
-
a
b
c
d
ptraiz
Implementação
Algoritmo: Percurso em pós-ordem (recursivo)
 procedimento pos(pt)
 | se ptesq ≠ λ então pos(ptesq)
 | se ptdir ≠ λ então pos(ptdir)
 | visita(pt)
 se ptraiz ≠ λ então pos(ptraiz)
Ordem de visitas: 
a b + c d - * e /
/
*
e
+
-
a
b
c
d
ptraiz
Implementação
Algoritmo: Percurso em ordem simétrica (recursivo)
 procedimento simet(pt)
 | se ptesq ≠ λ então simet(ptesq)
 | visita(pt)
 | se ptdir ≠ λ então simet(ptdir)
 se ptraiz ≠ λ então simet(ptraiz)
Ordem de visitas: 
((a + b) * (c – d)) / e
/
*
e
+
-
a
b
c
d
ptraiz
Implementação
Algoritmo: Percurso em pré-ordem (usando pilha)
 inserir raiz na pilha
 enquanto pilha não estiver vazia faça
 | remover vértice v da pilha
 | visitar vértice v
 | inserir filhos de v na pilha (da direita pra esquerda)
/
Topo
e
*
Topo
e
-
+
Topo
Ordem de visitas: 
/ * + a b – c d e
/
e
*
b
+
-
c
d
a
Representação de árvores
Na representação de árvores binárias, tem-se um grande número de ponteiros (dir e esq) sem informação relevante (λ)
A
B
C
D
G
ptraiz
λ
λ
E
λ
λ
H
λ
λ
I
λ
λ
F
λ
λ
λ
Árvores com Costura
A idéia da árvore com costura é utilizar esses ponteiros nulos para guardar alguma informação útil
A
B
C
D
G
ptraiz
λ
λ
E
λ
λ
H
λ
λ
I
λ
λ
F
λ
λ
λ
Que tipo de informação poderia ser guardada nestes campos?
9
Árvores com Costura
Acelerando o percurso em árvores binárias usando costuras
Dado um nó v, se o conteúdo do seu ponteiro esq é nulo, este pode ser substituído por um ponteiro para o antecessor de v no percurso
Dado um nó v, se o conteúdo do seu ponteiro dir é nulo, este pode ser substituído por um ponteiro para o sucessor de v no percurso
Para diferenciar um ponteiro normal de uma costura é preciso introduzir dois novos campos booleanos em cada nó
Árvores com Costura
Árvore com costuras para percurso simétrico
A
B
C
D
G
ptraiz
E
λ
H
I
F
0
0
0
1
0
0
1
0
1
1
1
1
1
1
0
0
1
1
1
0
Árvores com Costura
Percurso em ordem simétrica com costura
A
B
C
D
G
ptraiz
E
λ
H
I
F
0
0
0
1
0
0
1
0
1
1
1
1
1
1
0
0
1
1
1
0
Algoritmo: Sucessor em ordem simétrica
 função suc(raiz)
 | pt := raizdir
 | se raizcosturaD = 0 então
 | | enquanto ptcosturaE = 0 faça
 | | | pt := ptesq
 | retorna pt
O percurso é feito por sucessivas chamadas ao sucessor, iniciando de ptraiz. A visita acontece após a chamada ao procedimento sucessor.
12
Resumo
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
O percurso em árvores binárias pode ser acelerado com costuras
Adicionando um custo extra no uso de memória