Нерекурсивная отрисовка дерева в виде HTML списка?

noiz_music

Всем привет.
Что-то я туплю. Подскажите, пожалуйста следующую вещь.
Есть дерево, где у parent'a может быть сколько угодно child'ов, ссылки на которые у parent'a сожержатся в массиве childs.
Как мне нерекурсивно отрисовать его структуру в виде HTML списка типа:



<ul>

<li>blah

     <ul>

      <li>blah1</li>

      <li>blah2</li>

     </ul>

</li>

<li>blah3</li>

</ul>

Спасибо!

yolki

что такое "нерекурсивно"?
в чём проблема использовать рекурсию?
на каком языке? Если он достаточно хороший в смысле динмаической памяти (типа C(++)/Delphi, насчёт java не в курсе) - то любая рекурсия может быть сделана "нерекурсивно" на искусственном стеке. только нафига?

noiz_music

> что такое "нерекурсивно"?
итеративно
язык perl
да какая разница какой язык
извини, но твой ответ совсем не по теме

ppplva

все правильно говорит. Задача по сути - рекурсивна. Итеративное решение по-любому будет напоминать рекурсию на искусственном стеке.

noiz_music

да понятно все это
ну и пусть стэк
хочется сделать это все циклах, чтобы избежать путаницы perl'овог scoping'a особенно например в контексте mod_perl'a, если это о чем-то говорит, но не суть
хорошо, скажу вот так
есть cтэк stack
есть операции push и pop
есть node - узел дерева
у node есть массив childs, которые в свою очередь тоже являются node
так же у node есть value
есть цикл foreach (node->childs) который проходит по всем потомкам
есть операция проверки стека на пустоту isempty(stack)
как в этих терминах мне описать проход по дереву так как я описал выше
?
anybody?

ppplva



push(root)

while стек не пуст:

  pop(node)

  print node->value

  foreach child:

    push child

Наверное, я где-то туплю, потому что слишком просто...

noiz_music

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



foreach node->childs

print "<ul>";

recursive_search(child);

print "</ul>";

а вот как это сделать в выше написанном варианте?

ppplva

Типа так



push(root)

while стек не пуст:

  pop(node)

  if node==end_of_children:

    print "</ul>"

  else:

    print node->value

    push end_of_children

    foreach child:

      push child

Dasar

на первый взгляд - фигня (а где вывод остальных тегов?)

ppplva

Это не программа, это proof of concept.
Кому надо - вставит.

rosali

В действительности достаточно хранить текущую ноду и глубину числом. стек _не_ нужен.

bansek

это если в ноде есть ссылку на родительскую имхо

Оставить комментарий