Vc deve ter alguma classe que controla a inclusão e remoção nessa árvore…
posta ai pra gente…
(só lembrando que, em Java não temos “ponteiro”, pra quem vem da linguagem C, como eu, pode encontrar dificuldades pra trabalhar com estrutura de dados… mas é só amadurecer o conceito de orientação a objetos e tudo se resolve…)
Fiz aqui agora, não ficou muito bonito não, isso pode ser melhorado muito…
public class No {
private int elemento;
private No dir, esq;
public No(int elemento){
this.elemento = elemento;
dir = null;
esq = null;
}
public int getElemento(){
return elemento;
}
public No getDir(){
return dir;
}
public void setDir(No dir){
this.dir = dir;
}
public No getEsq(){
return esq;
}
public void setEsq(No esq){
this.esq = esq;
}
}
public class Arvore {
No raiz;
No atual;
public Arvore() {
raiz = null;
}
public No getRaiz(){
return raiz;
}
public void insereNO(No no) {
if (raiz == null) {
raiz = no;
} else {
atual = raiz;
while (atual != null) {
if (no.getElemento() < atual.getElemento()) {
if (atual.getEsq() == null) {
atual.setEsq(no);
break;
}
else
atual = atual.getEsq();
} else if (no.getElemento() > atual.getElemento()) {
if (atual.getDir() == null) {
atual.setDir(no);
break;
}else
atual = atual.getDir();
}else{
System.out.println("Elemento já existe na árvore!!!");
return;
}
}
}
}
public void imprimeArvore(No no) {
if (no == null)
return;
System.out.println(no.getElemento() + " ");
imprimeArvore(no.getEsq());
imprimeArvore(no.getDir());
}
}
public class Main {
public static void main(String[] args) {
Arvore arvore;
No no;
arvore = new Arvore();
no = new No(10);
arvore.insereNO(no);
no = new No(5);
arvore.insereNO(no);
no = new No(15);
arvore.insereNO(no);
no = new No(12);
arvore.insereNO(no);
arvore.imprimeArvore(arvore.getRaiz());
}
}
nos testes que eu fiz funcionou…
agora fica o desafio pra vc… implementar a remoção…
lembre-se que a remoção do nó raiz terá um tratamento diferenciado…
cara… jeito eu encontrei… não é muito eficiente… mas… resolve…
O algoritmo é o seguinte:
Percorre a arvore inteira, a partir da raiz… e pega todos os elementos que são maior do que o elemento que vc deseja achar o sucessor…
Vc coloca esses caras numa lista ou num vetor… ai é só pegar o menor deles, que o mesmo é o sucessor!!!
public void sucessor(No autal, No elem){
if (atual == null)
return;
if(atual.getElemento() > elem.getElemento()){
//insere o elemento atual.getElemento numa lista, ou num vetor...
}
sucessor(atual.getEsq(), elem);
sucessor(atual.getDir(), elem);
}
[quote=ph_ms]cara… jeito eu encontrei… não é muito eficiente… mas… resolve…
O algoritmo é o seguinte:
Percorre a arvore inteira, a partir da raiz… e pega todos os elementos que são maior do que o elemento que vc deseja achar o sucessor…
Vc coloca esses caras numa lista ou num vetor… ai é só pegar o menor deles, que o mesmo é o sucessor!!!
public void sucessor(No autal, No elem){
if (atual == null)
return;
if(atual.getElemento() > elem.getElemento()){
//insere o elemento atual.getElemento numa lista, ou num vetor...
}
sucessor(atual.getEsq(), elem);
sucessor(atual.getDir(), elem);
}
espero ter ajudado…[/quote]
é por aí mesmo, mas pra economizar memória acho que jah pode fazer a comparação direto e nem precisa armazenar no vetor. A lógica é pegar o menor número maior que 18 por exemplo. Então pega o primeiro, 50 por exemplo, dai o próximo é 20, descarta o 50 e fica com o 20, dai o próximo é 30, nem pega ele, dai o próximo é 19…dai pega! e por aí vai!
