Árvores
Bruno Silva
Contexto
• Árvore, no contexto da programação e ciência
da computação, é uma estrutura de dados que
herda as características das topologias em
árvore.
• Servem para criação de estruturas
hierárquicas.
• Exemplo estrutura de diretórios do
computador.
Conceitos básicos
• Uma árvore é composta de um conjunto finito de
Nós.
• Desse conjunto, há um nó r denominado de raiz, que
contém zero ou mais sub-árvores, cujas raízes são
ligadas diretamente a r.
• Esses nós raízes das sub-árvores são ditos filhos do
nó pai, r.
• Nós com filhos são chamados de nós
internos.
• Nós que não têm filhos são chamados de nós
externos (folhas).
Propriedades
• Existe um único caminho da raiz para
qualquer nó da árvore.
• Portanto, podemos definir a altura da árvore
como sendo o comprimento do caminho mais
longo da raiz até uma das folhas.
• A altura de uma árvore que possui somente
um elemento é zero.
Árvore Binária
• Constituida por dois nós
– SAD: Sub árvore direita.
– SAE: Sub árvore esquerda.
class Arvore{
Object objeto;
Arvore sae;
Arvore sad;
};
//Esse objeto pode ser de qualquer tipo
Principais Funções
•
•
•
•
Inserir.
Remover.
Consultar.
Varrer elementos.
– Pré-ordem
– Em-odem
– Pós-ordem
Percorrendo uma árvore.
• 3 tipos de percurso
– Pré-Ordem: tratar raiz, percorrer sae, percorrer
sad;
– Em-Ordem : percorrer sae, tratar raiz, percorrer
sad;
– Pós-Ordem: percorrer sae, percorrer sad, tratar
raiz.
Pré-Ordem
• Imprima os valores presentes nos
nós da árvore ao lado em pré
ordem.
A
B
C
public void preOrdem(ArvoreNo no) {
if(no != null){
System.out.print(no.getInfo()+" ");
preOrdem(no.getNoE());
preOrdem(no.getNoD());
}
}
Resultado: A, B,C, D, E, F, G, H, I, J, K, L
I
D
E
J
H
F
G
K
L
Pós-Ordem
• Imprima os valores presentes nos
nós da árvore ao lado em pós
ordem.
A
B
public void posOrdem(ArvoreNo no) {
if(no != null){
posOrdem(no.getNoE());
posOrdem(no.getNoD());
System.out.print(no.getInfo()+" ");
}
}
Resultado: C, G, F, E, H, D, B, K, L, J, I, A
C
I
D
E
J
H
F
G
K
L
Em-Ordem
• Imprima os valores presentes nos
nós da árvore ao lado em ordem.
A
B
public void emOrdem(ArvoreNo no) {
if(no != null) {
emOrdem(no.getNoE());
System.out.print(no.getInfo()+" ");
emOrdem(no.getNoD());
}
}
Resultado: C, B, F, G, E, D, H, A, I, K, J, L
C
I
D
E
J
H
F
G
K
L
Consulta de nós (1)
• Consulta com sucesso.
• Exemplo: Na ABP abaixo, consultar os dados referenciados
pelo nó de valor 3.
4
4
1
6
3
2
5
1
7
3
Consulta de nós (2)
• Consulta sem sucesso.
• Exemplo: Na ABP abaixo, consultar os dados referenciados
pelo nó de valor 9.
4
4
1
6
3
2
5
6
7
7
Inserção de nós (1)
• A ordem em que os valores são inseridos é relevante.
– Exemplo 1: Inserir os nós 13 e 15.
– Exemplo 2: Inserir os nós 15 e 13.
raiz 10
raiz 10
2
1
8
3
7
2
12
9
16
4
16
4
1
11
8
3
7
12
9
11
13
15
15
13
Algoritmo de Inserção
public void Inserir(No novo, No anterior){
if (anterior != null){
if (novo.ObtemValor() < anterior.ObtemValor())
inicio.filho_Esq=this.Insere(novo, anterior.filho_Esq
else
if(novo.ObtemValor()>anterior.ObtemValor())
anterior.p_Dir=this.Insere(filho, anterior.filho_Dir
else
return;
}else
anterior = novo;
}
Inserção de nós (2)
• Exemplo: Construir uma ABP a partir da seguinte lista de valores:
5,2,7,6,4,3 e 8.
5
2
7
4
3
6
8
Remoção de nós – Caso 1
• Caso 1: nodo a ser removido tem zero filhos
– Apenas remove o nodo (Remover 3)
5
5
2
4
3
2
7
6
8
7
4
6
8
Remoção de nós – Caso 2
• Caso 2: no a ser removido tem um filho
–
Substitui o nó por seu filho
5
5
10
2
4
3
10
2
13
6
12
4
3
6
12
Remoção de nós – Caso 3
• Caso 3: Nó a ser removido tem dois filhos
–
Substitui o nó por seu sucessor
raiz 11
raiz 11
17
5
9
3
2
4 8
9
3
13
10
17
8
2
4
13
10
Após a remoção
Nó sucessor
• Considerando que as chaves sejam todas
distintas:
• O sucessor de um nodo x é o nodo y, tal que
chave[y] é o menor valor maior que chave[x].