| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Бинарные деревья |
| Автор: Церада 25.2.2011, 20:45 | ||
| Меня наверное, как нерадивого студента можно убить. Нужно написать алгоритм префиксного НЕрекурсивного обхода дерева (иными словами сверху-вниз). Знаю только, что порядок обхода должен быть таким: Корень, Левая ветвь, Правая ветвь. Но когда начинаю писать алгоритм - возникает вопрос: как пометить корень? В стеке поле добавлять нехорошо, а как иначе - не додумаюсь Добавлено @ 20:52 о. а если например так
дальше идем по левому вниз, а потом перепрыгиваем на q |
| Автор: HaronDDC 25.2.2011, 21:51 |
| Хм... подумал, видимо, без дополнительной памяти тут все равно не обойтись. Классический алгоритм поиска в ширину в графе также использует очередь из так сказать "фронта" волны не просмотренных вершин. |
| Автор: Церада 26.2.2011, 10:14 |
| Поиск в ширину я хоть понимаю как осуществлять. Перешел на уровень вниз - закинул с стек. Полез вверх по дереву - на выход. А тут как обойти.. Загадка. |
| Автор: Earnest 2.3.2011, 16:08 |
| Вся разница между обходом в ширину и в глубину - куда складываются дочерние элементы - в очередь или в стек. При обходе в глубину можно обойтись без явного стека, за счет неявного (рекурсии). Но формально - никакой разницы. Пройденные элементы в любом случае нужно помечать. |
| Автор: Церада 6.3.2011, 20:35 |
| ясно, спасибо! |