Конвертирование массива с деревом

У вас в массиве у элемента нет идентификатора родительского элемента. Всегда дочерние элементы следуют строго за родительским, причём в порядке возрастания вложенности? Если да, алогоритм напишу, если нет - алгоритм невозможен в принципе.

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

name, parent_id:

Array (

    [0] => Array (

            [name] => Д'Артаньян

            [parent_id] => -1

        )

    [1] => Array (

            [name] => Сын Д'Артаньяна

            [parent_id] => 0

        )

    [2] => Array (

            [name] => Атос

            [parent_id] => -1

        )

....

если parent_id == -1 то это корень, другое значение ссылается на родителя.

Вряд ли это кстати. Топикстартер говорит о дереве NestedSets.

Николай В., левого ключа и уровня для такой сортировки недостаточно. Правый ключ также нужен.

А, соббсно, в чем проблема? Или я не могу понять непостижимой глубины поставленной задачи? 😮

Имхо, это классическая задача на перевод бинарного дерева в обычное (обратите внимание на то, как перечислены субъекты в списке)

Подробнее:

выглядит примерно вот так:

Заводим элемент с нулевым левелом

Проходим по исходному списку.

Если левел следующего элемента списка выше текущего на единицу, добавляем его в качестве сына.

Если левел следующего элемента списка выше текущего на два, вызываем себя рекурсивно, задавая в качестве параметров последнего добавленного сына и продолжение списка.

Если левел следующего элемента списка равен обрабатываемому "мушкетеру" - выходим.

Если список кончился - работа выполнена.

Да, задача не тривиальная :) Тоже пришлось побиться минут 15.

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

Но есть более быстродействиенный метод:

$array = array ();
$way = array();
$lastlevel = 1;
$cnt = 0;
foreach ($list as $id=>$item) {
	if ($item['level'] > $lastlevel) {
		$way[] = $id;
	} else if ($item['level'] == $lastlevel) {
		if ($cnt > 0) {
			array_pop($way);
		}
		$way[] = $id;
	} else {
		array_pop($way);
		array_pop($way);
		$way[] = $id;
	}
	$lastlevel = $item['level'];
	$str = '$array';
	$wcnt = 0;
	foreach ($way as $id) {
		$str .= (($wcnt > 0)?'[\'tree\']':'') . "[{$id}]";
		$wcnt ++;
	}
	$str .= ' = $item;';
	eval($str);
	$cnt ++;
}

Тут приходится прибегать к функции eval() - это сильно усложняет чтение кода и портит его логику. Программисты не любят эту функцию. Но использовать здесь рекурсию, имхо, еще хуже :)

В общем, идея такая: мы пробегаемся по списку и для каждого элемента генерим строку вроде

$array[3]['tree'][4]['tree'][5] = $item;

а затем заставляем интерпретатор отработать эту строку с помощью eval().

В массиве $way мы храним номера родительских элементов. То есть 3, 4, 5. Если level текущего элемента больше level прошлого элемента, добавляем к этому массиву номер текущего элемента. Если они равны - убираем один и заменяем его новым. Если level текущего элемента меньше, чем level прошлого, убираем два номера и добавляем текущий.

Скрипт работает. Проверил.

Только для простоты ключами многоуровневого массива сделал id элементов. Но это вам, я думаю, несущественно.

Исходный массив $list

Получаем $array

Можно сразу в дерево, не назначая предка:

function Nested2Tree(&$nested, $level) {

	$result = array();

	$item = array_shift($nested);

	while(($item["level"] >= $level) && (count($nested) > 0)) {

		$result[] = array(

			"name" => $item["name"],

			"tree" => Nested2Tree($nested, $level + 1),

		);

		$item = array_shift($nested);

	}

	if ($item["level"] < $level) { array_unshift($nested, $item); }

	return $result;

}



$tree = Nested2Tree($nested, 1);

dkameleon, благодарю. То что надо.

Господа и дамы, спасибо огромное всем за помощь.