Árvore binária?

Programação Java
#1

Dae galera… eu estou com um problema que não tenho idéia de como começar…
É o seguinte… tenho duas tabelas no banco… Documento e GrupoDocumento… essa segunda tabela tem dois campos…
CodPai e CodFilho… ela serve para guardar a definição dos pais do documento e assim eu poderei percorrer por essa árvore…
Eu vou e cadastro um documento… posso dizer que ele é em resposta à outros dois documentos… sendo assim a relação aqui é de NxN, ou seja, um documento pode ter vários pais e um pai pode ter vários filhos…
Eu acho que essa estrutura é parecida com uma árvore genealogica… onde um sobrinho tem varios tios… etc…
O que eu quero com isso tudo… eu preciso ao clicar em um documento… mostrar toda a arvore dele… ou seja… preciso saber os pais dele, os pais do pai dele… e assim sucessivamente… … Eu não tenho idéia de como poderei jogar essa regra quando for fazer uma consulta no banco de dados…( Obs: MySQL 5.0 )… Terei que usar procedure?? Cursor do java?? Alguém tem alguma luz… apenas pra mim dar um início…
Vamos supor a seguinte situação::
Tenho o documento 1,2,3,4, 5
1 é pai do 2, o 2 é pai do 3 e do 4, e o 3 e o 4 são pais do 5

              1
              |
              2
              /\
             3 4
              \/
              5
             /\
            /\
....

Tendo essa estrutura… eu quero poder listar por exemplo toda a hierarqui do documento 5, sendo que ele tem dois pais que são o 3 e o 4…
O sistema é web…
Agradeço desde já a ajuda…
Abraço!!

#2

Cara, essa estrutura daí não é uma árvore, mas sim um grafo. Então procedimentos de caminhamento em árvores não vão funcionar para esta estrutura, tendo uma estrutura em memória você pode aplicar um caminhamento pré-ordem ou um caminhamento pós-ordem para fazer essa tarefa. Uma sugestão para a consulta seria você fazer algo do tipo:

SELECT * FROM NODO pai WHERE pai.codigo IN (SELECT codigo FROM NODO filho WHERE filho.codPai = pai.codigo)

#3

Cara… Com a tua resposta eu estou dando uma estudada em grafos pra ver… mas você poderia me dar um pouco mais de detalhes? Ou algo ou artigo sobre isso… exemplo…
Agradeço pela resposta…

#4

Seguinte,
Tinha esse site salvo aqui…explica sobre grafos…
Tem alguns algoritmos prontos só que em Linguagem C… mais pra entender o conceito vc pode usar como base…
http://www.ime.usp.br/~pf/algoritmos_em_grafos/
abraço

#5

Vou colocar aqui uma implementação simples de um grafo, existem outras várias implementações possíveis.

Implementação do nodo:

public class Nodo {
    private Object elemento;
    private Collection<Nodo> vizinhos;

    public Nodo(Object elemento) {
        this.elemento = elemento;
        vizinhos = new ArrayList<Nodo>();
    }

    public Object getElemento() {
        return elemento;
    }
 
    public void setElemento(Object elemento) {
        this.elemento = elemento;
    }

    public Collection<Nodo> getVizinhos() {
        return vizinhos;
    }

    public void addVizinho(Nodo nodo) {
        vizinhos.add(nodo);
    }
}

Implementação de um listener para o caminhamento (padrão Visitor):

public interface GrafoListener {
    public void processaNodo(Nodo nodo);
}

Implementação da classe GrafoUtils, responsável por fazer os caminhamentos:

public class GrafoUtils {
    public static void caminhamentoPreOrdem(Nodo raiz, GrafoListener listener) {
        caminhamentoPreOrdem(raiz, listener, new ArrayList<Nodo>());
    }

    private static void caminhamentoPreOrdem(Nodo raiz, GrafoListener listener, Collection<Nodo> visitados) {
        if (visitados.contains(raiz)) {
            return;
        }

        visitados.add(raiz);

        listener.processaNodo(raiz);

        for(Nodo vizinho : raiz.getVizinhos()) {
            caminhamentoPreOrdem(vizinho, listener, visitados);
        }
    }

    public static void caminhamentoPosOrdem(Nodo raiz, GrafoListener listener) {
        caminhamentoPosOrdem(raiz, listener, new ArrayList<Nodo>());
    }

    private static void caminhamentoPosOrdem(Nodo raiz, GrafoListener listener, Collection<Nodo> visitados) {
        if (visitados.contains(raiz)) {
            return;
        }

        visitados.add(raiz);

        for(Nodo vizinho : raiz.getVizinhos()) {
            caminhamentoPreOrdem(vizinho, listener, visitados);
        }

        listener.processaNodo(raiz);
    }
}

Classe de teste exemplificando os dois caminhamentos em um grafo igual ao descrito no problema:

public class Teste {
    public static void main(String[] args) {
        Nodo a = new Nodo("a");
        Nodo b = new Nodo("b");
        Nodo c = new Nodo("c");
        Nodo d = new Nodo("d");
        Nodo e = new Nodo("e");

        a.addVizinho(b);
        b.addVizinho(c);
        b.addVizinho(d);
        d.addVizinho(e);

        GrafoListener listener = new GrafoListener() {
            public void processaNodo(Nodo nodo) {
                System.out.print(nodo.getElemento());
            }
        };

        GrafoUtils.caminhamentoPreOrdem(a, listener);
        System.out.println();
        GrafoUtils.caminhamentoPosOrdem(a, listener);
    }
}

O resultado da execução deverá ser:
abcde
bcdea

#6

Cara… muito obrigado pela ajuda… valeu mesmo…
Abraço e fica com Deus!!

#7