помогите пожалуйста с рекурсией

[Petruha-nsk]

Нужно написать подпрограмму, которая бы при рекурсивном обратном обходе дерева подсчитывала сколько раз какой-то элемент входит в дерево.
изначальным вариантом было:

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. кто может, подскажите пожалуйста.

[pu4koff]

Так надо?

int obr_obhod ( btree *d, int t)
{
  int result = 0;
  if ( d != NULL )
  {
    if(t == d->info) result++;
    result += obr_obhod (d->left, t) + obr_obhod (d->right, t);
  }
  return result;
}

[Petruha-nsk]

вроде оно)
а разве при запуске подпрограммы сумма result не обнуляется?

[pu4koff]

Локальные переменные, если мне не изменяет память, не инициализируются нулевыми значениями и изначально хранят "мусор". В любом случае все переменные лучше явно инициализировать

[Petruha-nsk]

ой,а можно Вас попросить словами немного описать как работает эта подпрограмма? просто рекурсия это слабое место из всех слабейших))

[pu4koff]

По факту мы как бы спускаемся от корня дерева к его листьям. Листовые узлы вернут соответственно 0 или 1 (если узел равен t). Их родители уже прибавят к этому значению еще что требуется и передадут этот результат выше. В общем как бы возвращаемся назад от листьев к корню и суммируем результаты работы нашей рекурсивной функции.
Рекурсивный обход дерева в принципе, если графически представить, то будет то же самое дерево. Принцип рекурсии в данном случае в том, что каждый узел этого дерева сам является деревом и алгоритм обработки каждого узла этого дерева одинаков. Ну как подсчет факториала: 5! = 5*4!, т.е. факториал(N) = N*факториал(N-1).
Ну а с "нашим" деревом получается так:
количество(дерево) = корень + количество(левое) + количество(правое), где корень - это 0 или 1, в зависимости от (корень = t)
левое - это левое поддерево
правое - это правое поддерево

[Petruha-nsk]

спасибо большое! мне было очень важно и полезно это описание

[pu4koff]

Надеюсь, что реально помогло, а то объясняю я, мягко говоря, неочень понятно)