Binary tree level walking

Question

Binary tree level walking

Navigation

#1 by (3 votes)

2

Description of the problem I need to solve: "A path per level in a tree, first list the root, then all nodes that are at level 1 then all nodes of level 2, etc. Write a procedure to list the nodes of a binary tree by level."

As it is necessary to walk through a binary tree, I used recursion in the method writing, but I can not get the expected result. Here is the method I wrote:

public void imprimeNivel(No no) {
    if(no != null) {

        if(no == raiz) {
            System.out.println(raiz.getConteudo());
        } 
            if(no.getFilhoDireita() == null && no.getFilhoEsquerda() == null) {

            } else if(no.getFilhoDireita() == null) {
                System.out.printf("%d ", no.getFilhoEsquerda().getConteudo());
            } else if(no.getFilhoEsquerda() == null) {
                System.out.printf("%d ", no.getFilhoDireita().getConteudo());
            } else {
                System.out.printf("%d ", no.getFilhoEsquerda().getConteudo());
                System.out.printf("%d ", no.getFilhoDireita().getConteudo());
            }

            System.out.println();
            imprimeNivel(no.getFilhoEsquerda());
            imprimeNivel(no.getFilhoDireita());

    }
}

Could someone give me an idea how to solve this problem?

java algoritmo

asked by anonymous 04.05.2016 / 04:17

1 answer

Change Bootstrap navbar theme How to properly position a piece of View created in Java?

score 3 · Answer 1

Code

The most direct and simple algorithm code I know to cycle through the tree is using a queue:

public void walkLevels(No no) {
    if (no == null) throw new IllegalArgumentException("Tree node cannot be null!");
    Deque<No> fila = new ArrayDeque<>();
    fila.add(no);
    while (!fila.isEmpty()) {
        No atual = fila.removeFirst();
        System.out.printf("%s, ", atual.getConteudo());
        if (atual.getFilhoEsquerda() != null) fila.add(atual.getFilhoEsquerda());
        if (atual.getFilhoDireita() != null) fila.add(atual.getFilhoDireita());
    }
}

Algorithm

The basic idea of the algorithm is:

Start with the root

Consume the first node in the queue

Add his children, if any, to the end of the queue queue

Repeat steps 2 and 3 until you clear the queue

Because child nodes are always added to the end of the queue, this ensures that all previous level nodes will run before the next level.

Table test

Using the tree of Wikipedia :

Wecanmakearepresentationoftheexecutionlikethis:

FilaAção0-Início,colocaonóraiznafila18Consome8,adicionafilhos3e10aofinal2310Consome3,adicionafilhos1e6aofinal31016Consome10,adicionafilho14dadireitaaofinal41614Consome1,semfilhosentãonadaafazer5614Consome6,adicionafilhos4e7aofinal61447Consome14,adicionafilho13daesquerdaaofinal74713Consome4,semfilhosentãonadaafazer8713Consome7,semfilhosentãonadaafazer913Consome13,semfilhosentãonadaafazer10-Filavazia-->Terminou!

Binary tree level walking

1 answer

Code

Algorithm

Table test

Full code on my GitHub