Gostaria de desenvolver um algoritmo que faz a busca por profundidade em uma árvore binária, mas não estou conseguindo.
Ao fazermos a árvore atribuímos a cada nó o custo (custo para transitar de um nó ao outro) e a heurística (valor heurístico 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 árvore é a seguinte:
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 árvore:
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 árvore por busca de profundidade, o método da busca por profundidade recebe como parâmetro a árvore e o nó final que desejamos encontrar na varredura da arvore, quando encontrarmos esse nó o método retorna um array com todos os nós que se passaram até chegar no nó esperado.
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
}
}
Estou varrendo a árvore pelo lado esquerdo, mas não estou conseguindo voltar na árvore.