Criar método "conteins" recursivo em arvores gerais

Boa noite,

Alguém poderia me auxiliar na criação do método private boolean conteins(elemento x) para árvores gerais e que seja recursivo, não tô conseguindo…

Árvores gerais? Isso quer dizer que cada nó da árvore pode ter um número arbritário de filhos?

Como está a sua classe Node? Em outras palavras, qual objeto você está usando como nó da árvore?

Certamente a implementação do método que você quer depende diretamente desta classe.

Até onde você já fez?

[quote=rod.attack]Árvores gerais? Isso quer dizer que cada nó da árvore pode ter um número arbritário de filhos?

Como está a sua classe Node? Em outras palavras, qual objeto você está usando como nó da árvore?

Certamente a implementação do método que você quer depende diretamente desta classe.

Até onde você já fez?[/quote]

Sim árvore genérica, geral… não é binária pois um pai pode ter mais de 2 filhos…
Na verdade não estamos utilizando Node… É exercício de aula, não sei bem se saberei explicar, por isso passo abaixo dois métodos da árvore, pode ser que ajude, um do percurso em profundidade (pré-ordem) e outro do percurso em largura.

Percurso em profundidade:

 public List<E> traversalPre() {
        List<E> res = new ArrayList<E>();
        traversalPreAux(this, res);
        return res;
    }

    private void traversalPreAux(Tree<E> tree, List<E> res) {
        res.add(tree.getItem());
        for (Tree<E> aux : tree.children) {
            traversalPreAux(aux, res);
        }
    }

Percurso em largura:

    public List<E> traversalBreadth() {
        Queue<Tree><E>> fila = new LinkedList<Tree><E>>();
        Tree<E> atual = null;
        List<E> res = new ArrayList<E>();
        fila.add(this);
        while (!fila.isEmpty()) {
            atual = fila.remove();
            res.add(atual.getItem());
            for(Tree<E> aux : atual.children)
                fila.add(aux);            
        }
        return res;
    }

Estamos utilizando pra tudo TAD, Tipo Abstrato de Dados, porisso o tipo <E>… Daí posso usar para qualquer coisa depois…

O que preciso é um método(conteins()) que me retorne True ou false caso a árvore ja possua um elemento qualquer que eu queira procurar em algum lugar… e tem que ser recursivo…

To meio pergido…

Voce pode usar um tipo mais acima da hierarquia como Collections. Assim seu método ia funcionar com todas classes que extendem Collections.

Um método contains (com A, e não E) em árvores geralmente é implementado assim:

[code]public bool contains(E objeto) {
if (this.getItem().equals(objeto))
return true;

for (Node n : getChildren()) {
if (children.contains(objeto))
return true;
}
}[/code]

[quote=ViniGodoy]Um método contains (com A, e não E) em árvores geralmente é implementado assim:

[code]public bool contains(E objeto) {
if (this.getItem().equals(objeto))
return true;

for (Node n : getChildren()) {
if (children.contains(objeto))
return true;
}
}[/code]

[/quote]

Valeu pela dica do contAins… hehehe

Mas eu não tenho uma classe Node, na maioria das pesquisas que fiz li algo sobre Node, mas acho que na minha aula estamos trabalhando diferente, acho que tratando cada “Node” como arvore talvez… Por exemplo, no package de arvore geral tenho, além da Main, mais 4 classes: EmptyTreeException, IteratorTreeType, Tree e TreeIterators.

*** Na verdade to meio na correria e não to conseguindo acompanhar a disciplina(e como estamos com pouco tempo em aula tb as árvores ta sendo visto bem rápido tb…) e no final do semestre agora tem projeto final pra fazer e tô apanhando, com bastante dificuldade… :frowning:

Grato pela dica,
Até+.

O negócio é assim.

Você precisa saber quem são os filhos daquela posição que você está, aí a lógica é simples:

  1. Teste se o objeto não está nesse nó. Se estiver, retorne true;
  2. Se não estiver, para cada nó filho, chame o contains. Se o nó contiver o valor, retorne true.

Como o método contains será chamado no filho, o filho também repetirá esse processo, chamado contains para os filhos dele. Não tem como fazer árvore sem uma estrutura de um nó definida. Se você não tem essa estrutura, talvez seja hora de rever seu código pois, no mínimo, uma das suas classes está com o nome errado.

[quote=ViniGodoy]O negócio é assim.

Você precisa saber quem são os filhos daquela posição que você está, aí a lógica é simples:

  1. Teste se o objeto não está nesse nó. Se estiver, retorne true;
  2. Se não estiver, para cada nó filho, chame o contains. Se o nó contiver o valor, retorne true.

Como o método contains será chamado no filho, o filho também repetirá esse processo, chamado contains para os filhos dele. Não tem como fazer árvore sem uma estrutura de um nó definida. Se você não tem essa estrutura, talvez seja hora de rever seu código pois, no mínimo, uma das suas classes está com o nome errado.[/quote]

Correto,

Entendi perfeitamente o conceito do contains… ele avalia e se não for o que procuro ele, recursivamente, vai avaliando os filhos e passando por todos os níveis até achar ou não…

Eu estou com mais dificuldade na verdade agora é pra usar a árvore no projeto final da disciplina, uma porque não aprendi muito bem a usá-las ainda e por que a cabeça não ajuda muito também(não sou mto bom em programar, mas to tentando melhorar… :slight_smile: ). O projeto é um joguinho(nem dá pra se chamar de jogo … hehehe) tenho que fazer uns robôs sairem de um labirinto qualquer criando um método para gerar os passos dos mesmos pelo labirinto até achar a saída… O prof. ja deu várias dicas, inclusive falou como devemos fazer, mas não to conseguindo implementar, na cabeça eu sei o que cada um dos 2 carinhas tem que fazer, mas o código não ta saindo… :frowning:

Um deles vai sair de uma posição qualquer do labirinto com a mão esquerda sempre encostando na parede da sua esqueda, esse sempre sai, mas pode caminhar pra caramba até sair… O amis esperto vai sair tb, e se fizer como ele deu a dica vai sair pela melhor alternativa, ou seja, menor caminho… Assim, vê a posição a sua direita, se não é parede ou se ainda não passei por ali coloca na árvore a posição(ponto x,y) e coloca aquela arvore na fila, senão tenta a esquerda, cima, baixo… Agora não lembro do final da lógica(sei que tem que percorrer em largura, em profundidade tb funciona mas não garante o melhor caminho…), mas ele explicou em aula e funciona mesmo, sei que qdo entra num beco sem saída vira “folha” e não continua mais alí… ao chegar na saída para e fim de papo… hehehe Com ele mostrando manualmente no quadro foi tão fácil de entender… Agora não sai nada… :[

Abraço,