Search by tree depth

5

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.

    
asked by anonymous 09.06.2015 / 19:28

2 answers

5

Actually, recursion is the most intuitive way of doing the search in depth because it is easy to see that each subtree can be considered as a new tree (and treated the same way). So to learn, I suggest following the suggestion of the colleague's answer @YuriCalistrato .

However, considering that you mention attributes such as cost (cost of "navigating" from one node to another in the tree) and heuristics (estimation of how many nodes are missing up to the solution / final node of interest), another interesting possibility is not to use recursion, replacing it with a queue of nodes to be processed.

The idea is simple:

When you browse to any node in the tree, you expand your child nodes (access them by some method) and add them to the beginning of a queue (it can be a ArrayList , for example).

  • The next node to be browsed will be the first available queue. You verify that it is the solution, and if not, it repeats the process from step 1.

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

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

    • If the child nodes are inserted at the end of the queue, they will be processed only after all those already there. Therefore, processing first evaluates all nodes on the same level, then delves into the tree. That is, a search in width is being implemented.

    • If child nodes are inserted into the queue as a priority (that is, the queue order is calculated according to some numeric metric you have created), the algorithm will process them in that order. So you can build a priority queue using a cost, a heuristic, or the sum of these values to construct variations on the search like Uniform Cost Search (cost only), Hill Rise Search (heuristic only), and Search A * ( cost + heuristics).

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

    Note: In the literature, this priority queue is often called the "frontier" search (because it stores the nodes that are the border boundary, which is continually expanded as the search unfolds).

        
    18.08.2015 / 17:41
    4

    The navigation found on the page Wikipedia uses recursion .

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

    Example:

    tree http://augustoborelli.xpg.uol.com.br/imagens/arvore_bin4.gif

    In this case, they access the left side continuously until their limitation. When it reaches the border on the left, it accesses the right node.

    In the case of accesses:

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

    H does not have children. When calling and having no children, the method did nothing else, " if (no! = Null) in ">, returning to the parent and continuing the normal flow, passing" System.out.print (no.getInfo () + ""); "and going back to the" in> Order (no.getNoD ()); ".

    The secret lies in recursion. I hope you have clarified the operation! Good Luck!

        
    09.06.2015 / 22:54