Обход дерева без рекурсии и без стека

[khizhaster]

Простите, вы Кнута читали?

[vsvasya]

ещё нет) это в todo на ближайшее время )

[YasonBy]

Прежде чем делать открытие — загляни в справочник.

К. Прутков-инженер «Советы начинающему гению»

[dimsmol]

напоминает обход лабиринта без циклов с одним входом — идем все время держась за левую (или правую) стену :-)

[ZZZ_Sochi]

А зачем? В большинстве случаев рекурсия вполне приемлема. В тех случаях, где не приемлема рекурсия, пойдёт стандартный стек. А настолько глубокого дерева, где стек будет неработоспособен я не знаю.
ИМХО — баловство.

[general]

Не совсем так. Дерево из 100,000 элементов вполне может быть высотой в 100,000 элементов.

[ZZZ_Sochi]

Это настолько частный случай, что в реальной практики врядли с ним встретишься.
Ну и для обсчёта таких специфических данных надо использовать специфические языки знающие, что такое хвостовая рекурсия.

[vsvasya]

обновил пост, дописал в конце — почему родилась эта штука )

[vsvasya]

Очень удобно, когда нужно сделать кучу разных действий с деревом, в разных местах.
Если рекурсия — то приходится писать кучу вспомогательных неудобных функций.
Особенно если доступ к дереву нужен из другого класса.

Спасибо! Сейчас допишу это в пост.

[ZZZ_Sochi]

Чего-то я не уловил сути… Зачем нужны «вспомогательные функции»?
Да, я сам не люблю рекурсию, но иногда она выглядет куда красивее огорода со стеком или вот таким решением.
Ну ладно, не буду спорить, благо, что решение приятное и не сложное. Просто хочу сказать, что это довольно специфическая вещь и нужна не часто, но стоит иметь такое решение в виду.
Собственно у Кнута на эту тему было красиво…

[vsvasya]

обновил пост )

[general]

Ждем статью «Сортировка менее чем за n^2»

[ZZZ_Sochi]

+1

[MOHAX]

тогда уж так «красивая сортировка за n^2, а не тот огород с n * log(n)»

[dmbreaker]

Ага, но с блэкджеком и шлюхами :)

[Wyrd]

Вы что-то пропустили… есть такая штука, называется boost::graph, которая в частности применима к деревьям.

Там есть:
* Различные варианты представления графа в памяти (можно, например, использовать граф, оптимизированный под поиск, а можно оптимизированный под добавление элементов)
* Хранение данных не только в узлах, но и в связях между узлами.
* Двусторонние/односторонние связи.
* В полпинка (в 100 строчек) делается вывод графа в png файлы (через graphvis).
* Куча разных итераторов, перебирающих граф в разных порядках.
* Уже реализованные разные алгоритмы, вроде поиска кратчайшего пути.

и т.д.

[vsvasya]

спасибо, смотрю