Преобразовать серию отношений родитель-ребенок в иерархическое дерево?

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

Сначала инициализируйте массив дочерних / родительских пар:

 $tree = array( 'H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null ); 

Затем функция, которая анализирует этот массив в иерархической древовидной структуре:

 function parseTree($tree, $root = null) { $return = array(); # Traverse the tree and search for direct children of the root foreach($tree as $child => $parent) { # A direct child is found if($parent == $root) { # Remove item from tree (we don't need to traverse this again) unset($tree[$child]); # Append the child into result array and parse its children $return[] = array( 'name' => $child, 'children' => parseTree($tree, $child) ); } } return empty($return) ? null : $return; } с function parseTree($tree, $root = null) { $return = array(); # Traverse the tree and search for direct children of the root foreach($tree as $child => $parent) { # A direct child is found if($parent == $root) { # Remove item from tree (we don't need to traverse this again) unset($tree[$child]); # Append the child into result array and parse its children $return[] = array( 'name' => $child, 'children' => parseTree($tree, $child) ); } } return empty($return) ? null : $return; } 

И функция, которая пересекает это дерево, чтобы распечатать неупорядоченный список:

 function printTree($tree) { if(!is_null($tree) && count($tree) > 0) { echo '<ul>'; foreach($tree as $node) { echo '<li>'.$node['name']; printTree($node['children']); echo '</li>'; } echo '</ul>'; } } 

И фактическое использование:

 $result = parseTree($tree); printTree($result); 

Вот содержимое $result :

 Array( [0] => Array( [name] => D [children] => Array( [0] => Array( [name] => G [children] => Array( [0] => Array( [name] => H [children] => NULL ) [1] => Array( [name] => F [children] => NULL ) ) ) [1] => Array( [name] => E [children] => Array( [0] => Array( [name] => A [children] => NULL ) [1] => Array( [name] => C [children] => Array( [0] => Array( [name] => B [children] => NULL ) ) ) ) ) ) ) ) 

Если вы хотите немного повысить эффективность, вы можете объединить эти функции в один и уменьшить количество итераций:

 function parseAndPrintTree($root, $tree) { $return = array(); if(!is_null($tree) && count($tree) > 0) { echo '<ul>'; foreach($tree as $child => $parent) { if($parent == $root) { unset($tree[$child]); echo '<li>'.$child; parseAndPrintTree($child, $tree); echo '</li>'; } } echo '</ul>'; } } с function parseAndPrintTree($root, $tree) { $return = array(); if(!is_null($tree) && count($tree) > 0) { echo '<ul>'; foreach($tree as $child => $parent) { if($parent == $root) { unset($tree[$child]); echo '<li>'.$child; parseAndPrintTree($child, $tree); echo '</li>'; } } echo '</ul>'; } } 

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

Еще одна функция для создания дерева (без рекурсии, вместо этого использует ссылки):

 $array = array('H' => 'G', 'F' => 'G', ..., 'D' => null); function to_tree($array) { $flat = array(); $tree = array(); foreach ($array as $child => $parent) { if (!isset($flat[$child])) { $flat[$child] = array(); } if (!empty($parent)) { $flat[$parent][$child] =& $flat[$child]; } else { $tree[$child] =& $flat[$child]; } } return $tree; } 

Возвращает иерархический массив, подобный этому:

 Array( [D] => Array( [G] => Array( [H] => Array() [F] => Array() ) ... ) ) 

Который можно легко напечатать как список HTML, используя рекурсивную функцию.

Другой, более упрощенный способ преобразования плоской структуры в $tree в иерархию. Для его отображения необходим только один временный массив:

 // add children to parents $flat = array(); # temporary array foreach ($tree as $name => $parent) { $flat[$name]['name'] = $name; # self if (NULL === $parent) { # no parent, is root element, assign it to $tree $tree = &$flat[$name]; } else { # has parent, add self as child $flat[$parent]['children'][] = &$flat[$name]; } } unset($flat); 

Это все, чтобы получить иерархию в многомерном массиве:

 Array ( [children] => Array ( [0] => Array ( [children] => Array ( [0] => Array ( [name] => H ) [1] => Array ( [name] => F ) ) [name] => G ) [1] => Array ( [name] => E [children] => Array ( [0] => Array ( [name] => A ) [1] => Array ( [children] => Array ( [0] => Array ( [name] => B ) ) [name] => C ) ) ) ) [name] => D ) 

Выход менее тривиален, если вы хотите избежать рекурсии (может быть, бремя с большими структурами).

Я всегда хотел решить UL / LI «дилемму» для вывода массива. Дилемма заключается в том, что каждый элемент не знает, будут ли дети следить или сколько предшествующих элементов необходимо закрыть. В другом ответе я уже решил, что с помощью RecursiveIteratorIterator и ищет getDepth() и другую метаинформацию, предоставленную моим собственным письменным Iterator : Приведение вложенной модели набора в <ul> но скрытие «закрытых» поддеревьев . Этот ответ также показывает, что с итераторами вы достаточно гибкие.

Однако это был предварительно отсортированный список, поэтому не подходит для вашего примера. Кроме того, я всегда хотел решить эту проблему в виде стандартной древовидной структуры и элементов HTML <ul> и <li> .

Основная идея, которую я придумал, заключается в следующем:

1. TreeNode Абстрагирует каждый элемент в простой тип TreeNode который может обеспечить его ценность (например, Name ) и имеет ли он детей.
2. TreeNodesIterator – RecursiveIterator TreeNodesIterator , способный выполнять итерацию по набору (массиву) этих TreeNodes . Это довольно просто, поскольку тип TreeNode уже знает, есть ли у него дети и какие.
3. RecursiveListIterator – RecursiveIteratorIterator который имеет все необходимые события, когда он рекурсивно перебирает любой тип RecursiveIterator :
   • beginIteration / endIteration – начало и конец основного списка.
   • beginElement / endElement – начало и конец каждого элемента.
   • beginChildren / endChildren – начало и конец каждого списка детей. Этот RecursiveListIterator предоставляет эти события только в виде вызовов функций. списки детей, так как это типично для списков <ul><li> , открываются и закрываются внутри его родительского элемента <li> . Поэтому событие endElement запускается после соответствующего события endChildren . Это можно было бы изменить или настроить для расширения использования этого класса. Затем события распределяются как вызовы функций объекту-декоратору, чтобы сохранить что-то в стороне.
4. ListDecorator – класс «декоратор», который является только приемником событий RecursiveListIterator .

Я начинаю с основной логики вывода. Взятый теперь иерархический массив $tree , окончательный код выглядит следующим образом:

 $root = new TreeNode($tree); $it = new TreeNodesIterator(array($root)); $rit = new RecursiveListIterator($it); $decor = new ListDecorator($rit); $rit->addDecorator($decor); foreach($rit as $item) { $inset = $decor->inset(1); printf("%s%s\n", $inset, $item->getName()); } 

Сначала рассмотрим ListDecorator который просто обертывает элементы <ul> и <li> и решает, как выводится структура списка:

 class ListDecorator { private $iterator; public function __construct(RecursiveListIterator $iterator) { $this->iterator = $iterator; } public function inset($add = 0) { return str_repeat(' ', $this->iterator->getDepth()*2+$add); } 

Конструктор принимает итератор списка, над которым он работает. inset – это просто вспомогательная функция для хорошего отступа вывода. Остальные – это только функции вывода для каждого события:

  public function beginElement() { printf("%s<li>\n", $this->inset()); } public function endElement() { printf("%s</li>\n", $this->inset()); } public function beginChildren() { printf("%s<ul>\n", $this->inset(-1)); } public function endChildren() { printf("%s</ul>\n", $this->inset(-1)); } public function beginIteration() { printf("%s<ul>\n", $this->inset()); } public function endIteration() { printf("%s</ul>\n", $this->inset()); } } 

Имея в виду эти выходные функции, это основной вывод / цикл вывода снова, я через него шаг за шагом:

 $root = new TreeNode($tree); 

Создайте корневой TreeNode который будет использоваться для запуска итерации:

 $it = new TreeNodesIterator(array($root)); 

Этот TreeNodesIterator является RecursiveIterator который позволяет рекурсивную итерацию по одному $root узлу. Он передается как массив, потому что этому классу нужно что-то перебирать и разрешать повторное использование с набором TreeNode элементов, который также является массивом элементов TreeNode .

 $rit = new RecursiveListIterator($it); 

Этот RecursiveListIterator является RecursiveIteratorIterator который предоставляет указанные события. Чтобы использовать его, необходимо предоставить только ListDecorator (класс выше) и назначить с помощью addDecorator :

 $decor = new ListDecorator($rit); $rit->addDecorator($decor); 

Затем все настроено так, чтобы просто foreach его и вывести каждый узел:

 foreach($rit as $item) { $inset = $decor->inset(1); printf("%s%s\n", $inset, $item->getName()); } 

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

Основанный на событии ListDecorator позволяет вам модифицировать вывод специально и предоставлять несколько типов списков для одной и той же структуры данных. Также возможно изменить ввод, поскольку данные массива были инкапсулированы в TreeNode .

Полный пример кода:

 <?php namespace My; $tree = array('H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null); // add children to parents $flat = array(); # temporary array foreach ($tree as $name => $parent) { $flat[$name]['name'] = $name; # self if (NULL === $parent) { # no parent, is root element, assign it to $tree $tree = &$flat[$name]; } else { # has parent, add self as child $flat[$parent]['children'][] = &$flat[$name]; } } unset($flat); class TreeNode { protected $data; public function __construct(array $element) { if (!isset($element['name'])) throw new InvalidArgumentException('Element has no name.'); if (isset($element['children']) && !is_array($element['children'])) throw new InvalidArgumentException('Element has invalid children.'); $this->data = $element; } public function getName() { return $this->data['name']; } public function hasChildren() { return isset($this->data['children']) && count($this->data['children']); } /** * @return array of child TreeNode elements */ public function getChildren() { $children = $this->hasChildren() ? $this->data['children'] : array(); $class = get_called_class(); foreach($children as &$element) { $element = new $class($element); } unset($element); return $children; } } class TreeNodesIterator implements \RecursiveIterator { private $nodes; public function __construct(array $nodes) { $this->nodes = new \ArrayIterator($nodes); } public function getInnerIterator() { return $this->nodes; } public function getChildren() { return new TreeNodesIterator($this->nodes->current()->getChildren()); } public function hasChildren() { return $this->nodes->current()->hasChildren(); } public function rewind() { $this->nodes->rewind(); } public function valid() { return $this->nodes->valid(); } public function current() { return $this->nodes->current(); } public function key() { return $this->nodes->key(); } public function next() { return $this->nodes->next(); } } class RecursiveListIterator extends \RecursiveIteratorIterator { private $elements; /** * @var ListDecorator */ private $decorator; public function addDecorator(ListDecorator $decorator) { $this->decorator = $decorator; } public function __construct($iterator, $mode = \RecursiveIteratorIterator::SELF_FIRST, $flags = 0) { parent::__construct($iterator, $mode, $flags); } private function event($name) { // event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)\n", $name, $this->getDepth(), @$this->elements[$this->getDepth()]); $callback = array($this->decorator, $name); is_callable($callback) && call_user_func($callback); } public function beginElement() { $this->event('beginElement'); } public function beginChildren() { $this->event('beginChildren'); } public function endChildren() { $this->testEndElement(); $this->event('endChildren'); } private function testEndElement($depthOffset = 0) { $depth = $this->getDepth() + $depthOffset; isset($this->elements[$depth]) || $this->elements[$depth] = 0; $this->elements[$depth] && $this->event('endElement'); } public function nextElement() { $this->testEndElement(); $this->event('{nextElement}'); $this->event('beginElement'); $this->elements[$this->getDepth()] = 1; } public function beginIteration() { $this->event('beginIteration'); } public function endIteration() { $this->testEndElement(); $this->event('endIteration'); } } class ListDecorator { private $iterator; public function __construct(RecursiveListIterator $iterator) { $this->iterator = $iterator; } public function inset($add = 0) { return str_repeat(' ', $this->iterator->getDepth()*2+$add); } public function beginElement() { printf("%s<li>\n", $this->inset(1)); } public function endElement() { printf("%s</li>\n", $this->inset(1)); } public function beginChildren() { printf("%s<ul>\n", $this->inset()); } public function endChildren() { printf("%s</ul>\n", $this->inset()); } public function beginIteration() { printf("%s<ul>\n", $this->inset()); } public function endIteration() { printf("%s</ul>\n", $this->inset()); } } $root = new TreeNode($tree); $it = new TreeNodesIterator(array($root)); $rit = new RecursiveListIterator($it); $decor = new ListDecorator($rit); $rit->addDecorator($decor); foreach($rit as $item) { $inset = $decor->inset(2); printf("%s%s\n", $inset, $item->getName()); } с <?php namespace My; $tree = array('H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null); // add children to parents $flat = array(); # temporary array foreach ($tree as $name => $parent) { $flat[$name]['name'] = $name; # self if (NULL === $parent) { # no parent, is root element, assign it to $tree $tree = &$flat[$name]; } else { # has parent, add self as child $flat[$parent]['children'][] = &$flat[$name]; } } unset($flat); class TreeNode { protected $data; public function __construct(array $element) { if (!isset($element['name'])) throw new InvalidArgumentException('Element has no name.'); if (isset($element['children']) && !is_array($element['children'])) throw new InvalidArgumentException('Element has invalid children.'); $this->data = $element; } public function getName() { return $this->data['name']; } public function hasChildren() { return isset($this->data['children']) && count($this->data['children']); } /** * @return array of child TreeNode elements */ public function getChildren() { $children = $this->hasChildren() ? $this->data['children'] : array(); $class = get_called_class(); foreach($children as &$element) { $element = new $class($element); } unset($element); return $children; } } class TreeNodesIterator implements \RecursiveIterator { private $nodes; public function __construct(array $nodes) { $this->nodes = new \ArrayIterator($nodes); } public function getInnerIterator() { return $this->nodes; } public function getChildren() { return new TreeNodesIterator($this->nodes->current()->getChildren()); } public function hasChildren() { return $this->nodes->current()->hasChildren(); } public function rewind() { $this->nodes->rewind(); } public function valid() { return $this->nodes->valid(); } public function current() { return $this->nodes->current(); } public function key() { return $this->nodes->key(); } public function next() { return $this->nodes->next(); } } class RecursiveListIterator extends \RecursiveIteratorIterator { private $elements; /** * @var ListDecorator */ private $decorator; public function addDecorator(ListDecorator $decorator) { $this->decorator = $decorator; } public function __construct($iterator, $mode = \RecursiveIteratorIterator::SELF_FIRST, $flags = 0) { parent::__construct($iterator, $mode, $flags); } private function event($name) { // event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)\n", $name, $this->getDepth(), @$this->elements[$this->getDepth()]); $callback = array($this->decorator, $name); is_callable($callback) && call_user_func($callback); } public function beginElement() { $this->event('beginElement'); } public function beginChildren() { $this->event('beginChildren'); } public function endChildren() { $this->testEndElement(); $this->event('endChildren'); } private function testEndElement($depthOffset = 0) { $depth = $this->getDepth() + $depthOffset; isset($this->elements[$depth]) || $this->elements[$depth] = 0; $this->elements[$depth] && $this->event('endElement'); } public function nextElement() { $this->testEndElement(); $this->event('{nextElement}'); $this->event('beginElement'); $this->elements[$this->getDepth()] = 1; } public function beginIteration() { $this->event('beginIteration'); } public function endIteration() { $this->testEndElement(); $this->event('endIteration'); } } class ListDecorator { private $iterator; public function __construct(RecursiveListIterator $iterator) { $this->iterator = $iterator; } public function inset($add = 0) { return str_repeat(' ', $this->iterator->getDepth()*2+$add); } public function beginElement() { printf("%s<li>\n", $this->inset(1)); } public function endElement() { printf("%s</li>\n", $this->inset(1)); } public function beginChildren() { printf("%s<ul>\n", $this->inset()); } public function endChildren() { printf("%s</ul>\n", $this->inset()); } public function beginIteration() { printf("%s<ul>\n", $this->inset()); } public function endIteration() { printf("%s</ul>\n", $this->inset()); } } $root = new TreeNode($tree); $it = new TreeNodesIterator(array($root)); $rit = new RecursiveListIterator($it); $decor = new ListDecorator($rit); $rit->addDecorator($decor); foreach($rit as $item) { $inset = $decor->inset(2); printf("%s%s\n", $inset, $item->getName()); } с <?php namespace My; $tree = array('H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null); // add children to parents $flat = array(); # temporary array foreach ($tree as $name => $parent) { $flat[$name]['name'] = $name; # self if (NULL === $parent) { # no parent, is root element, assign it to $tree $tree = &$flat[$name]; } else { # has parent, add self as child $flat[$parent]['children'][] = &$flat[$name]; } } unset($flat); class TreeNode { protected $data; public function __construct(array $element) { if (!isset($element['name'])) throw new InvalidArgumentException('Element has no name.'); if (isset($element['children']) && !is_array($element['children'])) throw new InvalidArgumentException('Element has invalid children.'); $this->data = $element; } public function getName() { return $this->data['name']; } public function hasChildren() { return isset($this->data['children']) && count($this->data['children']); } /** * @return array of child TreeNode elements */ public function getChildren() { $children = $this->hasChildren() ? $this->data['children'] : array(); $class = get_called_class(); foreach($children as &$element) { $element = new $class($element); } unset($element); return $children; } } class TreeNodesIterator implements \RecursiveIterator { private $nodes; public function __construct(array $nodes) { $this->nodes = new \ArrayIterator($nodes); } public function getInnerIterator() { return $this->nodes; } public function getChildren() { return new TreeNodesIterator($this->nodes->current()->getChildren()); } public function hasChildren() { return $this->nodes->current()->hasChildren(); } public function rewind() { $this->nodes->rewind(); } public function valid() { return $this->nodes->valid(); } public function current() { return $this->nodes->current(); } public function key() { return $this->nodes->key(); } public function next() { return $this->nodes->next(); } } class RecursiveListIterator extends \RecursiveIteratorIterator { private $elements; /** * @var ListDecorator */ private $decorator; public function addDecorator(ListDecorator $decorator) { $this->decorator = $decorator; } public function __construct($iterator, $mode = \RecursiveIteratorIterator::SELF_FIRST, $flags = 0) { parent::__construct($iterator, $mode, $flags); } private function event($name) { // event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)\n", $name, $this->getDepth(), @$this->elements[$this->getDepth()]); $callback = array($this->decorator, $name); is_callable($callback) && call_user_func($callback); } public function beginElement() { $this->event('beginElement'); } public function beginChildren() { $this->event('beginChildren'); } public function endChildren() { $this->testEndElement(); $this->event('endChildren'); } private function testEndElement($depthOffset = 0) { $depth = $this->getDepth() + $depthOffset; isset($this->elements[$depth]) || $this->elements[$depth] = 0; $this->elements[$depth] && $this->event('endElement'); } public function nextElement() { $this->testEndElement(); $this->event('{nextElement}'); $this->event('beginElement'); $this->elements[$this->getDepth()] = 1; } public function beginIteration() { $this->event('beginIteration'); } public function endIteration() { $this->testEndElement(); $this->event('endIteration'); } } class ListDecorator { private $iterator; public function __construct(RecursiveListIterator $iterator) { $this->iterator = $iterator; } public function inset($add = 0) { return str_repeat(' ', $this->iterator->getDepth()*2+$add); } public function beginElement() { printf("%s<li>\n", $this->inset(1)); } public function endElement() { printf("%s</li>\n", $this->inset(1)); } public function beginChildren() { printf("%s<ul>\n", $this->inset()); } public function endChildren() { printf("%s</ul>\n", $this->inset()); } public function beginIteration() { printf("%s<ul>\n", $this->inset()); } public function endIteration() { printf("%s</ul>\n", $this->inset()); } } $root = new TreeNode($tree); $it = new TreeNodesIterator(array($root)); $rit = new RecursiveListIterator($it); $decor = new ListDecorator($rit); $rit->addDecorator($decor); foreach($rit as $item) { $inset = $decor->inset(2); printf("%s%s\n", $inset, $item->getName()); } 

Outpupt:

 <ul> <li> D <ul> <li> G <ul> <li> H </li> <li> F </li> </ul> </li> <li> E <ul> </li> <li> A </li> <li> C <ul> <li> B </li> </ul> </li> </ul> </li> </ul> </li> </ul> 

Демо (вариант PHP 5.2)

Возможным вариантом будет итератор, который выполняет итерацию по любому RecursiveIterator Итератору и обеспечивает итерацию по всем событиям, которые могут произойти. Переключатель / корпус внутри цикла foreach может затем обрабатывать события.

Связанный:

• Вложенный список с рекурсивным атрибутом
• Класс RecursiveIteratorIterator

Ну, сначала я бы превратил прямой массив пар ключ-значение в иерархический массив

 function convertToHeiarchical(array $input) { $parents = array(); $root = array(); $children = array(); foreach ($input as $item) { $parents[$item['id']] = &$item; if ($item['parent_id']) { if (!isset($children[$item['parent_id']])) { $children[$item['parent_id']] = array(); } $children[$item['parent_id']][] = &$item; } else { $root = $item['id']; } } foreach ($parents as $id => &$item) { if (isset($children[$id])) { $item['children'] = $children[$id]; } else { $item['children'] = array(); } } return $parents[$root]; } 

Это может преобразовать плоский массив с parent_id и id в иерархический:

 $item = array( 'id' => 'A', 'blah' => 'blah', 'children' => array( array( 'id' => 'B', 'blah' => 'blah', 'children' => array( array( 'id' => 'C', 'blah' => 'blah', 'children' => array(), ), ), 'id' => 'D', 'blah' => 'blah', 'children' => array( array( 'id' => 'E', 'blah' => 'blah', 'children' => array(), ), ), ), ), ); 

Затем просто создайте функцию рендеринга:

 function renderItem($item) { $out = "Your OUtput For Each Item Here"; $out .= "<ul>"; foreach ($item['children'] as $child) { $out .= "<li>".renderItem($child)."</li>"; } $out .= "</ul>"; return $out; } 

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

Спасибо, я сделал для вас свой тест, чтобы сравнить два решения, представленные на этом посту.

У меня было плоское дерево @ 250k с 6 уровнями, которые мне пришлось преобразовать, и я искал лучший способ сделать это и избежать рекурсивных итераций.

Рекурсия vs Ссылка:

 // Generate a 6 level flat tree $root = null; $lvl1 = 13; $lvl2 = 11; $lvl3 = 7; $lvl4 = 5; $lvl5 = 3; $lvl6 = 1; $flatTree = []; for ($i = 1; $i <= 450000; $i++) { if ($i % 3 == 0) { $lvl5 = $i; $flatTree[$lvl6] = $lvl5; continue; } if ($i % 5 == 0) { $lvl4 = $i; $flatTree[$lvl5] = $lvl4; continue; } if ($i % 7 == 0) { $lvl3 = $i; $flatTree[$lvl3] = $lvl2; continue; } if ($i % 11 == 0) { $lvl2 = $i; $flatTree[$lvl2] = $lvl1; continue; } if ($i % 13 == 0) { $lvl1 = $i; $flatTree[$lvl1] = $root; continue; } $lvl6 = $i; } echo 'Array count: ', count($flatTree), PHP_EOL; // Reference function function treeByReference($flatTree) { $flat = []; $tree = []; foreach ($flatTree as $child => $parent) { if (!isset($flat[$child])) { $flat[$child] = []; } if (!empty($parent)) { $flat[$parent][$child] =& $flat[$child]; } else { $tree[$child] =& $flat[$child]; } } return $tree; } // Recursion function function treeByRecursion($flatTree, $root = null) { $return = []; foreach($flatTree as $child => $parent) { if ($parent == $root) { unset($flatTree[$child]); $return[$child] = treeByRecursion($flatTree, $child); } } return $return ?: []; } // Benchmark reference $t1 = microtime(true); $tree = treeByReference($flatTree); echo 'Reference: ', (microtime(true) - $t1), PHP_EOL; // Benchmark recursion $t2 = microtime(true); $tree = treeByRecursion($flatTree); echo 'Recursion: ', (microtime(true) - $t2), PHP_EOL; с // Generate a 6 level flat tree $root = null; $lvl1 = 13; $lvl2 = 11; $lvl3 = 7; $lvl4 = 5; $lvl5 = 3; $lvl6 = 1; $flatTree = []; for ($i = 1; $i <= 450000; $i++) { if ($i % 3 == 0) { $lvl5 = $i; $flatTree[$lvl6] = $lvl5; continue; } if ($i % 5 == 0) { $lvl4 = $i; $flatTree[$lvl5] = $lvl4; continue; } if ($i % 7 == 0) { $lvl3 = $i; $flatTree[$lvl3] = $lvl2; continue; } if ($i % 11 == 0) { $lvl2 = $i; $flatTree[$lvl2] = $lvl1; continue; } if ($i % 13 == 0) { $lvl1 = $i; $flatTree[$lvl1] = $root; continue; } $lvl6 = $i; } echo 'Array count: ', count($flatTree), PHP_EOL; // Reference function function treeByReference($flatTree) { $flat = []; $tree = []; foreach ($flatTree as $child => $parent) { if (!isset($flat[$child])) { $flat[$child] = []; } if (!empty($parent)) { $flat[$parent][$child] =& $flat[$child]; } else { $tree[$child] =& $flat[$child]; } } return $tree; } // Recursion function function treeByRecursion($flatTree, $root = null) { $return = []; foreach($flatTree as $child => $parent) { if ($parent == $root) { unset($flatTree[$child]); $return[$child] = treeByRecursion($flatTree, $child); } } return $return ?: []; } // Benchmark reference $t1 = microtime(true); $tree = treeByReference($flatTree); echo 'Reference: ', (microtime(true) - $t1), PHP_EOL; // Benchmark recursion $t2 = microtime(true); $tree = treeByRecursion($flatTree); echo 'Recursion: ', (microtime(true) - $t2), PHP_EOL; 

Вывод говорит сам за себя:

 Array count: 255493 Reference: 0.3259289264679 (less than 0.4s) Recursion: 6604.9865279198 (almost 2h) 

Вот что я придумал:

 $arr = array( 'H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null ); $nested = parentChild($arr); print_r($nested); function parentChild(&$arr, $parent = false) { if( !$parent) { //initial call $rootKey = array_search( null, $arr); return array($rootKey => parentChild($arr, $rootKey)); }else { // recursing through $keys = array_keys($arr, $parent); $piece = array(); if($keys) { // found children, so handle them if( !is_array($keys) ) { // only one child $piece = parentChild($arr, $keys); }else{ // multiple children foreach( $keys as $key ){ $piece[$key] = parentChild($arr, $key); } } }else { return $parent; //return the main tag (no kids) } return $piece; // return the array built via recursion } } 

выходы:

 Array ( [D] => Array ( [G] => Array ( [H] => H [F] => F ) [E] => Array ( [A] => A [C] => Array ( [B] => B ) ) ) ) 

Ну, чтобы разобрать в UL и LI, это будет что-то вроде:

 $array = array ( 'H' => 'G' 'F' => 'G' 'G' => 'D' 'E' => 'D' 'A' => 'E' 'B' => 'C' 'C' => 'E' 'D' => 'NULL' ); recurse_uls ($array, 'NULL'); function recurse_uls ($array, $parent) { echo '<ul>'; foreach ($array as $c => $p) { if ($p != $parent) continue; echo '<li>'.$c.'</li>'; recurse_uls ($array, $c); } echo '</ul>'; } 

Но мне бы хотелось увидеть решение, которое не требует, чтобы вы так часто проходили через массив …

Как создать динамический вид дерева и меню

Шаг 1. Сначала мы создадим таблицу treeview в базе данных mysql. эта таблица содержит четыре столбца. id – это идентификатор задачи, а имя – имя задачи.

 - -- Table structure for table `treeview_items` -- CREATE TABLE IF NOT EXISTS `treeview_items` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(200) NOT NULL, `title` varchar(200) NOT NULL, `parent_id` varchar(11) NOT NULL, PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=7 ; -- -- Dumping data for table `treeview_items` -- INSERT INTO `treeview_items` (`id`, `name`, `title`, `parent_id`) VALUES (1, 'task1', 'task1title', '2'), (2, 'task2', 'task2title', '0'), (3, 'task3', 'task1title3', '0'), (4, 'task4', 'task2title4', '3'), (5, 'task4', 'task1title4', '3'), (6, 'task5', 'task2title5', '5'); 

Шаг 2: Рекурсивный метод просмотра дерева, созданный ниже методом treeTreeView (), который вызывает рекурсию, если текущий идентификатор задачи больше, чем предыдущий идентификатор задачи.

 function createTreeView($array, $currentParent, $currLevel = 0, $prevLevel = -1) { foreach ($array as $categoryId => $category) { if ($currentParent == $category['parent_id']) { if ($currLevel > $prevLevel) echo " <ol class='tree'> "; if ($currLevel == $prevLevel) echo " </li> "; echo '<li> <label for="subfolder2">'.$category['name'].'</label> <input type="checkbox" name="subfolder2"/>'; if ($currLevel > $prevLevel) { $prevLevel = $currLevel; } $currLevel++; createTreeView ($array, $categoryId, $currLevel, $prevLevel); $currLevel--; } } if ($currLevel == $prevLevel) echo " </li> </ol> "; } 

Шаг 3. Создайте индексный файл, чтобы отобразить древовидную структуру. Это основной файл примера treeview, здесь мы будем называть метод createTreeView () с требуемыми параметрами.

  <body> <link rel="stylesheet" type="text/css" href="_styles.css" media="screen"> <?php mysql_connect('localhost', 'root'); mysql_select_db('test'); $qry="SELECT * FROM treeview_items"; $result=mysql_query($qry); $arrayCategories = array(); while($row = mysql_fetch_assoc($result)){ $arrayCategories[$row['id']] = array("parent_id" => $row['parent_id'], "name" => $row['name']); } ?> <div id="content" class="general-style1"> <?php if(mysql_num_rows($result)!=0) { ?> <?php createTreeView($arrayCategories, 0); ?> <?php } ?> </div> </body> 

Шаг 4. Создание CSS-файла style.css Здесь мы напишем весь класс, связанный с CSS, в настоящее время я использую список заказов для создания древовидного представления. вы также можете изменить путь изображения здесь.

 img { border: none; } input, select, textarea, th, td { font-size: 1em; } /* CSS Tree menu styles */ ol.tree { padding: 0 0 0 30px; width: 300px; } li { position: relative; margin-left: -15px; list-style: none; } li.file { margin-left: -1px !important; } li.file a { background: url(document.png) 0 0 no-repeat; color: #fff; padding-left: 21px; text-decoration: none; display: block; } li.file a[href *= '.pdf'] { background: url(document.png) 0 0 no-repeat; } li.file a[href *= '.html'] { background: url(document.png) 0 0 no-repeat; } li.file a[href $= '.css'] { background: url(document.png) 0 0 no-repeat; } li.file a[href $= '.js'] { background: url(document.png) 0 0 no-repeat; } li input { position: absolute; left: 0; margin-left: 0; opacity: 0; z-index: 2; cursor: pointer; height: 1em; width: 1em; top: 0; } li input + ol { background: url(toggle-small-expand.png) 40px 0 no-repeat; margin: -0.938em 0 0 -44px; /* 15px */ height: 1em; } li input + ol > li { display: none; margin-left: -14px !important; padding-left: 1px; } li label { background: url(folder-horizontal.png) 15px 1px no-repeat; cursor: pointer; display: block; padding-left: 37px; } li input:checked + ol { background: url(toggle-small.png) 40px 5px no-repeat; margin: -1.25em 0 0 -44px; /* 20px */ padding: 1.563em 0 0 80px; height: auto; } li input:checked + ol > li { display: block; margin: 0 0 0.125em; /* 2px */} li input:checked + ol > li:last-child { margin: 0 0 0.063em; /* 1px */ } 

Подробнее