Самый простой способ построить дерево из списка предков

Question

В моем сердце я чувствую, что должно быть очень простое рекурсивное решение этого вопроса, но я не могу сразу его ухватить.

У меня есть дерево, хранящееся в SQL как таблица замыканий. Дерево выглядит так: (1 (2 (3), 4)), а языками являются MySQL SQL и PHP 5.3.

Таблица закрытия, таким образом:

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

Я могу довольно легко запросить предков с помощью:

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

Как я могу легко построить дерево в PHP с этими данными? Могу ли я использовать более умный запрос, чтобы получить больше данных из MySQL?

Answer 1

Первый ключ - сортировка результатов SQL по количеству предков. Я сделал это на PHP, так как избегаю сложностей многозначных чисел.

Предоставляет список узлов в том порядке, в котором они могут быть корректно вставлены.

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
        )

)

На данный момент меня не волнуют ключи, только списки предков. Путь через дерево можно найти между пересечением доступных узлов и оставшихся предков.

  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

Я использовал закрывающую таблицу (этот термин звучит для меня странно ... Я забыл, что / где я слышал, что это называется чем-то еще), но у меня был 3-й столбец "расстояния" между предком и потомком, который позволяет вам различают прямых потомков (детей) и косвенных потомков (внуков и т. д.).

Технически таблица, которую вы перечислили, может записывать данные в ориентированном ациклическом графе, поэтому построение иерархического дерева без дубликатов может быть невозможным.

редактировать:

Если бы я делал запросы в PHP, я бы, вероятно, просто ВЫБЕРИЛ на самой таблице без использования GROUP_CONCAT - вы все равно будете обрабатывать вещи процедурно, так почему бы просто не получить соответствующее подмножество таблицы закрытия в чистом виде?

Обратите внимание, что в таблице закрытия не будет храниться информация о заказе (если это важно).

Если древовидные аспекты этих иерархических данных очень важны, и у вас есть выбор, как хранить данные, рассмотрите модель вложенного множества , которая может поддерживать порядок и намного проще реконструировать дерево.