1. java
  2. android
  3. c#
  4. .net
  5. javascript
  6. php
  7. jquery
  8. html
  9. sql

Busca por profundidade- Arvore

Gostaria de desenvolver um algoritmo que faz a busca por profundidade em uma àrvore binária, mas não estou conseguindo.

Ao fazermos a arvore atribuimoas a cada nó o custo (custo para transitar de um nó ao outro) e a heuristica( valor heuristico de cada nó), para fazermos a busca por profundidade não levamos em consideração esses dois valores.

A classe que gera os nós da Arvore é o seguinte:

package entity.tad.btree;

public class BTreeNode {

    private String nome; // identificação do nó de árvore
    private BTreeNode sucessor1 = null; // filho 1
    private BTreeNode sucessor2 = null; // filho 2
    private int custo1; // custo para 1
    private int custo2; // custo para 2
    private int hInfo; // informação heurística

    /**
     * Construtor para o BTreeNode
     * 
     * @param s
     *            indica o nome para o BTreeNode que está sendo criado
     */
    public BTreeNode(String s) {
        this.nome = s;
    }

    /**
     * Construtor para o BTreeNode
     * 
     * @param s indica o nome para o BTreeNode que está sendo criado
     * @param h indica o valor heuristico para o BTreeNode que está sendo criado
     *            
     */
    public BTreeNode(String s, int h) {
        this.nome = s;
        this.hInfo = h;
    }

    /**
     * Insere os sucessores de um BTreeNode. Tenta inserir no sucessor1. Caso
     * não esteja nulo, insere no sucessor2
     * 
     * @param node
     *            BTreeNode a ser inserido
     * @param custo
     *            Custo de transição de um nó de árvore até o sucessor sendo
     *            inserido
     */
    public void setSucessor(BTreeNode node, int custo) {

        if (this.sucessor1 == null) {
            this.sucessor1 = node;
            this.custo1 = custo;
        } else if (this.sucessor2 == null) {
            this.sucessor2 = node;
            this.custo2 = custo;
        }

    }


    public int gethInfo() {
        return hInfo;
    }

    public void sethInfo(int hInfo) {
        this.hInfo = hInfo;
    }

    public String getNome() {
        return nome;
    }

    public BTreeNode getSucessor1() {
        return sucessor1;
    }

    public BTreeNode getSucessor2() {
        return sucessor2;
    }

    public int getCusto1() {
        return custo1;
    }

    public int getCusto2() {
        return custo2;
    }

}

Após criarmos cada nó e definirmos seus filhos usamos essa classe para definir qual nó será a raiz da arvore.

package entity.tad.btree;

public class BTree {

    private BTreeNode raiz;

    /**
     * Construtor de uma árvore BTree
     * 
     * @param r
     *            BTreeNode passado como raiz da árvore
     */
    public BTree(BTreeNode r) {
        this.raiz = r;
    }

    public BTreeNode getRaiz() {
        return raiz;
    }

    public void setRaiz(BTreeNode raiz) {
        this.raiz = raiz;
    }



}

Criamos então outra classe que deveremos varrer a arvore por busca de profundidade, o metodo da busca por profundidade recebe como parametro a arvore e o nó final que desejamos encontrar na varredura da arvore, quando encontrarmos esse nó o metodo retorna um array com todos os nós que se passaram até chegar no nó esperado.

package control.rule.depth;

import java.util.ArrayList;

import control.rule.BTreeRule;
import entity.tad.btree.BTree;
import entity.tad.btree.BTreeNode;

public class DepthRule extends BTreeRule {

    @Override
    public ArrayList<BTreeNode> getPath(BTree tree, String goalName) {
        // Local que faz o código de busca profundidade
        return null; // o metodo de busca retorna um array com todos os elementos que o    //algoritmo passou na arvore


    }



}

Alguém poderia mne ajudar com esse trabalho, varro a arvore pelo lado esquerdo, mas não estou conseguindo voltar na arvore.

Obrigado

  1. Você vai ver essas setas em qualquer página de pergunta. Com elas, você pode dizer se uma pergunta ou uma resposta foram relevantes ou não.
  2. Edite sua pergunta ou resposta caso queira alterar ou adicionar detalhes.
  3. Caso haja alguma dúvida sobre a pergunta, adicione um comentário. O espaço de respostas deve ser utilizado apenas para responder a pergunta.
  4. Se o autor da pergunta marcar uma resposta como solucionada, esta marca aparecerá.
  5. Clique aqui para mais detalhes sobre o funcionamento do GUJ!

1 resposta

Não é a resposta que estava procurando? Procure outras perguntas com as tags busca algoritmos ou faça a sua própria pergunta.