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

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

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


mysql php closures tree
person Jonathan Dobbie    schedule 29.06.2009    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Первый ключ — отсортировать результаты 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)]
        );  
  }
person Jonathan Dobbie    schedule 30.06.2009
comment
Интересно! это имеет смысл, у родителей всегда будет меньше предков, чем у их детей. - person Jason S; 30.06.2009

arrow_upward
2
arrow_downward

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

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

изменить:

Если бы я выполнял запросы на PHP, я бы, вероятно, просто использовал SELECT для самой таблицы без использования GROUP_CONCAT - вы все равно будете обрабатывать вещи процедурно, так почему бы просто не получить соответствующее подмножество таблицы закрытия в самом необработанном виде. форма?

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

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

person Jason S    schedule 29.06.2009
comment
Вложенные наборы не имеют ссылочной целостности, и многие другие операции являются дорогостоящими/сложными. (т.е.: удаление) - person Jonathan Dobbie; 30.06.2009