Arvore dentro de uma pilha

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

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

///////////////////////////////////////////////////// 
// 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(); 

}