@MaMkO

Можно ли оптимизировать рекурсию?

Здравствуйте, начинаю осваивать рекурсию, написал код для вывода многоуровневых категорий
class Category
{

  public array $tree = [];

  // Построение дерева
  public function createTree($data)
  {
    //Ищем элементы без родительских
    foreach ($data as $item) {
        if ($item['parent_id'] === null) {
          $this->tree[$item['id']] = $item;
          $this->createElemTree($data, $this->tree[$item['id']], $item['id']);
        }
    }

    return $this->tree;
  }

  // Добавление элементов как дочерних
  public function createElemTree($data, &$parentElem, $parentId = null)
  {
    foreach ($data as $key=>$item) {
        if ($item['parent_id'] === $parentId) {
          $parentElem['children'][$key] = $item;
          $this->createElemTree($data, $parentElem['children'][$key], $item['id']);
        }
    }
  }
}


$data = [
    ['id' => 0, 'name' => 'Электроника', 'parent_id' => null],
    ['id' => 1, 'name' => 'Косметика', 'parent_id' => null],
    ['id' => 2, 'name' => 'Инструменты', 'parent_id' => null],
    ['id' => 3, 'name' => 'Телефоны', 'parent_id' => 0],
    ['id' => 4, 'name' => 'Духи', 'parent_id' => 1],
    ['id' => 5, 'name' => 'Samsung', 'parent_id' => 3]
];

$category = new Category();
$tree = $category->createTree($data);


Интересует такой вопрос - можно ли как-то оптимизировать текущий код?
  • Вопрос задан
  • 154 просмотра
Решения вопроса 1
Alexandroppolus
@Alexandroppolus
кодир
Это тривиально делается за линейное время и без рекурсии.
Сначала составляем словарь dict (id => узел дерева), в твоем случае таким словарем может быть исходный массив, если id идут по порядку от нуля, и $data[id] всегда содержит элемент с таким id, а элементы массива станут узлами дерева.
Потом обходим массив снова и в чилдрены dict[$item['parent_id']] добавляем $item.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы