como faço para empilhar uma arvore em uma pilha.
Tenho um projeto de arvore binária de busca na qual tenho que fazer um método que exiba o pré-ordem de forma iterativa. Para isso necessito empilhar a arvore na pilha e depois desempilhar a pilha em ordem inversa para gerar o pre-ordem iterativamente. Só que estou com dúvidas como faço isso.
Meu projeto tem as seguintes classes:
No
ArvoreBinariaBusca (possui a aplicação)
ABB (possui os métodos)
Pilha (classe na qual uso a pilha)
No.java
public class No
{
private long dado;
private No esq;
private No dir;
public No(long valor)
{
dado = valor;
esq = null;
dir = null;
}
public long getDado()
{
return dado;
}
public void setDado(long valor)
{
dado = valor;
}
public No getEsq()
{
return esq;
}
public No getDir()
{
return dir;
}
public void setDir(No p)
{
dir = p;
}
public void setEsq(No p)
{
esq = p;
}
} // fim classe No
ArvoreBinariaBusca.java
import javax.swing.*;
public class ArvoreBinariaBusca {
public static void main(String[] args) {
String sValor, sOpcao;
long valor;
int opcao;
No achou;
// Cria uma rvore vazia.
ABB arvore = new ABB();
String menu = "\n1 - Inserir valor na ABB " +
"\n2 - Pre-Ordem Iterativo " + // NOTE QUE VRIAS OPERAES NO IRO MUDAR !!!!
"\n3 - Calcular Nivel" +
"\n4 - Sair\n\nOpcao ";
try
{
while(true)
{
// apresenta menu e l a opo
sOpcao = JOptionPane.showInputDialog(menu);
opcao = Integer.parseInt(sOpcao);
switch(opcao)
{
case 1: // Insero - note : sempre ir inserir como folha
sValor = JOptionPane.showInputDialog("Valor para insero ? ");
valor = Long.parseLong(sValor);
achou = arvore.buscaABB(arvore.getRaiz(),valor);
if (achou == null) // testa se no achou - s ir inserir valor, caso ele no seja encontrado na rvore
{
arvore.insereABB(arvore,valor);
}
else
System.out.println("\n " + valor + " ja existe na rvore. Impossvel inserir !");
break;
case 2:
// Escrever os dados da lista pelo mtodo central ou em ordem
if (!arvore.estaVazia())
{
System.out.println("\n Arvore pelo In Order (Em Ordem) : ");
arvore.emOrdem(arvore.getRaiz());
}
else
{
JOptionPane.showMessageDialog(null,"arvore vazia",
"Erro na lista",JOptionPane.ERROR_MESSAGE);
}
break;
case 3 :
sValor = JOptionPane.showInputDialog("Valor ? ");
valor = Long.parseLong(sValor);
achou = arvore.buscaABB(arvore.getRaiz(),valor);
if (achou != null)
{
System.out.println("\nNo: "+valor+"\nNivel: "
+ arvore.calculaNivel(arvore.getRaiz(),valor));
}
else
System.out.println("\nNo "+valor+" nao encontrado!");
break;
case 4: System.exit(0); // Termina o programa
break;
default:
JOptionPane.showMessageDialog(null,"Opcao Invalida",
"Erro: opcao",JOptionPane.ERROR_MESSAGE);
}// fim switch
}// fim while
} // fim try
catch(NumberFormatException nfe)
{
System.exit(0); // Termina o programa
}
}// fim main
}// fim classe
ABB.java
/////////////////////////////////////////////////////
// Operaes com rvore binria
//////////////////////////////////////////////////////
public class ABB
{
private No raiz;
// Construtor - cria uma rvore vazia
public ABB()
{
raiz = null;
}
// Constutor - cria uma rvore com o n raiz e os links aterrados
public ABB(long valorRaiz)
{
raiz = new No(valorRaiz);
}
////////////////////////////////////////////////////////////////
// Mtodos
//////////////////////////////////////////////////////////////////
// Pega a referncia para a raiz da rvore
public No getRaiz()
{
return raiz;
}
// Verifica se a rvore est vazia
public boolean estaVazia()
{
return (raiz == null);
}
// Exerccio 1 : Fazer uma busca em uma ABB considerando um valor passado
// Note que esta busca mais eficiente do que a busca feita em uma AB,
// que at resolveria o que queremos.
public No buscaABB (No r, long valor) {
if (r == null)
return null;
if(r.getDado() == valor)
return r;
if(valor < r.getDado())
return (buscaABB(r.getEsq(),valor));
return (buscaABB(r.getDir(),valor));
}
// Insere um valor em uma ABB sempre como folha
public void insereABB(ABB arv, long valor)
{
No novoNo, aux;
boolean achou;
aux = arv.getRaiz();
novoNo = new No(valor);
if (raiz == null)
{
raiz = novoNo;
}
else
{
achou = false;
aux = raiz;
while (!achou)
{
if (valor < aux.getDado())
{
if (aux.getEsq() == null)
{
aux.setEsq(novoNo);
achou = true;
}
else
aux = aux.getEsq();
}
else
if(valor > aux.getDado())
{
if (aux.getDir() == null)
{
aux.setDir(novoNo);
achou = true;
}
else
aux = aux.getDir();
}
} // fim while
}// fim else
} // fim mtodo
public void emOrdem(No r)
{
if (r != null)
{
emOrdem(r.getEsq());
System.out.print(" " + r.getDado());
emOrdem(r.getDir());
}
}
// Percurso Pr-ordem para AB ou ABB
public void preOrdem(No r)
{
if (r != null)
{
System.out.print(" " + r.getDado());
preOrdem(r.getEsq());
preOrdem(r.getDir());
}
}
// Exerccio resolvido : Faa a chamada, se desejar.
public void posOrdem(No r)
{
if (r != null)
{
posOrdem(r.getEsq());
posOrdem(r.getDir());
System.out.print(" " + r.getDado());
}
}
// Conta o nmero de ns da rvore - AB ou ABB
public long alturaABB (No r)
{
int esq = 0;
int dir = 0;
if (r != null) {
if(r.getEsq() == null && r.getDir() == null)
esq = dir = 1;
if(r.getEsq() != null)
esq+= (1 + alturaABB(r.getEsq()));
if(r.getDir() != null)
dir+= (1 + alturaABB(r.getDir()));
}
if (esq >= dir)
return esq;
else
return dir;
}
public int calculaNivel (No r, long valor) {
if (r == null)
return -1;
if(r.getDado() == valor)
return 1;
if (valor < r.getDado())
return (1 + calculaNivel(r.getEsq(),valor));
else
return (1 + calculaNivel(r.getDir(),valor));
}
} // fim da classe
Pilha.java
public class Pilha
{
private int tam; // tamanho mximo da pilha
private long[] v; // vetor de dados
private int topo; // topo da pilha
// construtor
public Pilha(int tamanho)
{
tam = tamanho; // define o tamanho mximo
v = new long[tam]; // cria o vetor
topo = -1; // inicializa a pilha
}
// insere um elemento no topo da pilha - empilhamento
public void empilha(long valor)
{
v[++topo] = valor; // incrementa o topo e depois insere o elemento
}
// tira um elemento do topo da pilha. Nao trata pilha vazia aqui !
public long desempilha()
{
return v[topo--]; // pega primeiro o elemento e depois decrementa o topo
}
// mostra o elemento que est no topo da pilha
public long mostra()
{
return v[topo];
}
// retorna verdadeiro se pilha est vazia
public boolean estaVazia()
{
return (topo == -1);
}
// retorna verdadeiro se pilha est cheia
public boolean estaCheia()
{
return (topo == (tam - 1));
}
}
/* public class Pilha {
int raiz;
public Pilha(long valorRaiz) {
tam = valorRaiz; // define o tamanho mximo
v = new long[valorRaiz]; // cria o vetor
raiz = new Pilha(valorRaiz);
}
public void empilha() {
raiz.empilha();
}
public void desempilha() {
while(r != null){
desempilha.getDir();
desempilha.getEsq();
desempilha.getDado();
}
Eu acredito que o certo seria fazer o método na classe Pilha, mas como vou implementa-lá por exemplo na classe ArvoreBinariaBusca onde está o switch?
agradeço pela atenção,
Bruno