У меня есть несколько пар «родитель-потомок», которые я хотел бы превратить в как можно более компактную структуру иерархических древовидных структур. Например, это могут быть такие пары:
Потомок : Родитель
H : G
F : G
G : D
E : D
A : E
B : C
C : E
D : NULL,
которые необходимо преобразовать в (иерархическое) дерево (деревья):
D
├── E
│ ├── A
│ │ └── B
│ └── C
└── G
├── F
└── H
В итоге я хочу получить вложенный набор элементов <ul>, в каждом из которых <li> содержит имя потомка. В парах нет несоответствий (дочерний элемент – это собственный родитель, родитель - это потомок дочернего и т.д.), поэтому, вероятно, можно провести ряд оптимизаций. Как в PHP перейти от массива, содержащего пары потомок => родитель, к набору вложенных <ul>?
Я думаю, что здесь можно использовать рекурсию, но я не вполне уверен в этом.
Ответ 1
Для этого требуется очень простая рекурсивная функция для разбора пар «потомок/родитель» в древовидную структуру и еще одна рекурсивная функция для ее распечатки. Достаточно одной функции, но для наглядности приведем две (комбинированную функцию можно найти в конце этого ответа).
Сначала инициализируйте массив пар «потомок/родитель»:
$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();
# Обход дерева и поиск прямых дочерних элементов корня
foreach($tree as $child => $parent) {
# A direct child is found
if($parent == $root) {
# Удалите элемент из дерева (нам не нужно обходить его снова)
unset($tree[$child]);
# Добавить дочерний элемент в массив result и разобрать его дочерние элементы
$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>';
}
}
Вы сэкономите только 8 итераций на таком маленьком наборе данных, но на больших наборах это может иметь большое значение.
Ответ 2
Еще одна функция для создания дерева (без рекурсии, вместо нее используются ссылки):
$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-списка с помощью рекурсивной функции.
Ответ 3
Другой – более упрощенный способ преобразования плоской структуры $tree в иерархию. Для его реализации требуется только один временный массив:
// добавление дочерних элементов к родительскому
$flat = array(); # временный массив
foreach ($tree as $name => $parent) {
$flat[$name]['name'] = $name; # self
if (NULL === $parent) {
# нет родителя, является корневым элементом, присваиваем его $tree
$tree = &$flat[$name];
} else {
# есть родитель, добавляем себя в качестве потомка
$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 для вывода массива. Дилемма заключается в том, что каждый элемент не знает, будут ли последующие элементы или нет, или сколько предыдущих элементов нужно закрыть.
Основная концепция, которую я придумал, заключается в следующем:
TreeNode - абстрагирует каждый элемент в простой тип TreeNode, который может предоставить значение (например, Name) и указать, есть ли у него дочерние элементы.
TreeNodesIterator - рекурсивный итератор, который может выполнять итерацию по набору (массиву) этих TreeNode. Это довольно просто, поскольку тип TreeNode уже знает, есть ли у него потомки и кто они.
RecursiveListIterator - RecursiveIteratorIterator, который имеет все события, необходимые при рекурсивном переборе любого типа RecursiveIterator:
beginIteration/endIteration – начало и конец основного списка;
beginElement/endElement – начало и конец каждого элемента;
beginChildren/endChildren – начало и конец каждого дочернего списка. Данный RecursiveListIterator предоставляет эти события только в виде вызовов функций. дочерние списки, как это типично для списков <ul><li>, открываются и закрываются внутри родительского элемента <li>. Поэтому событие endElement срабатывает после соответствующего события endChildren. Это можно изменить или сделать настраиваемым, чтобы расширить возможности использования данного класса. События распределяются как вызовы функций для объекта-декоратора, чтобы сохранить разделение.
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 является рекурсивным итератором, который позволяет выполнять рекурсивную итерацию над единственным корневым узлом $root. Он передается в виде массива, потому что этому классу нужно что-то для итерации, и позволяет повторно использовать набор дочерних элементов, который также является массивом элементов 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);
$flat = array();
foreach ($tree as $name => $parent) {
$flat[$name]['name'] = $name; # self
if (NULL === $parent) {
$tree = &$flat[$name];
} else {
$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) {
$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());
}
Вывод:
<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>
Возможным вариантом может быть итератор, который итерирует любой RecursiveIterator и обеспечивает итерацию всех событий, которые могут произойти. Тогда переключатель/case внутри цикла foreach мог бы работать с событиями.
Ответ 4
Сначала я бы превратил прямой массив пар ключ-значение в иерархический массив:
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;
}
Web
