Procura de elementos

lilcrazy

Power Member
Arvores Binarias java

Boas pessoal!

Eu tenho de fazer uma aplicação em java usando árvores binárias. Do género: inserir um número, apagar esse número, verificar se existe esse número e imprimir no ecrã o número na posição x.
Nunca fiz nenhum exercício usando árvores binárias mas, de acordo com a minha pesquisa, penso que são os números pelo utilizador inseridos que irão pertencer à àrvore. Sendo assim, e tendo de estar por ordem númerica, penso que o melhor seria utilizar uma árvore binária degenerada. Estou certo?

Alguém me pode ilustrar com exemplos, ou dando um pequeno empurrão?

Obrigado[]
 
Tutorial bastante interessante-> Link

Sabes que uma arvore é composta por uma Raiz(root) que é o primeiro nó da arvore, que liga a uma folha.
Por sua vez essa folha, tem uma elemento e dois filhos, cada filho liga a uma folha. Um dos filhos(normalmente designado por folha esquerda) liga a uma nova folha, e o outro filho(folha direita), liga a uma nova folha, e assim sucessivamente, conforme indica o desenho:

binarytree.gif


Posso te dizer que primeiro deves fazer uma Interface BinTree<E> ou o nome que queiras dar à tua arvore. public interface BinTree<E> { }
E depois implementar essa interface numa classe que deves usar os metodos, por exemplo public classe LinkedBinTree<E> implements BinTree<E> { }


No wikipedia também encontras muita informação, sobre BinTree.

Qualquer dúvida, pergunta.
 
Já agora para dar mais umas luzes, para uma class LinkedBinTree<E> os possíveis atributos, apenas são a raiz, aka root. Root deve ser do tipo Node<E>:
private Node<E> root;

Para isso deves programar uma classe privada Node<E> que vai construir vários nós, recursivamente, por no entanto ajudar-te com a class privada:

PHP:
private static class Node<E>  {
      private E data; // Elemento
      private Node<E> left, right; // No que aponta para a arvore esquerda, e direita

      //Constructor
      public Node<E> (E element, Node<E> l, Node<E> r ) {

               data = element;
               l = left;
               r = right;
      }
}

O resto acho que agora é facil, é so saber quais os metodos que precisas, meter as assinaturas na interface, pre-condições, pos-condições. E depois implementar como já tinha dito no outro post. :)
 
Bem já estou +/- orientado. Já insiro elementos na árvore, vê se existe ou não. Na parte do remover é que está uma bocado complicado. Por exemplo numa árvore com 100 como raiz, 90 como braço esquerdo, e 10 como braço esquerdo de 90, quero remover 90 mas ele remove o 100. Alguém me pode dizer o que se passa (código ainda incompleto, se alguém ajudar agradeço ;-))

/**
Retira um nó da Árvore Binária
1. se o elemento for uma folha, remove-se simplesmente o elemento
2. se o elemento é um nó interno e tem apenas um filho, esse filho é colocado no lugar do elemento a remover (que é seu pai)
3. se o elemento é um nó interno e tem dois filhos, coloca-se na posição do elemento a remover o menor elemento da sub-árvore direita (uma transferência de posição)
*/
public void delete(int dados, NoBinario temp){
if (temp!=null){
if (dados<temp.dados){
//procura à esquerda
delete(dados, temp.noEsquerdo);
}else if(dados>temp.dados){
//procura à direita
delete(dados, temp.noDireito);
}else if(temp.noEsquerdo==null && temp.noDireito==null){
//nó sem descendentes
raiz=null;
System.out.println(dados+" DELETADO!");
}else if(temp.noEsquerdo==null){
//nó com um filho à direita
temp = raiz.noDireito;
System.out.println(dados+" DELETADO!");
}else if(temp.noDireito==null){
//nó com um filho à esquerda
temp = raiz.noEsquerdo;
System.out.println(dados+" DELETADO!");
}
}
}
 
lilcrazy, para a proxima usa as tags, fica dificil de perceber o código. E também comenta algumas partes, fica dificil de perceber para quem lê o código de fora.
Respondendo então à questão, a melhor maneira de resolver este exercício é recorrendo à recursividade, por exemplo:

PHP:
public void delete(int elemento) {
       root = delete(root, elemento);
}

Ou seja, começando na raíz, ele vai procurar nas subarvores esquerdas e direita, onde o elemento se encontra, depois precisas de escrever o metodo recursivo que vai devolver um tipo igual ao root:

PHP:
private NoBinario delete(NoBinario raizActual, int elemento) {
         if (raizActual == null) //Quer dizer que o elemento nao esta na arvore, é a ultima subarvore
                 return raizActual;
        
         //Senao
        int res = item.compareTo(localRoot.data); //tentar saber o sinal do numero

        // Se o elemento for menor que o raizActual.data(ou element ou whatever)
        if (res < 0) {
			raizActual.left = delete(raizActual.left, elemento);
			return raizActual;
        }
        // No caso de ser maior
        if (res > 0) {
                        raizActual.right = delete(raizActual.right, elemento);
                        return raizActual;
        }
       
        //falta ainda ver quando eles sao iguais, que vou deixar para fazeres :-D

Não fiz nada que não tenhas feito, apenas organizei para ficar mais bonito, o problema está quando eles são iguais.
Vais ver os se a arvore esquerda não tem filhos à direita, se não tiver a raizActual.data = raizActual.left.data; e agora a raizActual.left vai aponta para a raizActual.left.left
Já agora suponho que a tua arvore seja do tipo Prefixa, isto é, à medida que vais colocando os elementos, ele coloca os valores ordenados da esquerda para a direita.
Espero ter ajudado em alguma coisa.
 
Sorry, ao postar nem vi a confusão que ficou. Como estava com um bocado de pressa, falhou o copy paste. My bad!

A minha árvore insere o primeiro valor na raíz e o próximo elemento a inserir se for menor vai para a esquerda, se for maior vai para a direita.

Vou tentar então completar.

Obrigado pelas luzes. ;-)
 
Estou com um problema. Se, por exemplo, inserir um 100 (raiz) e depois inserir um 90 (esquerda) ou 120 (direita). Ao remover a raiz, o elemento 90 ou 120 são encontrados mas não é eliminado o 100 e colocados o 90 ou 120 na raíz. Alguma dica?

Ora aí está o que já consegui fazer...

/**
Retira um nó da Árvore Binária
1. se o elemento for uma folha, remove-se simplesmente o elemento
2. se o elemento é um nó interno e tem apenas um filho, esse filho é colocado no lugar do elemento a remover (que é seu pai)
3. se o elemento é um nó interno e tem dois filhos, coloca-se na posição do elemento a remover o menor elemento da sub-árvore direita (uma transferência de posição)
*/
PHP:
public NoBinario delete(int dados, NoBinario temp){ 
   if (dados==temp.dados){   //Se o nó foi encontrado...
    if((temp.noEsquerdo==null) && (temp.noDireito==null)){   //se o nó não tem filhos nem á esquerda, nem á direita (folha) então é eliminado simplesmente
    System.out.println(temp.dados+" DELETADO!");
    temp=null;   
   }else if((temp.noEsquerdo!=null) && (temp.noDireito!=null)){   //Se o nó tem filhos à esquerda e à direita...
    if((temp.noEsquerdo!=null) && (temp.noDireito==null)){   //Se o nó tem filhos apenas à esquerda, coloca o nó no lugar do elemento que é seu pai do lado esquerdo
     temp.dados=temp.noEsquerdo.dados;
     temp.noEsquerdo=temp.noEsquerdo.noEsquerdo;
     return temp;
   }else if((temp.noEsquerdo==null) && (temp.noDireito!=null)){  //Se o nó apenas tem filhos à direita, coloca o nó no lugar do elemento que é seu pai do lado direito 
    temp.dados=temp.noDireito.dados; 
    temp.noDireito=temp.noDireito.noDireito;
    return temp;
   }  
  }
 }else if (dados<temp.dados){   //Se o elemento for menor que os dados da raiz actual
    temp.noEsquerdo=delete(dados, temp.noEsquerdo); 
    return temp; 
 }else if (dados>temp.dados){   //Se o elemento for maior que os dados da raiz actual
    temp.noDireito=delete(dados, temp.noDireito); 
    return temp; 
   }
   return temp; 
 }
 
Problema resolvido! Era um problema de if´s e else´s...
Agora só falta ver quando um nó tem dois filhos (esquerdo e direito), e procurar o menor elemento da sub-árvore direita e substituí-lo pelo elemento a remover...
 
Ok, já consigo encontrar o menor elemento da sub-árvore direita. Consigo também substituir esse elemento e "puxar" a àrvore para cima, no entanto, dependendo de certos valores a àrvore fica mal substituída e alguns elementos pelo caminho são perdidos alterando a árvore...
Que está mal neste código?:

