Форум PHP

Всем привет.
Есть задача реализовать вывод обычного дерева, но делать это без рекурсии...
Как-то это возможно сделать?

Обычное дерево это какое?
Я бы юзал массивы, в один массив запихнул бы "детей", в другой "родителей", а потом в цикле выводил бы все, с проверкой на наличие "детя" и если есть - выводить в потоке из массива это "дитя"

Обычное в смысле в базе, где есть 3 поля: id, parent_id, name где parent_id это id родителя.
Как такую таблицу вывести на экран не рекурсией?

Не рекурсией не получится. Если уровень вложенности будет 3 или больше то вы замучаетесь подстраиваться под каждый уровень и описывать все возможные варианты.

Самое легкое (в плане производительности) решение:

Предположим добавление комментариев к теме выглядит следующим образом:

$arr = array(      array('id'=>1, 'pid'=>0, 'name'=>'Comment 1'),       array('id'=>2, 'pid'=>1, 'name'=>'Comment 1.1'),        array('id'=>4, 'pid'=>2, 'name'=>'Comment 1.1.1'),        array('id'=>5, 'pid'=>2, 'name'=>'Comment 1.1.2'),        array('id'=>7, 'pid'=>2, 'name'=>'Comment 1.1.3'),       array('id'=>3, 'pid'=>1, 'name'=>'Comment 1.2'),       array('id'=>6, 'pid'=>1, 'name'=>'Comment 1.3'),      array('id'=>8, 'pid'=>0, 'name'=>'Comment 2'),       array('id'=>12, 'pid'=>8, 'name'=>'Comment 2.1'),       array('id'=>17, 'pid'=>8, 'name'=>'Comment 2.2'),        array('id'=>13, 'pid'=>12, 'name'=>'Comment 2.1.1'),         array('id'=>16, 'pid'=>13, 'name'=>'Comment 2.1.1.1'),      array('id'=>9, 'pid'=>0, 'name'=>'Comment 3'),       array('id'=>14, 'pid'=>9, 'name'=>'Comment 3.1'),        array('id'=>15, 'pid'=>14, 'name'=>'Comment 3.1.1'),      array('id'=>10, 'pid'=>0, 'name'=>'Comment 4'),      array('id'=>11, 'pid'=>0, 'name'=>'Comment 5'),      );

Каждый комментарий имеет id и id родителя (pid). Ответ на тему должен принимать pid = 0, а ответ на комментарий — id комментария на который отвечаете соответственно. В конечном итоге дерево должно выглядеть так, как показано в массиве образце.

Чтобы раскрыть дерево за 1 SQL, достаточно достать из базы все комментарии имеющие идентификатор темы, отсортировав их так:

ORDER BY pid ASC, id ASC

В результате получим следующий массив.

$arr = array(      array('id'=>1, 'pid'=>0, 'name'=>'Comment 1'),      array('id'=>8, 'pid'=>0, 'name'=>'Comment 2'),      array('id'=>9, 'pid'=>0, 'name'=>'Comment 3'),      array('id'=>10, 'pid'=>0, 'name'=>'Comment 4'),      array('id'=>11, 'pid'=>0, 'name'=>'Comment 5'),       array('id'=>2, 'pid'=>1, 'name'=>'Comment 1.1'),       array('id'=>3, 'pid'=>1, 'name'=>'Comment 1.2'),       array('id'=>6, 'pid'=>1, 'name'=>'Comment 1.3'),        array('id'=>4, 'pid'=>2, 'name'=>'Comment 1.1.1'),        array('id'=>5, 'pid'=>2, 'name'=>'Comment 1.1.2'),        array('id'=>7, 'pid'=>2, 'name'=>'Comment 1.1.3'),      array('id'=>12, 'pid'=>8, 'name'=>'Comment 2.1'),       array('id'=>17, 'pid'=>8, 'name'=>'Comment 2.2'),       array('id'=>14, 'pid'=>9, 'name'=>'Comment 3.1'),       array('id'=>13, 'pid'=>12, 'name'=>'Comment 2.1.1'),        array('id'=>16, 'pid'=>13, 'name'=>'Comment 2.1.1.1'),        array('id'=>15, 'pid'=>14, 'name'=>'Comment 3.1.1'),      );

Теперь требуется изменить структуру массива.

for ($i = 0, $c = count($arr); $i < $c; $i++)      {        $new_arr[$arr[$i]['pid']][] = $arr[$i];      }

И завершающая рекурсионная функция.

function my_sort($data, $parent = 0, $level = 0)      {        $arr = $data[$parent];        for($i = 0; $i < count($arr); $i++)        {          echo '<div style="padding-left:' . $level . 'px;">';          echo $arr[$i]['name'];            if(isset($data[$arr[$i]['id']])) my_sort($data, $arr[$i]['id'], 20);          echo '</div>';        }      }

Теперь чтобы показать все дерево одним разом, достаточно вызвать

