Написать рекурсивную функцию подсчета количества вхождений в дерево заданного числа на заданном уровне - C (СИ)
Формулировка задачи:
Задано бинарное дерево,в вершинах которого расположены целые числа.Написать рекурсивную функцию подсчета количества вхождений в дерево заданного числа на заданном уровне.
Можно так написать?
#include <stdio.h>
int count (struct node tree, int a, int level)
{
if (tree==NULL)
return 0;
if (tree->val==a)
return 1;
count (tree->left, level-1)+count (tree->right, level-1);
}
int main(void) {
// your code goes here
return 0;
}Решение задачи: «Написать рекурсивную функцию подсчета количества вхождений в дерево заданного числа на заданном уровне»
textual
Листинг программы
int counter(struct node tree, int number, int level)
{
if (level == 0) return (tree->val == number ? 1 : 0);
return (tree->left ? counter(tree->left, number, level-1 : 0)) + (tree->right ? counter(tree->right, number, level-1 : 0));
}
Объяснение кода листинга программы
- Функция
counterпринимает три аргумента:tree(структура, представляющая узел дерева),number(число, которое нужно подсчитать в дереве) иlevel(уровень, на котором нужно подсчитать число). - Если
levelравно 0, то функция возвращает 1, если значение в узле равноnumber, иначе возвращает 0. - В противном случае, функция рекурсивно вызывает саму себя с аргументами
tree->leftиnumber(левое поддерево и число), а такжеtree->rightиnumber(правое поддерево и число). Аргументlevelуменьшается на 1 для каждого поддерева. - Результаты подсчета из обоих поддеревьев складываются и возвращаются как итоговый результат.