Il modo più semplice per costruire un albero da un elenco di antenati

Question

Nel mio cuore, sento che ci deve essere una soluzione ricorsiva super semplice a questo, ma non posso immediatamente farlo.

Ho una struttura archiviata in SQL come tabella di chiusura. L'albero ha il seguente aspetto: (1 (2 (3), 4)) e le lingue sono MySQL di MySQL e PHP 5.3.

La tabella di chiusura è quindi:

+----------+------------+ 
| ancestor | descendant | 
+----------+------------+ 
|  1 |   1 | 
|  2 |   2 | 
|  3 |   3 | 
|  4 |   4 | 
|  1 |   2 | 
|  1 |   3 | 
|  1 |   4 | 
|  2 |   3 | 
+----------+------------+ 

posso interrogare gli antenati abbastanza facilmente con:

SELECT descendant AS id, GROUP_CONCAT(ancestor) as ancestors FROM 
closure GROUP BY (descendant); 

+----+-----------+ 
| id | ancestors | 
+----+-----------+ 
| 1 | 1   | 
| 2 | 2,1  | 
| 3 | 3,1,2  | 
| 4 | 4,1  | 
+----+-----------+ 

Come posso facilmente costruire un albero in PHP con questi dati? Posso usare una query più intelligente per estrarre più dati da MySQL?

Answer 1

La prima chiave consiste nell'ordinare i risultati SQL in base al numero di antenati. L'ho fatto in PHP poiché evito le complessità dei numeri a più cifre.

Fornisce un elenco di nodi in un ordine in cui possono essere inseriti correttamente.

Array 
(
    [1] => Array 
     (
      [0] => 1 
     ) 

    [4] => Array 
     (
      [0] => 4 
      [1] => 1 
     ) 

    [2] => Array 
     (
      [0] => 2 
      [1] => 1 
     ) 

    [3] => Array 
     (
      [0] => 3 
      [1] => 1 
      [2] => 2 
     ) 

) 

A questo punto, non mi interessano le chiavi, solo le liste degli antenati. Il percorso attraverso l'albero può essere trovato tra l'intersezione dei nodi disponibili e gli antenati rimanenti.

function add_node($ancestors, &$tree) { 
    if (count($ancestors) == 1) { 
     $tree[array_pop($ancestors)] = array(); 
     return; 
    } 
    $next_node = array_intersect($ancestors, array_keys($tree)); 
    $this->add_node(
     array_diff($ancestors, $next_node) , 
     $tree[array_pop($next_node)] 
     ); 
    } 

Answer 2

Ho usato un tavolo di chiusura (il termine mi sembra strano ... ho dimenticato cosa/dove l'ho sentito chiamare qualcos'altro) ma avevo una terza colonna di "distanza" tra antenato e discendente, che consente si distingue tra discendenti diretti (figli) e discendenti indiretti (nipoti, ecc.).

Tecnicamente la tabella elencata può registrare i dati in un grafico aciclico diretto, quindi potrebbe non essere possibile costruire un albero gerarchico senza sezioni duplicate.

edit:

Se fossi l'interrogazione in PHP, probabilmente sarei basta selezionare sul tavolo stesso w/o utilizzando group_concat - si sta andando ad essere l'elaborazione di cose procedurale comunque, quindi perché no basta ottenere il sottoinsieme appropriato della tabella di chiusura nella sua forma più grezza?

Si noti inoltre che una tabella di chiusura non memorizzerà le informazioni di ordinazione (se ciò è importante).

Se gli aspetti dell'albero di questi dati gerarchici sono molto importanti e si ha una scelta su come memorizzare i dati, si consideri lo nested set model che può mantenere l'ordine ed è molto più facile ricostruire un albero.