[color=violet]
Minha professora de Estrutura de Dados passou um trabalho para implementarmos um código de ABB com remoção de Nós e de folhas e eu não estou conseguindo fazer . 
Será que alguem pode me ajudar com o código de remoção em uma Árvore Binária de Busca? :?: :roll:
[/color]
Podemos sim, posta o código e a dúvida que a gente ajuda! 
[color=violet]
Esse é o código com os outros métodos.O único que consigo fazer é o de remoção… 
Quem souber,por favor me tá uma ajuda :idea:
Obrigado!!! :!:
[/color]
/////////////////////////////////////////////////////
// Operacoes com arvore binaria
//////////////////////////////////////////////////////
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(valor == r.getDado())
return r;
if(valor < r.getDado())
return(buscaABB(r.getEsq(),valor));
else
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
// Exerccio 2 : Retornar a referncia do n com o MAIOR valor
public No maiorDado(No r)
{
if(r == null)
return null;
if(r.getDir() == null)
return r;
return(maiorDado(r.getDir()));
}
// Exerccio 3: Retornar a referncia do n com o menor valor
public No menorDado(No r)
{
if(r == null)
return null;
if(r.getEsq() == null)
return r;
return(maiorDado(r.getEsq()));
}
// Exerccio 4: Imprimir na ordem inversa
public void ordemInversa(No r)
{
if (r != null)
{
ordemInversa(r.getDir());
System.out.print("" + r.getDado());
ordemInversa(r.getEsq());
}
}
// Exerccio 5 : Conta o no. de descendentes de um valor passado
public long contaDescendentes (No r, long valor)
{
No acha;
acha = buscaABB(r,valor);//busca diz o valor(procurado)na arvore
if(acha == null)//se não achou
return 0;
return(contaNos(acha));
}
// Percurso Em Ordem para AB ou ABB
public void emOrdem(No r)
{
if (r != null)
{
emOrdem(r.getEsq());
System.out.print(" " + r.getDado());
emOrdem(r.getDir());
}
}
// Percurso Pre 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 : Mtodo Ps-Ordem para AB ou ABB - Faa a chamada
/*
public void PosOrdem(No r)
{
if (r != null)
{
posOrdem(r.getEsq());
posOrdem(r.getDir());
System.out.print(" " + r.getDado());
}
}
*/
// Conta o numero de nos da arvore - AB ou ABB
public int contaNos(No r)
{
if (r == null)
return 0;
return (1 + contaNos(r.getEsq()) + contaNos(r.getDir()) );
}
// Conta o numero de nos folhas - AB ou ABB
public int contaFolhas(No r)
{
int folha = 0;
if (r == null)
return 0;
if (r.getEsq() == null && r.getDir() == null)
folha = 1;
return (folha + contaFolhas(r.getEsq()) + contaFolhas(r.getDir()) );
}
// Somar dados da arvore - AB ou ABB
public long somarDados(No r)
{
if (r == null)
return 0;
return (r.getDado() + somarDados(r.getEsq()) + somarDado (r.getDir()));
}
// Calcula altura da arvore - AB ou ABB
public int altura(No r)
{
int he = 0, hd = 0 ;
if (r == null)
return 0;
he = altura(r.getEsq());
hd = altura(r.getDir());
if (he > hd)
return (he + 1);
else
return (hd + 1);
}
//Contar quant de pais
public int contaPais(No r)
{
if(r == null)
return 0;
if(r.getEsq() != null || r.getDir() != null)
return(1 + contaPais(r.getEsq()) + contaPais(r.getDir()));
return 0;
}
} // fim da classeFaltou a classe No.
Outra coisa, quando estiver postando, verifique se a formatação BB está habilitada.
Existe um chebox embaixo da área de texto onde você edita o post com a opção de desabilitar, certifique-se de que esteja desmarcada.
Por isso suas tags code e color não estão funcionando corretamente. Se esse for o caso, no seu perfil de usuário essa opção pode estar configurada como default. Confira lá!
[color=violet]
Brigadinho pela dica!!
E a classe Nó está abaixo!! :!:
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
[/color]
Em primeiro lugar, parabéns. Sua classe está praticamente funcionando.
Seu único engano é o seguinte:
O usuário da árvore ABB não conhece nada sobre nós. Então, todos os seus métodos públicos devem receber um valor, não um nó como parâmetro.
Consertar sua classe é bem fácil:
-
Troque todos os métodos que recebem um nó para protected;
Ou seja, ao invés do método:
protected void preOrdem(No r);
O usuário terá o método:
public void preOrdem(); -
Crie métodos publicos que recebem ou não um valor (se não receberem, procure a partir da raiz). Esse método, deve localizar o nó inicial (use para isso o método buscaABB) e, só então, chamar os métodos protected a partir desse nó.
Exemplo:
public void preOrdem()
{
preOrdem(getRaiz());
}
No método somar dados, você poderia até fornecer duas assinaturas. A primeira sem um valor(), para somar todos os dados da árvore, e a segunda com um valor, para somar a partir do Nó que tem aquele valor. No anexo eu fiz isso.
- O método insereABB recebe a árvore toda como parâmetro. Não faça isso, lembre-se você está na classe árvore. Ao invés de passa-la como parâmetro, chame o método getRaiz() diretamente. Assim, o método insereABB inserirá na árvore em questão.
Como sua classe está muito bem estruturada e claramente você entendeu o conceito de árvore binária, coloquei a correção em anexo. Eu testei através do seguinte programa:
public class Teste {
public static void main(String[] args) {
ABB abb = new ABB(10);
abb.insereABB(5);
abb.insereABB(12);
abb.insereABB(20);
System.out.println(abb.somarDados());
System.out.println(abb.contaFolhas());
System.out.println("---");
abb.preOrdem();
System.out.println("---");
abb.ordemInversa();
System.out.println(abb.somarDados(12));
}
}Não foi necessário alterar a classe No.
[color=violet]
Muito obrigado pelas dicas.O meu programa está rodando certinho.
Só estou com um pequeno problema…não estou conseguindo de maneira alguma fazer o método de remoção.Minha professora deu exemplos teóricos(em forma de árvore)mais acho que a minha mente fechou. hahahha :lol:[/color]
[color=violet]Muito obrigado pelas dicas.O meu programa está rodando certinho.
Só estou com um pequeno problema…não estou conseguindo de maneira alguma fazer o método de remoção.Minha professora deu exemplos teóricos(em forma de árvore)mais acho que a minha mente fechou. hahahha :lol:[/color]
Faça o seguinte:
-
Crie uma versão protected do seu método insereABB para inserir um nó, ao invés de somente um valor. Depois, você altera o insere atual para usar esse método. Fica mais ou menos assim.
-
Use o método buscaPai para localizar o pai do nó a ser excluído.
-
Localize o nó do pai, e remova a referência do nó de lá. Guarde uma cópia do nó removido em alguma variável temporária;
-
Use o método insereABB para inserir os nós da esquerda e direita do nó removido.
Pronto!
A modificação de seu método de inserção fica assim:
private void insereABB(No novoNo) {
boolean achou;
No aux = this.getRaiz();
if (raiz == null) {
raiz = novoNo;
} else {
achou = false;
aux = raiz;
while (!achou) {
if (novoNo.getDado() < aux.getDado()) {
if (aux.getEsq() == null) {
aux.setEsq(novoNo);
achou = true;
} else aux = aux.getEsq();
}
else if (novoNo.getDado() > aux.getDado()) {
if (aux.getDir() == null) {
aux.setDir(novoNo);
achou = true;
} else aux = aux.getDir();
}
} // fim while
}// fim else
}
// Insere um valor em uma ABB sempre como folha
public void insereABB(long valor) {
insereABB(new No(valor));
}// fim métodoPS: A maneira descrita acima é o jeito “rápido e sujo” de resolver o problema. O ideal é fazer uma remoção que busque manter o balanceamento da árvore:
- Se o nó for uma folha, remova-o diretamente;
- Se o nó tiver apenas um filho, apenas desloque o filho para a posição do nó a ser removido, e remova o filho;
- Se o nó tiver dois filhos, desloque o próximo nó da árvore para o lugar do atual, e então, realize o processo de inserção desse nó a partir do nó recém deslocado;
É muito provável que o seu professor queira esse último algoritmo, ou algo similar a isso. Sugiro que você dê uma olhada num livro de estrutura de dados, que deve descrever como isso é feito.
Dá uma olhada no link abaixo para uma implementação completa:
http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html