Web

Как преобразовать серию «родитель-потомок» в иерархическое дерево

У меня есть несколько пар «родитель-потомок», которые я хотел бы превратить в как можно более компактную структуру иерархических древовидных структур. Например, это могут быть такие пары:

Потомок : Родитель

    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;

}

 

Схожие статьи

Лучший браузер для веб-разработчиков сайтов 2021
Web

Лучший браузер для веб-разработчиков сайтов 2021

Web

Транзакции в PHP + MySQL

Что такое веб-дизайнер. Описание профессии и ее подводные камни
Web

Что такое веб-дизайнер. Описание профессии и ее подводные камни

Web

Как настроить права доступа к файлам в Laravel?