Search for tree depth

Question

I’d like to develop an algorithm that searches for depth in a binary tree, but I’m not getting it.

When we make the tree we assign to each node the cost (cost to transition from one node to the other) and the heuristic (heuristic value of each node), to make the search for depth we do not take into account these two values.

The class that generates the tree nodes 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 we create each node and define your 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 should scan the tree by depth search, the method of depth search takes as parameter the tree and the final node 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 until you reach the expected knot.

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’m not getting back in the tree.

Answer 1

Actually, recursiveness is the most intuitive to do the in-depth search because it is easy to see that each subtree can be considered as a new tree (and treated in the same way). So, to learn, I suggest following the suggestion of reply from Mr @Yuricalistrato.

However, whereas you cite in your question attributes such as cost (cost of "navigating" from one node to another in the tree) and heuristics (estimate of how many nodes are missing until the final solution/node of interest), another interesting possibility is not to use recursiveness, replacing it with a queue of us to be processed.

The idea is simple:

1. When navigating to any node in the tree, you expand your child nodes (access them by some method) and add them at first of a row (can be a ArrayList, for example).

2. The next node to be navigated will be the first available in the queue. You check if it is the solution, and if it is not repeat the process from step 1.

This approach is interesting simply because it allows you to easily change your algorithm to implement other types of search, since is the insertion/removal order of nodes in the queue which indicates how processing occurs:

• If child nodes are inserted at the beginning of the queue, they will be immediately processed next. Therefore, the processing progressively sinks into the tree, ie, is implementing an in-depth search.

• If the child nodes are inserted at the end of the queue, they will be processed only after all those that are already there. So the processing first evaluates all the nodes on the same level, and then goes deeper into the tree. That is, is implementing a search in width.

• If the child nodes are entered in the queue prioritized (that is, the queue order is calculated according to some numerical metric created by you), the algorithm will process them in that order. Thus, you can build a priority queue using a cost, a heuristic or the sum of these values to build variations in the search such as Uniform Cost Search (only cost), Hill Climb Search (only heuristics) and Search A* (cost + heuristics).

The Java language has data structures that greatly facilitate the implementation of this type of queue, among them the classes Stack, Queue, HashMap and TreeSet, which can be very useful. The class TreeSet, for example, allows you to provide in your constructor an object "comparator", in order to allow you to build your own priority queue.

Note: in the literature, this priority queue is usually called the search "frontier" (because it stores the nodes that are the boundary boundary, which is continuously expanded as the search unfolds).

Answer 2

The navigation found on the Wikipedia uses recursiveness.

public void emOrdem(ArvoreNo no) {
  if(no != null) {
      emOrdem(no.getNoE());
      System.out.print(no.getInfo()+" ");
      emOrdem(no.getNoD());
  }
}

Example:

_{(source: Uol.com.br)}

In this case, they access the left side continuously until its limitation. Upon reaching the left side limit, it accesses the right of the node.

In the case of accesses:

A, B, D, H -> I -> E, J -> K...

H doesn’t have children. He makes the call "emOrdem(no.getNoE());", when calling and having no children, the method did not accomplish anything else, "if(no != null)", returning to the father and continuing the normal flow, passing through "System.out.print(no.getInfo()+" ");" and back to the right-hand access "emOrdem(no.getNoD());".

The secret is recursiveness. I hope you have clarified the operation! Good Luck!