PTI - estrutura de dados

Prévia do material em texto

ARVORE DE DADOS
Item A)
// Implementacao da classe No de uma árvore
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) {// construtor da classe No this.id = id;
this.elemento = elemento; this.esq = esq;
this.dir = dir;
}
public void setId(long id) { // método para alterar o identificador do nó this.id = id;
}
public long getId() { // método para receber o identificador do nó return this.id;
}
public void setElemento(Object elemento) { // método para alterar o elemento this.elemento = elemento;
}
public Object getElemento() { // método para receber o objeto contido no No return elemento;
}
public void setEsq(No esq) { // método que altera o filho esquerdo this.esq = esq;
}
public No getEsq() { // método que recebe o filho esquerdo do nó return esq;
}
public void setDir(No dir) { // método que altera o filho direito this.dir = dir;
}
public No getDir() { // método que recebe o filho direito do nó return dir;
}
}
// Final da classe No
// Implementação da classe árvore binária, com construtor e o método insere() public class ArvoreBinaria {
private No raiz; Integer esquerda = 0;
public ArvoreBinaria() { // construtor da classe Arvore Binaria
this.raiz = null; // inicia a árvore vazia
}
public void insere(long id, Object elemento) { // método para inserção de 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()) { // vai inserir à esquerda atual = atual.getEsq();
if (atual == null) { // pode inserir à esquerda pai.setEsq(novoNo);
return;
} // se não é nulo, vai tentar o próximo filho
} else { // vai inserir à direita atual = atual.getDir();
if (atual == null) { // pode inserir à direita pai.setDir(novoNo);
return;
}
}
}
}
}
// final método insere
}
binária
private void preFixado(No atual) {// caminhamento pré-fixado da árvore
if (atual != null) {
System.out.println("Id: "+atual.getId()+" Elemento: "+atual.getElemento()); preFixado(atual.getDir());
Prefixado(atual.get Esq()); if(atual.getEsq() != null) {
esquerda++;
}
}
}
// final método preFixado
public void imprimeElementosArvore() { // impressão dos elementos da árvore preFixado(raiz);
System.out.println("Total de nós a esquerda: " + esquerda);
}
// final do método para impressão
// Final da classe ArvoreBinaria+-
//Criação da arvore binária
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)
// Implementação da classe No de uma árvore 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) { // construtor classe No this.id = id;
this.elemento = elemento; this.esq = esq;
this.dir = dir;
}
public void setId(long id) { // método para alterar o identificador do nó this.id = id;
}
public long getId() { // método para receber o identificador do nó return this.id;
}
public void setElemento(Object elemento) { // método para alterar o elemento this.elemento = elemento;
}
public Object getElemento() { // método para receber o objeto contido no No return elemento;
public void setEsq(No esq) { // método que altera o filho esquerdo this.esq = esq;
}
public No getEsq(){ // método que recebe o filho esquerdo do nó return esq;
}
public void setDir(No dir) { // método que altera o filho direito this.dir = dir;
}
public No getDir() { // método que recebe o filho direito do nó return dir;
}
}
// Final da classe No
// Implementação da classe árvore binária, com construtor e o método insere()
public class ArvoreBinaria { private No raiz;
Integer contador = 0; String espaco = "\t";
public ArvoreBinaria() {// construtor da classe Arvore Binaria
this.raiz = null; // inicia a árvore vazia
}
public void insere(long id, Object elemento) { // método para inserção de 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()) { // vai inserir à esquerda atual = atual.getEsq();
if (atual == null) { // pode inserir à esquerda pai.setEsq(novoNo);
return;
} // se não é nulo, vai tentar o próximo filho
} else { // vai inserir à direita atual = atual.getDir();
if (atual == null) { // pode inserir à direita pai.setDir(novoNo);
return;
}
}
}
} // final método insere
private void preFixado(No atual) { // caminhamento pré- fixado da árvore binária
//Esse objeto e usado para somar e subtrair valor da variavel contador
String repete = new String(new char[contador]).replace("\0", espaco);
if (atual != null) { contador++;
//a variavel repete aqui e usado para determinar a posição da raiz
System.out.println(repete + atual.getId()); preFixado(atual.getEsq()); preFixado(atual.getDir());
contador--;
}
if(atual == null){ System.out.println(repete+"-");
}
}
// final método preFixado
public void imprimeElementosArvore() { // impressão dos elementos da árvore
preFixado(raiz);
} // final do método para impressão
private long calcAltura(No atual, long a) { // calcula a altura da árvore
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) { // calcula a esq if (atual != null) {
long e,d;
e = calcEsq(atual.getEsq(),a)+1; return a+e;
return a;
}
// final método calcEsq
public long alturaArvore() { long a = 0;
System.out.println(" "); return calcAltura(raiz,a);
} // final do método alturaArvore
public long totalEsquerda(){ long es = 0;
return calcEsq(raiz, es);
}
// final método totalEsquerda
}
// Final da classe ArvoreBinaria
//Teste Arvore Binária
public class ExemploArvoreBinaria { public static void main(String[] args) {
ArvoreBinaria a = new ArvoreBinaria(); // cria a árvore binária 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();
}
}