PHP Lang
  1. PHP Lang
  3. Самый простой способ построить дерево из списка предков
Intereting Posts
Передача NULL из PHP в MySQL для автоматического увеличения Как динамически создавать объекты в PHP? jquery, Ajax или PHP: запустить скрипт в определенное время или выполнить действие в фоновом режиме Как я могу остановить PHP sleep (), влияющий на весь мой PHP-код? Larvel 4.2 artisan CLI больше не работает после обновления композитора PHP Reflection: как узнать, наследуется ли ReflectionMethod? JQuery Ajax Voting Каков наилучший способ реализовать большой (1 ГБ или более) сайт для загрузки файлов на PHP или Java? cURL ничего не возвращает? Динамический ряд строк php while loop Могу ли я сделать это с помощью только SQL? Codeigniter – странный параметр 'favicon.ico' Лучшая практика для PHP / MySQL Назначение / Система бронирования вставить несколько строк через php-массив в mysql Behat 3 – как получить пользовательское расширение в контексте

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

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

У меня есть дерево, хранящееся в SQL в качестве таблицы закрытия. Дерево выглядит так: (1 (2 (3), 4)), а языки – это MySQL и 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?

Solutions Collecting From Web of "Самый простой способ построить дерево из списка предков"

Первый ключ – сортировать результаты 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)] ); }

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

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

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

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

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

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