Árvores - Fabrício J. Barth

Transcrição

Árvores
Fabrı́cio J. Barth
BandTec - Faculdade de Tecnologia Bandeirantes
Setembro de 2011
Disciplina de Estrutura de Dados e Armazenamento
Tópicos
• Introdução
• Árvores binárias
? Implementação em Java
? Ordens de percurso em árvores binárias
? Altura de uma árvore
• Árvores com número váriavel de filhos
? Implementação em Java
? Altura de uma árvore
? Topologia
Árvores —
Tópicos
Faculdade de Tecnologia Bandeirantes 2
Introdução - Árvore
Um conjunto de nós tal que:
• existe um nó r, denominado raiz, com zero ou mais
sub-árvores, cujas raı́zes estão ligadas a r.
Árvores —
• os nós raı́zes destas sub-árvores são os filhos de r.
• os nós internos da árvore são os nós com filhos.
• as folhas ou nós externos da árvore são os nós sem
filhos.
Árvores —
Árvores Binárias
• uma árvore em que cada nodo tem zero, um ou dois
filhos.
• uma árvore binária é:
? uma árvore vazia, ou;
? um nodo raiz com duas sub-árvores: a sub-árvore
da direita (sad); a sub-árvore da esquerda (sae).
Árvores —
Árvores —
Árvores Binárias - Exemplo
Árvore binária representando expressões aritméticas:
• nós folhas representam operandos
• nós internos operadores
• exemplo: (3 + 6) × (4 − 1) + 5
Árvores —
+
×
5
−
+
3
Árvores —
6
4
1
Árvores binárias - implementação
• A representação de uma árvore é feita através de uma
referência para o nodo raiz da árvore.
• Representação de um nodo da árvore:
1
2
3
4
5
Árvores —
public class Nodo {
private char c;
private Nodo esq;
private Nodo dir;
}
Árvores binárias - implementação
Interface do tipo Árvore
• Nodo criaSemFilhos(char c)
• Nodo criaComFilhos(char c, Nodo esq, Nodo dir)
• boolean vazia(Nodo n)
• boolean pertence(char c, Nodo n)
• void imprime(Nodo n)
Árvores —
Interface do tipo Árvore
Árvores Binárias - implementação
1
2
3
Árvores —
public static Nodo criaSemFilhos(char c) {
return new Nodo(c,null,null);
}
1
2
3
4
5
Árvores —
public static Nodo criaComFilhos(char c,
Nodo esq,
Nodo dir) {
return new Nodo(c,esq,dir);
}
1
2
3
Árvores —
public static boolean vazia(Nodo n) {
return n == null;
}
1
2
3
4
5
6
7
8
Árvores —
public static boolean pertence(char c, Nodo n) {
if(vazia(n))
return false;
else
return c == n.getC() ||
pertence(c,n.getEsq()) ||
pertence(c,n.getDir());
}
1
2
3
4
5
6
7
Árvores —
public static void imprime(Nodo n) {
if(!vazia(n)){
System.out.print(n.getC()+" - ");
imprime(n.getEsq());
imprime(n.getDir());
}
}
Árvores Binárias - exemplo de uso
1
2
3
4
public Main(){
Nodo raiz = ArvoreBinaria.criaComFilhos(’a’,
ArvoreBinaria.criaSemFilhos(’d’),
ArvoreBinaria.criaSemFilhos(’e’));
5
if(ArvoreBinaria.pertence(’f’, raiz))
System.out.println("encontrou");
else
System.out.println("nao encontrou");
6
7
8
9
10
ArvoreBinaria.imprime(raiz);
11
12
Árvores —
}
Árvores Binárias - exemplo de uso
Ordens de percurso em árvores binárias
Árvores —
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Árvores —
public static void imprimePreOrdem(Nodo n) {
if(!vazia(n)){
imprimePreOrdem(n.getEsq());
imprimePreOrdem(n.getDir());
}
}
public static void imprimeInOrdem(Nodo n) {
if(!vazia(n)){
imprimeInOrdem(n.getEsq());
imprimeInOrdem(n.getDir());
}
}
public static void imprimePosOrdem(Nodo n) {
if(!vazia(n)){
imprimePosOrdem(n.getEsq());
imprimePosOrdem(n.getDir());
}
}
Exemplos concretos do uso de árvores
• Estrutura de diretórios e arquivos de um sistema
operacional
• Análise semântica de equações matemáticas
• É uma estrutura usada por vários outros algoritmos...
Árvores —
Exemplos concretos do uso de árvores
Altura de árvore binárias
• Propriedade fundamental de árvores: só existe um
caminho da raiz para qualquer nó.
• Altura de uma árvore: comprimento do caminho mais
longo da raiz até uma das folhas.
? a altura de uma árvore com um único nó raiz é zero
? a altura de uma árvore vazia é -1
Árvores —
• Nı́vel de um nó:
? a raiz está no nı́vel 0, seus filhos diretos estão no
nı́vel 1, ...
? o último nı́vel da árvore é a altura da árvore.
Árvores —
• Árvore cheia:
? todos os seus nós internos tem duas sub-árvores
associadas.
? número n de nós de uma árvore cheia de altura h é
igual a
n = sk+1 − 1
(1)
Árvores —
• Árvore degenerada:
? todos os seus nós internos tem uma única
sub-árvore associada.
? número n de nós de uma árvore cheia de altura h é
igual a
n=h+1
(2)
Árvores —
Árvores com número variável de filhos
Cada nó pode ter mais que duas sub-árvores associadas.
c:/
temp.txt
arquivos/
program/
aqr1.exe
Árvores —
arq2.exe
Árvores com número variável de filhos
usuarios/
arq3.exe
Árvores com até 3 nós
1
2
3
4
5
Árvores —
public class NodoTernario {
private String conteudo;
private NodoTernario[] filhos =
new NodoTernario[3];
}
Árvores com até 3 nós
Procurando por um elemento
1
2
3
4
5
6
7
8
9
10
11
Árvores —
public static boolean pertence(String c, NodoTernario n)
if(vazia(n)) return false; else{
if (c.equals(n.getConteudo())){
return true;
}else{
NodoTernario [] f = n.getFilhos();
for(int i=0; i<f.length; i++){
if(pertence(c,f[i])){return true;}
}
return false;
}}}
Procurando por um elemento
Árvores com até N nós fixos
1
2
3
4
5
Árvores —
public class NodoTernario {
private String conteudo;
private NodoTernario[] filhos =
new NodoTernario[N];
}
Árvores com até N nós fixos
Representação de árvore com número
variável de filhos
Árvores —
Representação de árvore com número variável de filhos
Funções de uma árvore n-ária
• Nodo create(char c)
• void insert(Nodo a, Nodo sub a)
• void print(Nodo a)
• boolean search(Nodo n, char c)
• int getAltura(Nodo n)
Árvores —
Funções de uma árvore n-ária
Nodo de uma árvore n-ária
1
public class Nodo {
2
private char c;
private Nodo prim;
private Nodo prox;
3
4
5
6
7
Árvores —
}
Nodo de uma árvore n-ária
Criação de nodos em uma árvore n-ária
1
2
3
4
5
6
7
Árvores —
public Nodo create(char c){
Nodo n = new Nodo();
n.setC(c);
n.setPrim(null);
n.setProx(null);
return n;
}
Criação de nodos em uma árvore n-ária
Inserção em uma árvore n-ária
1
2
3
4
5
6
7
8
9
Árvores —
/*
* inseri uma nova sub-arvore como filha
* de um dado no
*/
public void insert(Nodo a, Nodo sub_a){
//inserindo no inicio.
sub_a.setProx(a.getPrim());
a.setPrim(sub_a);
}
Inserção em uma árvore n-ária
Impressão de uma árvore n-ária
1
2
3
4
5
6
Árvores —
public void print(Nodo a){
System.out.println(a.getC());
for(Nodo p = a.getPrim(); p!=null; p=p.getProx()){
print(p); //imprime cada sub-arvore filha
}
}
Impressão de uma árvore n-ária
Busca em uma árvore n-ária
1
2
3
4
5
6
7
8
9
10
11
Árvores —
public boolean search(Nodo n, char c){
if(n.getC()==c){
return true;
}else{
for(Nodo p=n.getPrim(); p!=null; p=p.getProx()){
if(search(p,c))
return true;
}
}
return false;
}
Busca em uma árvore n-ária
Atributos de uma árvore n-ária
1
2
3
4
5
6
7
8
9
Árvores —
public int getAltura(Nodo n){
int hmax = -1; /*caso de arvore sem filhos*/
for(Nodo p=n.getPrim(); p!=null; p=p.getProx()){
int h = getAltura(p);
if(h > hmax)
hmax = h;
}
return hmax + 1;
}
Atributos de uma árvore n-ária
Exemplo de construção e utilização de
uma árvore n-ária
1
2
3
4
5
6
7
8
9
Árvores —
public Main(){
//cria nodos como folha
ArvoreNAria arv = new ArvoreNAria();
Nodo a = arv.create(’a’);
Nodo b = arv.create(’b’);
Nodo c = arv.create(’c’);
Nodo d = arv.create(’d’);
Nodo e = arv.create(’e’);
Nodo f = arv.create(’f’);
Exemplo de construção e utilização de uma árvore n-ária
//monta a hierarquia
arv.insert(a, b);
arv.insert(a, c);
arv.insert(c, d);
arv.insert(a, e);
arv.insert(d, f);
1
2
3
4
5
6
7
arv.print(a);
System.out.println(arv.search(a, ’d’));
System.out.println(arv.search(e, ’d’));
System.out.println(arv.getAltura(a));
8
9
10
11
12
Árvores —
}
Exemplo de construção e utilização de uma árvore n-ária
Topologia Binária
• Representação de um nodo de uma árvore n-ária ≡
representação de um nodo de uma árvore binária.
• Um nodo possui a informação que deve ser
armazenada e duas referências para sub-árvores:
? árvore binária: referências para as sub-árvores à
esquerda e à direita.
? árvore n-ária: referências para a primeira
sub-árvore filha e para a sub-árvore irmã.
Árvores —
Topologia Binária
Resumo
• Árvore binária.
• Árvore com número variável de filhos (n-ária).
Árvores —
Resumo
Material de consulta e referência
• Capı́tulo 13 do livro: “Introdução a Estruturas de
Dados” do Waldemar Celes, Renato Cerqueira e José
Lucas Rangel.
• Imagens retiradas do site da disciplina de
Programação II da PUC do Rio de Janeiro
http://www.inf.puc-rio.br/ inf1007/.
Árvores —
Material de consulta e referência

Árvores - Fabrício J. Barth

Transcrição

Documentos relacionados

fisiologia a - Liga Acadêmica de Cardiologia e Cirurgia

Bina Fonyat - Galeria da Gávea

27 de agosto, aniversário de Nascimento de Madre Teresa de

LAR DE SANTOS CELEBRAÇÃO DE BODAS DE DIAMANTE Já

abbccddeeffggooiijjkk nnmmqqtt

Cristina Babino - Universidade de Coimbra

anmmo.

toyota - Ampri

Release – Pedalada – Hospital Bandeirantes

Press Kit | Virada Sustentável 2016

O Projeto Millennium divulga a mais recente edição do relatório O