 |
|
Модераторы: Daevaorn |
 
|
|
Бинарные деревья, Префиксный обход 
| Церада |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 12.10.2008 Где: Барнаул Репутация: нет Всего: нет |
Меня наверное, как нерадивого студента можно убить.
Нужно написать алгоритм префиксного НЕрекурсивного обхода дерева (иными словами сверху-вниз). Знаю только, что порядок обхода должен быть таким: Корень, Левая ветвь, Правая ветвь. Но когда начинаю писать алгоритм - возникает вопрос: как пометить корень? В стеке поле добавлять нехорошо, а как иначе - не додумаюсь Добавлено @ 20:52 о. а если например так
дальше идем по левому вниз, а потом перепрыгиваем на q Это сообщение отредактировал(а) Церада - 25.2.2011, 20:53 |
|||
|
||||
Загрузка ...
| HaronDDC |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 6 Регистрация: 9.8.2007 Репутация: нет Всего: нет |
Хм... подумал, видимо, без дополнительной памяти тут все равно не обойтись.
Классический алгоритм поиска в ширину в графе также использует очередь из так сказать "фронта" волны не просмотренных вершин. |
|||
|
||||
| Церада |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 12.10.2008 Где: Барнаул Репутация: нет Всего: нет |
Поиск в ширину я хоть понимаю как осуществлять. Перешел на уровень вниз - закинул с стек. Полез вверх по дереву - на выход. А тут как обойти.. Загадка.
|
|||
|
||||
| Earnest |
|
|||
 Эксперт  Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 53 Всего: 183 |
Вся разница между обходом в ширину и в глубину - куда складываются дочерние элементы - в очередь или в стек. При обходе в глубину можно обойтись без явного стека, за счет неявного (рекурсии). Но формально - никакой разницы. Пройденные элементы в любом случае нужно помечать.
-------------------- ... |
|||
|
||||
| Церада |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 12.10.2008 Где: Барнаул Репутация: нет Всего: нет |
ясно, спасибо!
|
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0691 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |