Подсчитать количество элементов на n-м уровне бинарного дерева - C (СИ)
Формулировка задачи:
Помогите пожалуйста написать рекурсивную функцию или процедуру, которая подсчитывает количество элементов на n-м уровне бинарного дерева.
Обход дерева рекурсивно выглядит так:
На всякий случай напишу, как ввожу дерево:
ну и сам тип "дерево":
Очень нужна помощь!!! Уже трое суток мучаюсь, и никак!
obhod(btree*d)
{
if(d!=NULL)
{
обработка(d);
obhod(d->left);
obhod(d->right);}
}
}btree *build_tree ()
{
btree *d;
char sym;
fscanf(fp,"%c",&sym);
switch(sym)
{
case '(': {
d=new btree;
fscanf(fp, "%c", &sym);
d->elem=sym;
d->left=build_tree();
d->right=build_tree();
fscanf(fp, "%c",&sym);
return d;
}
case '0': return NULL;
case ',': d=build_tree();
return d;
}
return NULL;
}struct btree
{
char elem;
btree *left;
btree *right;
};Решение задачи: «Подсчитать количество элементов на n-м уровне бинарного дерева»
textual
Листинг программы
/* подсчет количества элементов на уровне level */
int nelem(struct btree *p, int level)
{
static int i = 0, cnt = 0;
if(p == NULL)
return 0;
else if(i == level)
return p->elem;
else {
i++;
cnt += nelem(p->left, level);
cnt += nelem(p->right, level);
}
return cnt;
}
Объяснение кода листинга программы
В данном коде реализована функция nelem, которая подсчитывает количество элементов на n-м уровне бинарного дерева.
int nelem(struct btree *p, int level)— объявление функции с двумя аргументами: указатель на узел дереваpи уровеньlevel.static int i = 0, cnt = 0;— объявление двух статических переменных: счётчика узловiи счётчика элементовcnt.- Если переданный узел
pравенNULL, то функция возвращает 0. Это соответствует концу дерева. - Если
iравноlevel, то функция возвращает значениеp->elem. Это элемент текущего уровня. - Если
iменьшеlevel, то происходит следующее: 5.1.i++— увеличение счётчика узлов. 5.2.cnt += nelem(p->left, level);— рекурсивный вызов функции для левого поддерева с передачей уровняlevel. Результат добавляется к счётчику элементовcnt. 5.3.cnt += nelem(p->right, level);— рекурсивный вызов функции для правого поддерева с передачей уровняlevel. Результат также добавляется к счётчику элементовcnt. - В конце функция возвращает значение счётчика элементов
cnt.