Дерево (tree) категорий на PHP

Подробности
</программирование>

Очень часто встречается задача преобразования массива данных, например, категорий в дерево (структуру с неограниченным уровнем вложенности). В этом случае обычно каждый элемент массива содержит данные о родителе. В случае с категориями это ID категории-родителя (parent).

Дано: массив, у которого ключи - ID категорий, а значения - объекты-записи, одно из свойство которых - parent, указывающее на родительскую категорию.
Задача: сначала преобразовать массив данных в дерево, а затем вывести это дерево на страницу в виде списка с неограниченным уровнем вложенности.

Решение:

Обе задачи элегантно решаются рекурсией.

private function makeTree($items,$root=0) {
	// будем строить новый массив-дерево
	$nitems = array();
	foreach($items as $ki=>$item) {
		/* проверяем, относится ли родитель элемента к самому
		верхнему уровню и не ссылается ли на самого себя */
		if($item->parent==$root&&$ki!=$item->parent) {
			// удаляем этот элемент из общего массива
			unset($items[$ki]);
			$nitems[$ki]=array(
			    // однако сохраним его в дереве
			    $ki=> $item,
			    /* пробежим еще раз, но с уже
			    меньшим числом элементов */
			    'children'=>$this->makeTree($items,$ki)
			);
		}
	}
	return $nitems;
}

 

Мы пробегаем через все элементы массива. Если уровень (parent) элемента - корневой (root, самый верхний), мы сохраняем этот элемент в дереве и создаем для него ветку потомков (children). Чтобы ее сформировать функция вызывает саму себя. Но предварительно мы уменьшаем число элементов в исходном массиве, удаляя текущий элемент, поскольку он не может быть потомком самого себя. 

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

Основная идея проста: мы сохраняем в массиве на текущем уровне и возвращаем в качестве потомков только те элементы, у котороых родитель (parent) - элемент строго предыдущего уровня. Эти элементы удаляются из исходного массива, а оставшиеся подвергаются очередной обработке на проверку parent через вызов функции самой себя. При этом корневыми указываются сохраненные элементы (удаленные из исходного массива) на данном уровне.

function printTree($tree) {
    // если у текущей ветки дерева есть собственные ветки
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        // пробегаем по этим веткам, обозначая их
        foreach($tree as $kn=>$node) {
            echo '<li>'.$node[$kn]->name;
            // а также по своим веткам каждой обозначенной ветки
            printTree($node['children']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

 

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

Наверх