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