Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/35: Рейтинг темы: голосов - 35, средняя оценка - 4.86
0 / 0 / 0
Регистрация: 02.12.2008
Сообщений: 23
1

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

11.04.2009, 19:01. Просмотров 7154. Ответов 8
Метки нет (Все метки)

Помогите пожалуйста написать рекурсивную функцию или процедуру, которая подсчитывает количество элементов на n-м уровне бинарного дерева.

Обход дерева рекурсивно выглядит так:

C
1
2
3
4
5
6
7
8
9
obhod(btree*d)
{
if(d!=NULL)
 {
  обработка(d);
  obhod(d->left);
  obhod(d->right);}
 }
}
На всякий случай напишу, как ввожу дерево:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
ну и сам тип "дерево":
C
1
2
3
4
5
6
struct btree
  {
  char elem;
  btree *left;
  btree *right;
  };
Очень нужна помощь!!! Уже трое суток мучаюсь, и никак!
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.04.2009, 19:01
Ответы с готовыми решениями:

Определить количество узлов на каждом уровне данного бинарного дерева
Помогите с этой задачей) Определить количество узлов на каждом уровне данного бинарного дерева....

Подсчитать количество листьев дерева не на последнем уровне, имеющем листья.
Добрый день! Не могу разобраться со следующим: нужно подсчитать количество листьев не на последнем...

Рекурсия: подсчитать сумму элементов бинарного дерева
Написать программу, которая создает сбалансированное бинарное дерево. Написать рекурсивную функцию,...

Homelisp: подсчитать количество вершин бинарного дерева, значение которых меньше заданного N
Дано бинарное дерево содержащее целые числа. Подсчитать количество вершин дерева, значение которого...

8
576 / 570 / 65
Регистрация: 29.01.2009
Сообщений: 1,274
11.04.2009, 19:53 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* подсчет количества элементов на уровне 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;
}
1
0 / 0 / 0
Регистрация: 02.12.2008
Сообщений: 23
12.04.2009, 10:47  [ТС] 3
Спасибо огромное!!!!! Вы меня просто спасли!!!
0
576 / 570 / 65
Регистрация: 29.01.2009
Сообщений: 1,274
12.04.2009, 11:43 4
Пожалуйста, конечно хотя надо бы так подкорректировать мой код, иначе при большом числе уровней может некорректно считать.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int nelem(struct tnode *p, int level, int i)
{
    static int cnt = 0;
    
    if(p == NULL)
       return 0;
    else if(i == level)
       return p->elem;
    else {
       cnt += nelem(p->left, level, i+1);
       cnt += nelem(p->right, level, i+1);
    }
    return (i > 0) ? 0 : cnt;
}
Так будут суммироваться все значения поля elem (если это число) на заданном уровне. Но если надо просто посчитать сколько существует узлов на уровне, тогда "return p->elem" замените на "return 1". В качестве i передавать 0.
1
0 / 0 / 0
Регистрация: 02.12.2008
Сообщений: 23
12.04.2009, 12:06  [ТС] 5
Ой, спасибо, еще раз)
А что делает 13 строчка?
0
576 / 570 / 65
Регистрация: 29.01.2009
Сообщений: 1,274
12.04.2009, 12:11 6
Определяет что вернет рекурсия. Если рекурсия на самом начальном уровне, то возвращает количество элементов, если глубже - то 0 (чтобы не произошло лишних суммирований).
0
0 / 0 / 0
Регистрация: 02.12.2008
Сообщений: 23
12.04.2009, 12:17  [ТС] 7
А можно это записать через условный опреатор?
C
1
2
3
4
if(i==0)
return cnt;
else
return 0;
0
576 / 570 / 65
Регистрация: 29.01.2009
Сообщений: 1,274
12.04.2009, 12:18 8
Можно и так
1
0 / 0 / 0
Регистрация: 02.12.2008
Сообщений: 23
12.04.2009, 12:27  [ТС] 9
Спасибо большое за помощь!!!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.04.2009, 12:27

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Подсчёт вершин на N-ом уровне не пустого бинарного дерева
Доброго времени суток! Пожалуйста прошу помочь решить задачку, подскажите хотя бы алгоритм,...

Определить число листьев на каждом уровне бинарного дерева
Помогите! Нужно написать программу Определение число листьев на каждом уровне БИНАРНОГО дерева....

Функция: подсчет количества вершин на N-ом уровне бинарного дерева
Помогите пожалуйста написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного...

Посчитать количество элементов бинарного дерева
Нужно посчитать количество элементов бинарного дерева.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.