Algorítmo de Árvore Binária

  1. Codifique uma função para imprimir uma árvore binária, nível por nível, começando pelo topo da árvore.

Para o exemplo abaixo teria de imprimir: 0 - 0L - 0R - 0LL - 0LR - 0RL - 0RR

Não encontrei um algoritmo para o problema descrito. Alguém conhece a solução???

Só para completar o exercício que o Daniel está propondo, se alguém quiser procurar no Google, procure por “breadth-first traversal”.

[code]
public class No {
private No esq;
private No dir;
private String nome;

private boolean mostraNivel(int nivel) {
    if (nivel == 0) {
        System.out.println(nome);
        return true;
    }
    return (esq != null ? esq.mostraNo(nivel - 1) : false)
        || (dir != null ? dir.mostraNo(nivel - 1) : false);
}

public void mostraArvore() {
    for (int i = 0; mostraNivel(i); i++) {}
}

}[/code]
Vê se esse código resolve. Crie os nós e popule os campos e então é só chamar o mostraArvore() da raiz.
Não testei, mas deve ser algo parecido com isso.

victorwss, o seu mostra apenas: 0 - 0L - 0LL

thingol, vendo esta URL: http://www.cs.bu.edu/teaching/c/tree/breadth-first/

Eu justamente havia pensando em usar uma estrutura extra (lista ou fila) para implementar, que é o que o link sugere.

Solução: http://www.sourcecodesworld.com/articles/java/java-data-structures/Tree_Traversals.asp

Código testado:

[code]public class No {
public No esq;
public No dir;
public String nome;

public void breadth_first(){
    Queue<No> q = new LinkedList<No>();
    No tmp;
    q.add(this);
    while(!q.isEmpty()){
        tmp = q.remove();
        if(tmp.esq != null)
            q.add(tmp.esq);
        if(tmp.dir != null)
            q.add(tmp.dir);
        System.out.print(tmp.nome+" ");
    }
}

}[/code]

[code]public class Teste {
public static void main(String[] agrs) {
No n = new No();
n.nome=“0”;

    n.esq = new No();
    n.esq.nome = "0L";
    n.dir = new No();
    n.dir.nome = "0R";
    
    n.esq.esq = new No();
    n.esq.esq.nome = "0LL";
    n.esq.dir = new No();
    n.esq.dir.nome = "0LR";
    
    n.dir.esq = new No();
    n.dir.esq.nome = "0RL";
    n.dir.dir = new No();
    n.dir.dir.nome = "0RR";
    
    n.dir.esq.esq = new No();
    n.dir.esq.esq.nome = "0RLL";
    
    n.breadth_first();
}

}[/code]

É isso aí.

O segredo de procurar no Google é lembrar-se do que já achou no Google :stuck_out_tongue:

Ops, troca o || por |.

[quote=thingol]É isso aí.
O segredo de procurar no Google é lembrar-se do que já achou no Google :P[/quote]

Pois é, eu não estava sabendo como procurar. Em português eu não achei nada com o que pesquisei. Em inglês eu não ia saber nunca. Mesmo assim eu não tinha achado nada.

Conheço essa imagem.

hehehehe… fala baixooooo

http://www.guj.com.br/posts/preList/103489/567224.java#567224

Em português o nome é busca em largura…

Legal, funcionou aqui.
Agora vou tentar ir mais além: na entrada do pgm, informar a qtde de nós e o pgm montar a árvore e fazer a varredura. :twisted:

busca em APMPLITUDE - fila
busca em PROFUNDIDADE - pilha

[quote=RodyBr]Legal, funcionou aqui.
Agora vou tentar ir mais além: na entrada do pgm, informar a qtde de nós e o pgm montar a árvore e fazer a varredura. :twisted: [/quote]

[code]public class Teste {
public static void main(String[] args) {

int num = Integer.parseInt(args[0]);

ArvoreBinaria bin = ArvoreBinaria();
for(int i=0; i<num; i++) {
   bin.add(num);
}

}
}[/code]