ТАК,
Проблема
Предположим, что мы имеем плоский массив со следующей структурой:
$array = [ ['level'=>1, 'name' => 'Root #1'], ['level'=>1, 'name' => 'Root #2'], ['level'=>2, 'name' => 'subroot 2-1'], ['level'=>3, 'name' => '__subroot 2-1/1'], ['level'=>2, 'name' => 'subroot 2-2'], ['level'=>1, 'name' => 'Root #3'] ]; Проблема в том, что – преобразовать этот массив, чтобы он стал деревом. Подчинение определяется только с помощью порядка элементов и level . Давайте определяем children как имя измерения для хранения дочерних узлов. Для массива выше это будет:
массив (
массив (
'level' => 1,
'name' => 'Root # 1',
),
массив (
'level' => 1,
'name' => 'Root # 2',
'children' =>
массив (
массив (
'level' => 2,
'name' => 'subroot 2-1',
'children' =>
массив (
массив (
'level' => 3,
'name' => '__subroot 2-1 / 1',
),
),
),
массив (
'level' => 2,
'name' => 'subroot 2-2',
),
),
),
массив (
'level' => 1,
'name' => 'Root # 3',
),
)
Немного больше разъяснений, если не очевидно, кто является родителем для кого: следующий код может легко визуализировать идею:
function visualize($array) { foreach($array as $item) { echo(str_repeat('-', $item['level']).'['.$item['name'].']'.PHP_EOL); } } visualize($array);
– для массива выше:
- [Корень №1] - [Корень № 2] - [подпункт 2-1] --- [__ subroot 2-1 / 1] - [подстрока 2-2] - [Корень № 3]
конкретика
Существуют некоторые ограничения как для желаемого решения, так и для входного массива:
foreach (или другой цикл – это не имеет значения), только один раз, каждый элемент один за другим должен обрабатываться. Мой подход
В настоящее время у меня есть решение со стеклом. Я работаю со ссылками и поддерживаю текущий элемент стека, на который будет производиться запись на текущем этапе. То есть:
function getTree(&$array) { $level = 0; $tree = []; $stack = [&$tree]; foreach($array as $item) { if($item['level']>$level) //expand stack for new items { //if there are child elements, add last to stack: $top = key($stack); if(count($stack[$top])) { end($stack[$top]); $stack[] = &$stack[$top][key($stack[$top])]; } //add ['children'] dim to top stack element end($stack); $top = key($stack); $stack[$top]['children'] = []; $stack[] = &$stack[$top]['children']; } while($item['level']<$level--) //pop till certain level { //two times: one for last pointer, one for ['children'] dim array_pop($stack); array_pop($stack); } //add item to stack top: end($stack); $stack[key($stack)][] = $item; $level = $item['level']; } return $tree; }
– Так как это достаточно долго, я создал образец использования и вывода.
Вопрос
Как вы можете видеть, мое решение довольно длинное, и оно основано на ссылках и обработке внутренних указателей массива (таких как end() ), поэтому вопрос :
Могут ли быть другие – более короткие и четкие пути решения этой проблемы? Это похоже на стандартный вопрос, но я не нашел соответствующего решения (есть один подобный вопрос – но там OP имеет точный подчинение parent_id пока я его не знаю)
Хорошая вещь о вашей проблеме заключается в том, что ваш вход всегда отформатирован правильно, поэтому ваша фактическая проблема сужается до поиска детей для каждого узла, если они существуют, или для поиска родителя для каждого узла, если он есть. Последнее здесь более подходит, потому что мы знаем, что узел имеет родительский элемент, если его уровень больше одного, и это ближайший узел над ним в исходном плоском массиве с уровнем, равным уровню текущего узла минус один. В соответствии с этим мы можем просто следить за несколькими узлами, которые нас интересуют. Чтобы быть точнее, когда мы находим два узла с одинаковым уровнем, узел, который был найден ранее, не может иметь больше детей.
Реализация этого будет выглядеть так:
function buildTree(array &$nodes) { $activeNodes = []; foreach ($nodes as $index => &$node) { //remove if you don't want empty ['children'] dim for nodes without childs $node['children'] = []; $level = $node['level']; $activeNodes[$level] = &$node; if ($level > 1) { $activeNodes[$level - 1]['children'][] = &$node; unset($nodes[$index]); } } }неfunction buildTree(array &$nodes) { $activeNodes = []; foreach ($nodes as $index => &$node) { //remove if you don't want empty ['children'] dim for nodes without childs $node['children'] = []; $level = $node['level']; $activeNodes[$level] = &$node; if ($level > 1) { $activeNodes[$level - 1]['children'][] = &$node; unset($nodes[$index]); } } }
демонстрация
Реализация с использованием рекурсии:
function buildTreeHelper(&$array, $currentLevel = 1) { $result = array(); $lastIndex = 0; while($pair = each($array)) { list(, $row) = $pair; $level = $row['level']; if ($level > $currentLevel) { $result[$lastIndex]['children'] = buildTreeHelper($array, $level); } else if ($level == $currentLevel) { $result[++$lastIndex] = $row; } else { prev($array); // shift back break; } } return $result; } function buildTree($array) { reset($array); return buildTreeHelper($array); } $array = [ ['level'=>1, 'name' => 'Root #1'], ['level'=>1, 'name' => 'Root #2'], ['level'=>2, 'name' => 'subroot 2-1'], ['level'=>3, 'name' => '__subroot 2-1/1'], ['level'=>2, 'name' => 'subroot 2-2'], ['level'=>1, 'name' => 'Root #3'] ]; print_r(buildTree($array));