my_sort($new_arr, 0);

Чтобы показать часть дерева, вторым параметром нужно указать id комментария, чьих потомков вы желаете раскрыть.

Например:

my_sort($new_arr, 8); my_sort($new_arr, 13);

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

[поправлено модератором]

Спасибо за ссылку.
А какой должна быть структура таблицы, чтобы можно было по корневым элементам выбрать все подветки одним запросом?

Смотрите в сторону алгоритмов вроде NestedSet. Тогда выборка всего дерева будет происходить одним запросом + все будет в нужном порядке. Остается только вывести все это дело в цикле.

в чем конкретно проблема? не нравится то, что делаете много запросов на каждой вложенной группе, или просто принципиально хотите без рекурсии?

1) см. дату топика.
2) странный у вас вопрос.

1) да, виноват
2) чем же он странный? сабж, на мой взгляд, куда более странный

чем же он странный? человек хочет взамест много запросов один запрос, помоему вполне себе нормальное желание :)

а по-моему бред, если он пытается добиться этого желаемого отказом от рекурсии.

вы полагаете NestedSet это бред?

для простой менюшки думаю да

Так как кто нибудь знает как такое на PHP трелизовать?
А то в инете только на билдере и дельфи примеры...

если без рекурсии, надо точно знать, сколько уровней. потом делать вложенные циклы. например, в меню 4 уровня - один цикл перебирает родителей, внутри него еще 3 вложенных друг в друга цикла, которые перебирают детей с соответствущими id родителей.

вложенные циклы
это таже рекурсия только вид сбоку, да еще и обрезаная

Пусть и поздно, но написал и отладил за час примерно. Может кому поможет.
Вывод дерева каталогов и файлов без рекурсии.

Если просто открыть file.php
http://host/file.php
то покажет все подпапки и файлы хостинга.

Если к адресной строке добавить переменную path=c:/
http://host/file.php?path=c:/
то покажет все подпапки и файлы по данному пути.

Если к адресной строке добавить переменную files=off
http://host/file.php?path=/&files=off
http://host/file.php?path=c:/windows/&files=off
http://host/file.php?files=off
то покажет только папки и подпапки без файлов по текущему пути.

<? import_request_variables("gp"); set_time_limit(60); ?> <pre> <? //если путь не указан, то показывать с корня сайта if(!isset($path)) $path=$_SERVER['DOCUMENT_ROOT']; //если в конце пути нет слеша, то добавить его if($path[strlen($path)-1]!="/") $path.="/"; print "<b style='font-size: 20px'>{$path}</b><hr>"; $dir=scandir($path); $arr[]=$dir; $p[]=$path; $lvl=0; $ch=1; while(1) {     //если изменение вниз, то читаем новую папку     if($ch<0)     {         //print "Изменение вниз (заходим в папку). Читать папку $path.\n";         $path.="{$cur}/";         $dir=scandir($path);         $ch=0;         $lvl++;     }          //если изменение вверх (папка закончилась), то берем папку выше     if($ch>0)     {         if(count($arr)==0)         {             //корневая папка закончилась, значит препрвать вывод дерева             //print "Элементов больше нет.";             break;         }         //print "Изменение вверх (взять данные о предыдущей папке).\n";         $dir=array_pop($arr);         $path=array_pop($p);         $lvl--;         $ch=0;     }          //если изменений нет     if(count($dir)==0)     {         //print "Элементов в текущей папке больше нет. Изменить вверх.\n";         $ch=1;         continue;     }          //взять следующий элемент и убрать его из списка текущей папки     $cur=array_shift($dir);     if($cur=="." || $cur=="..")     {         //print "Ненужные папки.\n";         continue;     }          //если папка, то сохранить текущее положение и перейти ниже     if(is_dir("{$path}{$cur}"))     {         //for($i=0;$i<=$lvl;$i++) print "&nbsp;&nbsp;";         print "<b>{$path}{$cur}/</b>\n";         //print "Текущий элемент -- папка.\n";         //запоминаем последний путь         $p[]=$path;         //запоминаем последнее содержимое         $arr[]=$dir;         $ch=-1;     }          //если файлы не показывать, то пропускаем, т.к. на папку уже проверили     if($files=="off") continue;     //если файл, то вывести на экран     if(is_file("{$path}{$cur}"))     {         for($i=0;$i<=$lvl;$i++) print "&nbsp;&nbsp;";         print "{$cur}\n";     }      } ?> </pre>

klaxwork, это шутка такая? У вас рекурсия заменена обычным циклом, что в принципе не имеет смысла.
Автор топика спрашивал как избавится от рекурсии, которая влечет за собой большое количество запросов при обращении к базе данных.

Был раньше на форуме гуру Trianon:

раз, два, три

Два года ответ готовили?

Я здесь при чем? Был вопрос - дал ответ! Не я поднял тему 2011 года )))