Generowanie drzewa z tablicy asocjacyjnej

Mamy podaną tablicę zawierającą tablice asocjacyjne reprezentujące poszczególne elementy drzewa. Te wewnętrzne tablice zawierają id elementu, id rodzica oraz nazwę. Z tej struktury wygenerujemy drzewo. Nasza początkowa tablica:

$arr = array
(
	array
	(
		'id' => '1',
		'parent_id' => '2',
		'name' => 'Name 1',
	),
	array
	(
		'id' => '2',
		'parent_id' => '6',
		'name' => 'Name 2',
	),
	array
	(
		'id' => '3',
		'parent_id' => '5',
		'name' => 'Name 3',
	),
	array
	(
		'id' => '4',
		'parent_id' => '2',
		'name' => 'Name 4',
	),
	array
	(
		'id' => '5',
		'parent_id' => '0',
		'name' => 'Name 5',
	),
	array
	(
		'id' => '6',
		'parent_id' => '0',
		'name' => 'Name 6',
	),
	array
	(
		'id' => '7',
		'parent_id' => '6',
		'name' => 'Name 7',
	),
	array
	(
		'id' => '8',
		'parent_id' => '2',
		'name' => 'Name 8',
	),
	array
	(
		'id' => '9',
		'parent_id' => '5',
		'name' => 'Name 9',
	)
);
Najpierw przeindeksujemy tablicę. W nowej tablicy $indexed_arr każdy klucz będzie id elementu natomiast wartością będzie tablica z danymi dotyczącymi elementu ($item). W tablicy z danymi dodajemy informację o potomkach (klucz children).
$indexed_arr = array();
foreach($arr as $item)
{
	$item['children'] = array();
	$indexed_arr[$item['id']] = $item;
}
Rozpoczynamy teraz właściwą budowę drzewa. Przechodzimy przez wcześniej zaindeksowaną tablicę. Ważną rzeczą jest przypisanie do zmiennej $item referencji do elementu aby pracować na oryginalnym elemencie. Następnie wykonujemy sprawdzenie czy element ma rodzica. Jeśli nie (parent_id = 0) to do elementu drzewa przypisujemy jego samego (referencja). W przeciwnym wypadku jeśli istnieje parent_id modyfikujemy tablicę w ten sposób, że do rodzica przypisujemy tablicę (referencja) z dziećmi (indeks children).
$tree = array();
foreach($indexed_arr as $id => $v)
{
	$item = &$indexed_arr[$id];
	if($item['parent_id'] == 0)
	{
		$tree[$id] = &$item;
	}
	elseif(isset($indexed_arr[$item['parent_id']]))
	{
		$indexed_arr[$item['parent_id']]['children'][$id] = &$item;
	}
	else
	{
		$tree['_orphans_'][$id] = &$item;
	}
}

print_r($tree);
Wynik funkcji print_r jest następujący.
Array
(
    [5] => Array
	(
		[id] => 5
		[parent_id] => 0
		[name] => Name 5
		[children] => Array
		(
			[3] => Array
			(
				[id] => 3
				[parent_id] => 5
				[name] => Name 3
				[children] => Array
				(
				)

			)
			[9] => Array
			(
				[id] => 9
				[parent_id] => 5
				[name] => Name 9
				[children] => Array
				(
				)
			)
		)
	)
    [6] => Array
	(
		[id] => 6
		[parent_id] => 0
		[name] => Name 6
		[children] => Array
		(
			[2] => Array
			(
				[id] => 2
				[parent_id] => 6
				[name] => Name 2
				[children] => Array
				(
					[1] => Array
					(
						[id] => 1
						[parent_id] => 2
						[name] => Name 1
						[children] => Array
						(
						)
					)
					[4] => Array
					(
						[id] => 4
						[parent_id] => 2
						[name] => Name 4
						[children] => Array
						(
						)
					)
					[8] => Array
					(
						[id] => 8
						[parent_id] => 2
						[name] => Name 8
						[children] => Array
						(
						)
					)
				)
			)
			[7] => Array
			(
				[id] => 7
				[parent_id] => 6
				[name] => Name 7
				[children] => Array
				(
				)
			)
		)
	)
)