Galera,
Estou a um tempo sem postar aqui no GUJ porque estou num corre-corre grande. Voltei ao minha rotina de estudos e agora surgiu uma dúvida. Estou estudando estrutura de dados e estou na parte de Arvores Binárias. Lendo uma apostila que eu peguei na net me deparei com um desafio interessante:
Transformar uma expressão(string) matemática em uma árvore.
Ex1.: x+y
/
x y
Ex2.: x+(y*z)
/
x *
/
y z
Como essa segunda arvore ficou mal desenhada vou explicar:
O nó (+) tem os filhos (x) e ();
O nó () tem os filhos (y) e (z);
Como eu não sabia nada de árvores fiz a implementação dela, só que eu não consegui caminhar com o desafio acima. Sinceramente não consegui nem imaginar como fazer isso. Tô todo confuso! Podem me ajudar? Me deêm uma luz!
Vejam minha árvore:
[code]public class ArvoreBinaria
{
private int qNos;
private int qNiveis;
public void inserir(Celula raiz, char elemento)
{
if (elemento < raiz.getElemento())
{
if (raiz.getEsquerda() != null)
{
inserir(raiz.getEsquerda(), elemento);
} else
{
System.out.println("Foi inserido " + elemento + " a esquerda de "
+ raiz.getElemento());
Celula c = new Celula(elemento);
c.setPai(raiz);
raiz.setEsquerda(c);
System.out.println("O pai de " + elemento + " é:" + raiz.getElemento());
System.out.println(" ");
}
} else if (elemento > raiz.getElemento())
{
if (raiz.getDireita() != null)
{
inserir(raiz.getDireita(), elemento);
} else
{
System.out.println("Foi inserido " + elemento + " a direita de "
+ raiz.elemento);
Celula c = new Celula(elemento);
c.setPai(raiz);
raiz.setDireita(c);
System.out.println("O pai de " + elemento + " é:" + raiz.getElemento());
System.out.println(" ");
}
}
}
public void preOrdem(Celula raiz)
{
if (raiz != null)
{
System.out.println(" Elemento: " + raiz.getElemento());
preOrdem(raiz.getEsquerda());
preOrdem(raiz.getDireita());
}
}
public void emOrdem(Celula raiz)
{
if (raiz != null)
{
emOrdem(raiz.getEsquerda());
System.out.println(" Elemento: " + raiz.getElemento());
emOrdem(raiz.getDireita());
}
}
public void posOrdem(Celula raiz)
{
if (raiz != null)
{
posOrdem(raiz.getEsquerda());
posOrdem(raiz.getDireita());
System.out.println(" Elemento: " + raiz.getElemento());
}
}
public int tamanho(Celula raiz)
{
if (raiz == null)
{
return 0;
} else
{
this.qNos++;
if (raiz.getDireita() != null)
{
this.qNos = 1 + somaTamanhoNos(raiz.getDireita());
}
if (raiz.getEsquerda() != null)
{
this.qNos = 1 + somaTamanhoNos(raiz.getEsquerda());
}
}
return this.qNos;
}
private int somaTamanhoNos(Celula p)
{
if (p.getDireita() != null)
{
this.qNos = 1 + somaTamanhoNos(p.getDireita());
}
if (p.getEsquerda() != null)
{
this.qNos = 1 + somaTamanhoNos(p.getEsquerda());
}
return this.qNos;
}
public int altura(Celula raiz)
{
if (raiz == null)
{
return 0;
} else
{
Celula c = raiz;
if (c.getDireita() != null)
{
this.qNiveis++;
this.altura(c.getDireita());
} else if (c.getEsquerda() != null)
{
this.qNiveis++;
this.altura(c.getEsquerda());
}
}
return this.qNiveis;
}
public boolean cheia(Celula raiz)
{
boolean resultado = true;
return resultado;
}
public boolean cheio(Celula raiz)
{
boolean cheio = false;
if ((2 ^ this.altura(raiz)) == (this.tamanho(raiz) - 1))
{
cheio = true;
}
return cheio;
}[/code]
[code]public class Celula {
Celula esquerda;
Celula direita;
Celula pai;
char elemento;
public Celula(char value) {
this.elemento = value;
}
public Celula getDireita() {
return direita;
}
public void setDireita(Celula direita) {
this.direita = direita;
}
public char getElemento() {
return elemento;
}
public void setElemento(char elemento) {
this.elemento = elemento;
}
public Celula getEsquerda() {
return esquerda;
}
public void setEsquerda(Celula esquerda) {
this.esquerda = esquerda;
}
public Celula getPai()
{
return pai;
}
public void setPai(Celula pai)
{
this.pai = pai;
}[/code]