Построение дерева без рекурсии в цикле

[alekciy]

Достаточно давно на глаза попадался пример кода в котором строилось дерево причем не через рекурсивные вызовы, а банальным циклом в один проход с использованием ссылок. Смутно припоминаю, хотя могу и ошибаться, что исходный массив был простой одномерный вида id => parent_id, а через цикл получали иерархию в виде многомерного массива. Сейчас ни где не могу найти подробности этого, поэтому буду благодарен, если кто кинет линк или код.

 

[dimitrius]

я нашел для себя решение здесь Графы. Поиск маршрутов

 

[weregod]

Сортировка по длине чего-нить, но корректно ли оно работало? Возможно, код предполагал какие-то особенности хранения данных, неприменимых к общему случаю.

 

[alekciy]

я нашел для себя решение здесь Графы. Поиск маршрутов

Нет, не то. Я хочу найти реализацию на PHP с циклом. Там достаточно короткий код был, но сейчас найти у себя я его ни где не могу.

 

[dimitrius]

Нет, не то. Я хочу найти реализацию на PHP с циклом. Там достаточно короткий код был, но сейчас найти у себя я его ни где не могу.

там все основные алгоритмы

 

[damner2]

alekciy наверна что-то типа того нада?

$items = array(
	1 => array(
		"parent_id" => null,
	),
	2 => array(
		"parent_id" => 1,
	),
	3 => array(
		"parent_id" => 1,
	),
	4 => array(
		"parent_id" => 3,
	),
);

foreach ($items as $id => &$item) {
	if (!$id) continue;
	$items[$item["parent_id"]]["children"][$id] = &$item;
}

var_dump($items[""]["children"]);

 

[alekciy]

Спасибо! Выглядит знакомо, кажется оно. Сейчас опробую. Пилить все равно придется, т.к. в данном примере Adjacency List, а у меня одномерный массив в виде Nested Set.

 

[AmdY]

alekciy
аааа.... в чём тогда проблема, NS уже плоский и отсортированный тащится из базы, нуно только отступы согласно level отбивать.

 

[alekciy]

alekciy
аааа.... в чём тогда проблема, NS уже плоский и отсортированный тащится из базы, нуно только отступы согласно level отбивать.

Знаю. Когда нужно просто отступы отбивать, то да, плоский список подходит. Но мне нужно не отступами отбивать, а выводить определенный html для потомков:

<div>
	<a>Родитель</a>
	<div>
		<div class="column">
			<a>Потомок 1</a>
			<a>Потомок 2</a>
			...
			<a>Потомок N</a>
		</div>
	</div>
</div>

Мне подумалось, что был бы двухмерный массив, то можно было использовать два цикла (внешний для отрисовки родительских категорий, внутренний для дочерних). Но вот сейчас с утра понял, что можно обойтись одним циклом и вложенными условиями по уровню. Смотреть будет так себе, зато по ходу желание получу.

В любом случае тема оказалась полезна. Благодаря damner2 удалось вспомнить однопроходную схему создания дерева.

 

[A1x]

alekciy не это случайно - http://phpclub.ru/detail/article/2002-06-03 ?

 

[alekciy]

alekciy не это случайно - http://phpclub.ru/detail/article/2002-06-03 ?

Направление тоже, но ситуация другая. Твой линк это все теже вариации NS на уровне SQL. С игнорированием отступов по level о которых говорил AmdY. Но у меня данные не уровня базы, а уровня PHP, они из базы получены и во входных данных к задаче есть линейный список в виде массива в котором зашита NS из базы (страшное слово, битрикс!). Логика же шаблона такова, что требует вложенных циклов, а не отступов.

 

[alekciy]

Но вот сейчас с утра понял, что можно обойтись одним циклом и вложенными условиями по уровню. Смотреть будет так себе, зато по ходу желание получу.

В итоге таки сделал конвертер из линейного списка в многомерный. Потому как выводить закрывающий div по if-у базируясь на значение level внутри foreach нельзя, т.к. это закрывает div на первой же итерации. И что бы решить, закрывать ли div нужно знать, а если вообще дочерние элементы. С чистым NS узнать этого нельзя.

 

[korpus]

массивы и ссылки на массивы это зло. И вот почему

 

[itprog]

korpus
собственно поведение логично, иначе бы не работало:

$a = array('qw', array('as', 'as')); 
$b = &$a[1]; 
unset($a[1][1]); 
var_dump($b);

 

[korpus]

itprog
В чём логичность?

 

[Alex Chuev]

Старая тема, но может быть кому понадобится... Написал такую функцию:

function array_tree($array, $id = 'id', $parent_id = 'parent_id', $children = 'children') {
    $tree = [[$children => []]];
    $references = [&$tree[0]];

    foreach($array as $item) {
        if(isset($references[$item[$id]])) {
            $item[$children] = $references[$item[$id]][$children];
        }

        $references[$item[$parent_id]][$children][] = $item;
        $references[$item[$id]] =& $references[$item[$parent_id]][$children][count($references[$item[$parent_id]][$children]) - 1];
    }

    return $tree[0][$children];
}

И не имеет значение, какие ключи у исходного массива.

 

[AmdY]

для NS всё проще, у тебя есть предыдущий levael и текущий. а начале цикла проверяешь есть ли разница и печаетшь $level - $prevLevel раз открывающийся тег, в конце цикла $prevLevel - $level закрывающийся.

 

[Alex Chuev]

для NS всё проще, у тебя есть предыдущий levael и текущий. а начале цикла проверяешь есть ли разница и печаетшь $level - $prevLevel раз открывающийся тег, в конце цикла $prevLevel - $level закрывающийся.

Функция не требует ни $level, ни $id записей в индексах массива. Получилась довольно универсально и без рекурсии.

Вот, оказывается, чем Слава в рабочее время занимается...))