PTI-estrutura-de-dados

Prévia do material em texto

(Item A) 
public class No { 
private long id; 
private Object elemento; 
private No esq; 
private No dir; 
public No(long id, Object elemento, No esq, No dir) { 
this.id = id; 
this.elemento = elemento; 
this.esq = esq; 
this.dir = dir;} 
public void setId(long id) { this.id = id;} 
public long getId() { return this.id;} 
public void setElemento(Object elemento) { this.elemento = elemento;} 
public Object getElemento() { return elemento;} 
public void setEsq(No esq) { this.esq = esq;} 
public No getEsq() { return esq;} 
public void setDir(No dir) { this.dir = dir;} 
public No getDir() { return dir;}} 
 
public class ArvoreBinaria { 
private No raiz; 
Integer esquerda = 0; 
public ArvoreBinaria() { 
this.raiz = null; } 
public void insere(long id, Object elemento) { No novoNo = new No(id, 
elemento, null, null); 
if (raiz == null) { 
raiz = novoNo; 
} else { 
No atual = raiz; 
No pai; 
while (true) { 
pai = atual; 
if (id < atual.getId()) { 
atual = atual.getEsq(); 
if (atual == null) { pai.setEsq(novoNo); 
return; 
} 
} else { atual = atual.getDir(); 
if (atual == null) { pai.setDir(novoNo); 
return; 
}}}}} 
private void preFixado(No atual) {if (atual != null) { 
System.out.println("Id: "+atual.getId()+" Elemento: "+atual.getElemento()); 
preFixado(atual.getDir()); 
preFixado(atual.getEsq()); 
if(atual.getEsq() != null) { 
esquerda++;}}} 
public void imprimeElementosArvore() { 
preFixado(raiz); 
System.out.println("Total de nós a esquerda: " + esquerda); 
}} 
public class ExemploArvoreBinaria { 
public static void main(String[] args) { 
ArvoreBinaria a = new ArvoreBinaria(); 
a.insere(6, "A"); 
a.insere(10, "B"); 
a.insere(11, "C"); 
a.insere(12, "D"); 
a.insere(8, "E"); 
a.insere(9, "F"); 
a.insere(7, "G"); 
a.insere(2, "H"); 
a.insere(4, "I"); 
a.insere(1, "J"); 
a.insere(3, "K"); 
a.insere(5, "L"); 
a.imprimeElementosArvore(); 
}} 
(Item B) 
public class No { 
private long id; // identificador do elemento 
private Object elemento; // armazena o elemento de cada No 
private No esq; // aponta para o filho esquerdo do nó 
private No dir; // aponta para o filho direito do nó,, 
public No (long id, Object elemento, No esq, No dir) { 
this.id = id; 
this.elemento = elemento; 
this.esq = esq; 
this.dir = dir; 
} 
public void setId(long id) { 
this.id = id; 
} 
public long getId() { 
return this.id; 
} 
public void setElemento(Object elemento) { 
this.elemento = elemento; 
} 
public Object getElemento() { 
return elemento; 
} 
public void setEsq(No esq) { 
this.esq = esq; 
} 
public No getEsq(){ 
return esq; 
} 
public void setDir(No dir) { 
this.dir = dir; 
} 
public No getDir() { 
return dir; 
}} 
public class ArvoreBinaria { 
private No raiz; 
Integer contador = 0; 
String espaco = "\t"; 
public ArvoreBinaria() {this.raiz = null; 
} 
public void insere(long id, Object elemento) { 
No novoNo = new No(id,elemento,null,null); 
if (raiz == null) { 
raiz = novoNo; 
} else { 
No atual = raiz; No pai; 
while (true) { 
pai = atual; 
if (id < atual.getId()) { 
atual = atual.getEsq(); 
if (atual == null) { 
pai.setEsq(novoNo); 
return; 
} 
} else { 
atual = atual.getDir(); 
if (atual == null) { 
pai.setDir(novoNo); 
return; 
}}}}} 
private void preFixado(No atual) { 
String repete = new String(new 
char[contador]).replace("\0", espaco); 
if (atual != null) { 
contador++; 
System.out.println(repete + atual.getId()); 
preFixado(atual.getEsq()); 
preFixado(atual.getDir()); 
contador--;} 
if(atual == null){ 
System.out.println(repete+"-"); 
}} 
public void imprimeElementosArvore() { 
preFixado(raiz); 
} 
private long calcAltura(No atual, long a) { 
if (atual != null) { 
long e,d; 
e = calcAltura(atual.getEsq(),a)+1; 
d = calcAltura(atual.getDir(),a)+1; 
if (e > d) { 
return a+e; 
} else { 
return a+d; 
}} 
return a; 
} // final método calcAltura 
private long calcEsq(No atual, long a) { 
if (atual != null) { 
long e,d; 
e = calcEsq(atual.getEsq(),a)+1; 
return a+e; 
} 
return a; 
} 
public long alturaArvore() { 
long a = 0; 
System.out.println(" "); 
return calcAltura(raiz,a); 
} 
public long totalEsquerda(){ 
long es = 0; 
return calcEsq(raiz, es); 
}} 
public class ExemploArvoreBinaria { 
public static void main(String[] args) { 
ArvoreBinaria a = new ArvoreBinaria(); 
a.insere(555,"A"); 
a.insere(333,"B"); 
a.insere(111,"C"); 
a.insere(444,"D"); 
a.insere(888,"E"); 
a.insere(999,"F"); 
a.imprimeElementosArvore(); 
}}