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

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

У меня есть дерево, хранящееся в 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?

Ответы на вопрос(2)

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

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

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

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

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

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

 Jonathan Dobbie30 июн. 2009 г., 01:16
Вложенные множества не имеют ссылочной целостности, а многие другие операции являются дорогостоящими / сложными. (i.e.:deletion
Решение Вопроса

ал это на 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)]
        );  
  }
 Jason S30 июн. 2009 г., 15:35
Интересный! это имеет смысл, у родителей всегда будет меньше предков, чем у их детей.

Ваш ответ на вопрос