La forma más fácil de construir un árbol a partir de una lista de Antepasados ​​

Question

En mi corazón, creo que debe haber una solución recursiva muy simple para esto, pero no puedo asimilarlo de inmediato.

Tengo un árbol almacenado en SQL como una tabla de cierre. El árbol se ve así: (1 (2 (3), 4)), y los lenguajes son SQL de MySQL y PHP 5.3.

La mesa de cierre es por lo tanto:

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

puedo consultar los antepasados ​​con bastante facilidad:

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  | 
+----+-----------+ 

¿Cómo puedo construir fácilmente un árbol en PHP con estos datos? ¿Puedo usar una consulta más inteligente para extraer más datos de MySQL?

Answer 1

La primera clave es ordenar los resultados de SQL por el número de antepasados. Hice esto en PHP porque evito las complejidades de los números de varios dígitos.

Esto proporciona una lista de nodos en un orden en el que se pueden insertar válidamente.

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 
     ) 

) 

En este momento, no me importan las claves, solo las listas de antepasados. El camino a través del árbol se puede encontrar entre la intersección de los nodos disponibles y los antepasados ​​restantes.

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

He usado una tabla de cierre (el término me suena extraño ... Olvidé qué/dónde lo oí llamar algo más) pero tenía una 3ra columna de "distancia" entre ancestro y descendiente, que permite usted distingue entre descendientes directos (niños) y descendientes indirectos (nietos, etc.).

Técnicamente, la tabla que ha enumerado puede registrar datos en un gráfico acíclico dirigido, por lo que puede que no sea posible construir un árbol jerárquico sin secciones duplicadas.

edición:

Si estuviera consultar en PHP, probablemente me acaba de seleccionar en la tabla misma w/o usando GROUP_CONCAT - vas a estar procesando cosas procesalmente todos modos, ¿por qué no acaba de obtener el subconjunto apropiado de la tabla de cierre en su forma más pura?

Tenga en cuenta también que una tabla de cierre no almacenará información de pedido (si eso es importante).

Si los aspectos del árbol de estos datos jerárquicos son muy importantes, y usted tiene la opción de cómo almacenar datos, considere el nested set model que puede mantener el orden y es mucho más fácil reconstruir un árbol.