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

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


dev:php:nerekursivnyj_metod_obxoda_dereva

====== Нерекурсивный метод обхода дерева ====== Представим, что у нас есть некий массив, представляющий из себя иерархическое дерево значение, скажем, имён страниц: <code php> $data = array( "Первая страница", array( array( "Страница третьей вложенности", ), "Первая дочерняя страница", "Вторая дочерняя страница", ), "Вторая страница", ); </code> Тогда код обхода будет выглядеть следующим образом: <code php> $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); // (создание представителя класса страницы с указанными именем и родителем), или что там нам/вам надо сделать с этим именем... } } </code> Недостаток такого подхода в том, что алгоритм не "кидается" в первый же найденный массив дочерних элементов, а сначала просматривает весь текущий уровень. Из-за этого невозможно выполнить как минимум две функции: - без ввода дополнительных свойств массива для помещаемого в стэк элемента узнать текущий уровень вложенности; - последовательность прохождения вложенных элементов непредсказуема для неизвестного массива, из-за чего нельзя, например, по такому алгоритму построить дерево меню. Зато такой алгоритм удобно применять при поиске какого-либо значения в массиве. С другой стороны, рекурсивный поиск пока никто не отменял; у последнего также будут отсутвовать перечисленные недостатки. Расход памяти в рекурсивном алгоритме зависит от глубины ветвлений, а в нерекурсивном - от общего количества ветвлений.

Дискуссия

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

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