Подсчитать количество элементов на 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
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д