|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
Нет наработок или кода, если нужно готовое решение - создайте тему в разделе Фриланс и оплатите работу. Название темы включает слова - "Помогите", "Нужна помощь", "Срочно", "Пожалуйста". Название темы слишком короткое или не отражает сути вашего вопроса. Тема исчерпала себя, помните, один вопрос - одна тема Прочитайте правила и заново правильно создайте тему. |
|
Опции темы | Поиск в этой теме |
14.04.2009, 16:36 | #1 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
помогите пожалуйста с рекурсией
Нужно написать подпрограмму, которая бы при рекурсивном обратном обходе дерева подсчитывала сколько раз какой-то элемент входит в дерево.
изначальным вариантом было: int i, t // глобальные переменные. i - это счётчик, значение 0 которому присваивается в main,а t - это само значение,которое при обходе нужно посчитать. obr_obhod ( btree *d ) { if ( d != NULL ) { obr_obhod ( d->left ); if(t==d->info) i++; else ; obr_obhod ( d->right ); } } однако такой вариант не устраивает. нужно избавиться от счётчика i. кто может, подскажите пожалуйста. |
14.04.2009, 16:52 | #2 |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
Так надо?
Код:
|
14.04.2009, 17:24 | #3 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
вроде оно)
а разве при запуске подпрограммы сумма result не обнуляется? |
14.04.2009, 18:23 | #4 |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
Локальные переменные, если мне не изменяет память, не инициализируются нулевыми значениями и изначально хранят "мусор". В любом случае все переменные лучше явно инициализировать
|
14.04.2009, 18:27 | #5 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
ой,а можно Вас попросить словами немного описать как работает эта подпрограмма? просто рекурсия это слабое место из всех слабейших))
|
14.04.2009, 21:03 | #6 |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
По факту мы как бы спускаемся от корня дерева к его листьям. Листовые узлы вернут соответственно 0 или 1 (если узел равен t). Их родители уже прибавят к этому значению еще что требуется и передадут этот результат выше. В общем как бы возвращаемся назад от листьев к корню и суммируем результаты работы нашей рекурсивной функции.
Рекурсивный обход дерева в принципе, если графически представить, то будет то же самое дерево. Принцип рекурсии в данном случае в том, что каждый узел этого дерева сам является деревом и алгоритм обработки каждого узла этого дерева одинаков. Ну как подсчет факториала: 5! = 5*4!, т.е. факториал(N) = N*факториал(N-1). Ну а с "нашим" деревом получается так: количество(дерево) = корень + количество(левое) + количество(правое), где корень - это 0 или 1, в зависимости от (корень = t) левое - это левое поддерево правое - это правое поддерево |
14.04.2009, 21:05 | #7 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
спасибо большое! мне было очень важно и полезно это описание
|
14.04.2009, 21:17 | #8 |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
Надеюсь, что реально помогло, а то объясняю я, мягко говоря, неочень понятно)
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
помогите разобраться с рекурсией с++ | l.e.n.a | Помощь студентам | 1 | 10.02.2009 20:32 |
Помогите с рекурсией | biv171 | Помощь студентам | 1 | 02.11.2008 10:36 |
Помогите с рекурсией | Serejka | Общие вопросы Delphi | 1 | 25.07.2008 15:36 |
Помогите плз с Рекурсией | Dendy | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 03.02.2008 22:44 |