PHP:
/** 
Retira um nó da Árvore Binária
1. se o elemento for uma folha, remove-se simplesmente o elemento
2. se o elemento é um nó interno e tem apenas um filho, esse filho é colocado no lugar do elemento a remover (que é seu pai)
3. se o elemento é um nó interno e tem dois filhos, coloca-se na posição do elemento a remover o menor elemento da sub-árvore direita (uma transferência de posição)
*/ 
public NoBinario delete(int dados, NoBinario temp){ 
  if (dados==temp.dados){ //Se o nó foi encontrado...
   if((temp.noEsquerdo==null) && (temp.noDireito==null)){ 
   //1º caso: nó não tem filhos nem á esquerda, nem á direita
   System.out.println(temp.dados+" DELETADO!");
   //folha simplesmente eliminada
   temp=null; 
  }else if((temp.noEsquerdo!=null) && (temp.noDireito!=null)){
   //3º caso: nó tem dois filhos, à esquerda e à direita
   System.out.println("MINIMO: "+minimo(temp.noDireito));
   System.out.println("DADOS: "+temp.dados);
   temp.dados=minimo(temp.noDireito);
   temp.noDireito=temp.noDireito.noDireito;
  }else if((temp.noEsquerdo!=null) && (temp.noDireito==null)){ 
   //2º caso: nó tem filhos apenas à esquerda
   //coloca o nó no lugar do elemento que é seu pai do lado esquerdo
   temp.dados=temp.noEsquerdo.dados;
   temp.noEsquerdo=temp.noEsquerdo.noEsquerdo;
   return temp;
  }else if((temp.noEsquerdo==null) && (temp.noDireito!=null)){ 
   //2º caso: nó tem filhos apenas à direita
   //coloca o nó no lugar do elemento que é seu pai do lado direito 
   temp.dados=temp.noDireito.dados; 
   temp.noDireito=temp.noDireito.noDireito;
   return temp;
  } 
 }else if (dados<temp.dados){ //Se o elemento for menor que os dados da raiz actual
  temp.noEsquerdo=delete(dados, temp.noEsquerdo); 
  return temp; 
 }else if (dados>temp.dados){ //Se o elemento for maior que os dados da raiz actual
  temp.noDireito=delete(dados, temp.noDireito); 
  return temp; 
 }
 return temp; 
}
 
 

/** 
Encontra o valor mínimo de uma árvore binária não-vazia 
*/ 
private int minimo(NoBinario no){ 
 NoBinario corrente = no; 

 while (corrente.noEsquerdo != null){ 
  corrente = corrente.noEsquerdo; 
 } 
 return(corrente.dados); [/LEFT]
} 
[LEFT]
 
Código remodelado(penso que já está tudo! :))

PHP:
//3º caso apenas -> quando um nó tem um filho à esquerda e também à direita
 
else if((temp.noEsquerdo!=null) && (temp.noDireito!=null)){
  temp.dados=minimo(temp.noDireito);
  if((temp.noEsquerdo==null) && (temp.noDireito!=null)){
   temp.dados=temp.noDireito.dados;
   temp.noDireito=temp.noDireito.noDireito;
  }else if((temp.noEsquerdo!=null) && (temp.noDireito==null)){
   temp.dados=temp.noEsquerdo.dados;
   temp.noEsquerdo=temp.noEsquerdo.noEsquerdo; 
  }
 }

Agora o meu problema maior (depois desta série de problemas lol!) é criar um método print(int indice), por exemplo, que receba um valor inteiro que indique um indice. Este indice representa, por exemplo, imaginemos que colocamos varios elementos na árvore ordenados. O elemento de indice um é o menor, o último elemento é o maior. Se tivermos na árvore os elementos 100 (raiz), 90 (esquerda), 120 (direita), 121 (direita, direita), 1 (esquerda, esquerda). Do menor para o maior ficaria: 1, 90, 100, 120, 121. Respectivamente os indices seriam: 1,2,3,4,5. Qual a melhor pesquisa a utilizar? In-Order? ou Pre-Order?

Obrigado pelas dicas ;-)
 
Não consegui vir mais cedo para responder ou tentar responder às tuas questões.
Mas já vi que abriste outra thread, vou tentar ajudar-te lá!
 
Hey!

Alguém me consegue ajudar neste problema?

Preciso de percorrer todos os nós de uma árvore binária ordenada (depois de inseridos os elementos) e ir colocando esses elementos numa tabela.

Obrigado
 
Exacto. Percorrer ordenadamente e ir devolvendo o indice. Se for o menor elemento devolve o indice 1, o elemento maior devolve indice 2 e por ai em diante...

É mesmo urgente eu saber como se faz isso. Já corri tudo quando é sitio pa me poderem ajudar e...nada :/
 
Ok peço desculpa! Mas estou um bocado atarefado, perdi um fim de semana todo por causa disto e já descobri +/- como se faz. Tenho de entregar quarta e já consegui fazer isto:

PHP:
public void printInOrder(NoBinario no, int pos, int contador){
 
 if(no == null){
  contador++;
  return;
 }

 printInOrder(no.noEsquerdo, pos, contador++);
 
 if(contador==pos)
  System.out.println(no.dados);
 
 printInOrder(no.noDireito, pos, contador++);

}
 
Back
Topo