1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Procura de elementos

Discussão em 'Programação' iniciada por lilcrazy, 20 de Março de 2007. (Respostas: 18; Visualizações: 1280)

  1. lilcrazy

    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[]
     
  2. MadOnion

    MadOnion Folding Member

    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:

    [​IMG]

    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.
     
  3. lilcrazy

    lilcrazy Power Member

    Bem ok, agora que já tenho umas luzes, mãos à obra!...

    Obrigado pela ajuda ;-)
     
  4. MadOnion

    MadOnion Folding Member

    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<Eleftright// No que aponta para a arvore esquerda, e direita

          //Constructor
          
    public Node<E> (E elementNode<ElNode<E) {

                   
    data element;
                   
    left;
                   
    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. :)
     
  5. lilcrazy

    lilcrazy Power Member

    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!");
    }
    }
    }
     
  6. MadOnion

    MadOnion Folding Member

    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(rootelemento);
    }
    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 raizActualint 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.leftelemento);
                return 
    raizActual;
            }
            
    // No caso de ser maior
            
    if (res 0) {
                            
    raizActual.right delete(raizActual.rightelemento);
                            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.
     
  7. lilcrazy

    lilcrazy Power Member

    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. ;-)
     
  8. lilcrazy

    lilcrazy Power Member

    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 dadosNoBinario 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(dadostemp.noEsquerdo); 
        return 
    temp
     }else if (
    dados>temp.dados){   //Se o elemento for maior que os dados da raiz actual
        
    temp.noDireito=delete(dadostemp.noDireito); 
        return 
    temp
       }
       return 
    temp
     }
     
  9. lilcrazy

    lilcrazy Power Member

    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...
     
  10. lilcrazy

    lilcrazy Power Member

    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 dadosNoBinario 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(dadostemp.noEsquerdo); 
      return 
    temp
     }else if (
    dados>temp.dados){ //Se o elemento for maior que os dados da raiz actual
      
    temp.noDireito=delete(dadostemp.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]
     
  11. lilcrazy

    lilcrazy Power Member

    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 ;-)
     
  12. MadOnion

    MadOnion Folding Member

    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á!
     
  13. lilcrazy

    lilcrazy Power Member

    Ok. Obrigado pela ajuda ;-)
     
  14. lilcrazy

    lilcrazy Power Member

    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
     
  15. HecKel

    HecKel The WORM

    Tens várias formas de percorrer árvores, queres percorrer a mesma obtendo os valores ordenadamente?

    abraços, HecKel
     
  16. lilcrazy

    lilcrazy Power Member

    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 :/
     
  17. HecKel

    HecKel The WORM

  18. Triston

    Triston Aku Soku Zan SM

  19. lilcrazy

    lilcrazy Power Member

    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 noint posint contador){
     
     if(
    no == null){
      
    contador++;
      return;
     }

     
    printInOrder(no.noEsquerdoposcontador++);
     
     if(
    contador==pos)
      
    System.out.println(no.dados);
     
     
    printInOrder(no.noDireitoposcontador++);

    }
     

Partilhar esta Página