53
edits
Changes
→Exercícios e Projetos
== Exercícios e Projetos ==
Como proposto pelo professor Umberto Rivechio, da turma XX da disciplina de Fundamentos Matemáticos para a Computação II, período 2016.1, aqui serão implementados dois exercícios em java, sugeridos pelo material original.
1. Desenvolver um método para listar os vértices de uma árvore ordenada com raiz em "level order".
'''''Solução'''''
Para realizar o exercício, vamos implementar a estrutura de dados de uma '''árvore binária''' através de duas classes: a classe '''Arvore''' e a classe '''No'''.
Os vértices da árvore (da classe No) serão ordenados pela sua '''chave''' (int) e armazenarão um inteiro no campo '''valor'''. Além disso, terão campos que guardarão os '''filhos'''. Além do método construtor, criaremos um método para imprimir cada nó da árvore.
Para poder imprimir os valores em level order, será preciso utilizar uma '''fila'''. Podemos utilizar a classe LinkedList do Java.
<pre>
class No {
public int chave;
public int valor;
public No filhoEsquerdo;
public No filhoDireito;
public No(int chave, int valor, No left, No right){
this.chave = chave;
this.valor = valor;
this.filhoEsquerdo = left;
this.filhoDireito = right;
}
public void printLevelOrder(){
System.out.print(this.valor);
LinkedList<No> nos = new LinkedList<>();
if(this.filhoEsquerdo != null)
nos.add(this.filhoEsquerdo);
if(this.filhoDireito!= null)
nos.add(this.filhoDireito);
while(!nos.isEmpty()){
No n = nos.remove();
System.out.print(", " + n.valor);
if(n.filhoEsquerdo != null)
nos.add(n.filhoEsquerdo);
if(n.filhoDireito != null)
nos.add(n.filhoDireito);
}
}
}
</pre>
A classe Arvore guardará a raiz da árvore.
Temos um método para inserir os valores de forma que a árvore continue ordenada.
<pre>
class Arvore {
public No raiz;
public Arvore(){
this.raiz = null;
}
public void inserir(int chave, int valor){
No n = raiz;
No pai = null;
while(n != null){
if(n.chave > chave) {
pai = n;
n = n.filhoEsquerdo;
} else if (n.chave < chave){
pai = n;
n = n.filhoDireito;
} else {
return;
}
}
if(pai == null){
this.raiz= new No(chave, valor, null, null);
} else {
if(pai.chave > chave)
pai.filhoEsquerdo = new No(chave, valor, null, null);
else
pai.filhoDireito = new No(chave, valor, null, null);
}
}
public void printLevelOrder(){
if(raiz != null)
raiz.printLevelOrder();
System.out.println();
}
}
</pre>
Se rodarmos o seguinte código:
<pre>
Arvore a = new Arvore();
a.inserir(5, 10);
a.inserir(6, 12);
a.inserir(3, 6);
a.inserir(7, 14);
a.inserir(1, 2);
a.inserir(9, 18);
a.inserir(4, 8);
a.printLevelOrder();
</pre>
Obtemos o seguinte resultado:
<pre>
10, 6, 12, 2, 8, 14, 18
</pre>
== Referências ==
Rosen, Kenneth H. (2002). "[http://www.mhhe.com/math/advmath/rosen/r5/student/ch09/maple.html Discrete Mathematics and Its Applications]". Material de apoio. Suplemento do Maple para o capítulo 9. Acesso em 29 de Maio de 2016.