Подсчитать количество элементов на n-м уровне бинарного дерева - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Помогите пожалуйста написать рекурсивную функцию или процедуру, которая подсчитывает количество элементов на n-м уровне бинарного дерева. Обход дерева рекурсивно выглядит так:
Листинг программы
  1. obhod(btree*d)
  2. {
  3. if(d!=NULL)
  4. {
  5. обработка(d);
  6. obhod(d->left);
  7. obhod(d->right);}
  8. }
  9. }
На всякий случай напишу, как ввожу дерево:
Листинг программы
  1. btree *build_tree ()
  2. {
  3. btree *d;
  4. char sym;
  5. fscanf(fp,"%c",&sym);
  6. switch(sym)
  7. {
  8. case '(': {
  9. d=new btree;
  10. fscanf(fp, "%c", &sym);
  11. d->elem=sym;
  12. d->left=build_tree();
  13. d->right=build_tree();
  14. fscanf(fp, "%c",&sym);
  15. return d;
  16. }
  17. case '0': return NULL;
  18. case ',': d=build_tree();
  19. return d;
  20. }
  21. return NULL;
  22. }
ну и сам тип "дерево":
Листинг программы
  1. struct btree
  2. {
  3. char elem;
  4. btree *left;
  5. btree *right;
  6. };
Очень нужна помощь!!! Уже трое суток мучаюсь, и никак!

Решение задачи: «Подсчитать количество элементов на n-м уровне бинарного дерева»

textual
Листинг программы
  1. /* подсчет количества элементов на уровне level */
  2. int nelem(struct btree *p, int level)
  3. {
  4.     static int i = 0, cnt = 0;
  5.    
  6.     if(p == NULL)
  7.        return 0;
  8.     else if(i == level)
  9.        return p->elem;
  10.     else {
  11.        i++;
  12.        cnt += nelem(p->left, level);
  13.        cnt += nelem(p->right, level);
  14.     }
  15.     return cnt;
  16. }

Объяснение кода листинга программы

В данном коде реализована функция nelem, которая подсчитывает количество элементов на n-м уровне бинарного дерева.

  1. int nelem(struct btree *p, int level) — объявление функции с двумя аргументами: указатель на узел дерева p и уровень level.
  2. static int i = 0, cnt = 0; — объявление двух статических переменных: счётчика узлов i и счётчика элементов cnt.
  3. Если переданный узел p равен NULL, то функция возвращает 0. Это соответствует концу дерева.
  4. Если i равно level, то функция возвращает значение p->elem. Это элемент текущего уровня.
  5. Если i меньше level, то происходит следующее: 5.1. i++ — увеличение счётчика узлов. 5.2. cnt += nelem(p->left, level); — рекурсивный вызов функции для левого поддерева с передачей уровня level. Результат добавляется к счётчику элементов cnt. 5.3. cnt += nelem(p->right, level); — рекурсивный вызов функции для правого поддерева с передачей уровня level. Результат также добавляется к счётчику элементов cnt.
  6. В конце функция возвращает значение счётчика элементов cnt.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 4.2 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы