Инструменты пользователя

Инструменты сайта


dev:php:nerekursivnyj_metod_obxoda_dereva

Нерекурсивный метод обхода дерева

Представим, что у нас есть некий массив, представляющий из себя иерархическое дерево значение, скажем, имён страниц:

$data = array(
   "Первая страница",
   array(
      array(
         "Страница третьей вложенности",
         ),
      "Первая дочерняя страница",
      "Вторая дочерняя страница",
      ),
   "Вторая страница",
   );

Тогда код обхода будет выглядеть следующим образом:

$stack = array(&$data);
while(count($stack))
{
   $root = array_pop($stack);
   foreach ($root as $name)
   {
      if (is_array($name)) array_push($stack, $name);
      else new Page($name, $root); // (создание представителя класса страницы с указанными именем и родителем), или что там нам/вам надо сделать с этим именем...
   }
}

Недостаток такого подхода в том, что алгоритм не «кидается» в первый же найденный массив дочерних элементов, а сначала просматривает весь текущий уровень. Из-за этого невозможно выполнить как минимум две функции:

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

Зато такой алгоритм удобно применять при поиске какого-либо значения в массиве. С другой стороны, рекурсивный поиск пока никто не отменял; у последнего также будут отсутвовать перечисленные недостатки.

Расход памяти в рекурсивном алгоритме зависит от глубины ветвлений, а в нерекурсивном - от общего количества ветвлений.

Дискуссия

Enter your comment
 
dev/php/nerekursivnyj_metod_obxoda_dereva.txt · Последние изменения: 16.11.2009 20:26 (внешнее изменение)

Инструменты страницы