I would like to develop an algorithm that does the depth search in a binary tree, but I am not getting it.
When we make the tree we assign to each node the cost (cost to move from one node to the other) and the heuristic (heuristic value of each node), to do the depth search we do not take these two values into account. p>
The class that generates the nodes of the tree is as follows:
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;
}
}
After creating each node and defining its children we use this class to define which node will be the root of the tree:
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;
}
}
We then create another class that we must scan the tree for depth search, the depth search method receives as parameter the tree and the final node that we want to find in the tree scan, when we find this node the method returns a array with all the nodes that have passed before reaching the expected node.
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
}
}
I'm sweeping the tree on the left side, but I can not get back into the tree.