Подсчитать количество элементов на 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-м уровне бинарного дерева.

  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
Похожие ответы