VPF::рекурсия в деревьях - Форум программистов

persalena

Дата 10.4.2009, 17:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 1.12.2008

Репутация: нет
Всего: нет

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

.

И еще: дерево скорее всего бинарное.. т.к как обычное дерево списком представить, я вообще не знаю... И ввод дерева у меня расчитан на бинарное...

вот что я написала... n вообщем то говоря с клавиатуры вводится, ноя пока взяла его за константу. программа впринципе работает, если k объявлять глобальной переменной, а мне бы ее как нибудь в локальную переделать..

Код

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
int p=0;
int n=3;
int i=0;
FILE *fp;
struct btree
  {
  char elem;
  btree *left;
  btree *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;
    }

void obhod(btree*d, int *k)
{
if(d!=NULL&&i<=n)
{
i++;
if(i==n)
*k++;
obhod(d->left, k);
obhod(d->right,k);}
else i--;
}


void main()
{int k;
k=0;
if ((fp=fopen("1.txt","r"))==NULL)
{
perror("error\n");
exit(0);
}
btree*d;
d=build_tree();
obhod(d,&k);
}

Это сообщение отредактировал(а) persalena - 10.4.2009, 17:12

bsa

Дата 10.4.2009, 18:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

persalena, отформатируй код пожалуйста (открывающая фигурная скобка на строке оператора или под ним без отступа относительно него, закрывающая - на отдельной строке без отступа от открывающей (или от оператора, к которому относится открывающая), все что между - с отступом):

Код

void obhod(btree*d, int *k)
{
   if (d!=NULL && i<=n) {
      ++i;  //++i работает быстрее i++, в общем случае
      if (i==n)
         ++*k; //*k++ работает несколько иначе, чем ты думаешь
      obhod(d->left, k);
      obhod(d->right, k);
   } else
      --i;
}

Согласись, что так намного наглядней.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Anikmar

Дата 10.4.2009, 18:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

Цитата(bsa @ 10.4.2009, 18:18

)

Согласись, что так намного наглядней.

У меня был знакомый, который открывающие/закрывающие скобки выносил вправо - к границе экрана. Утверждал, что ему так понятнее. Я его код вообще не мог воспринимать smile

bsa

Дата 12.4.2009, 22:38 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(Anikmar @ 10.4.2009, 18:22)

Цитата(bsa @ 10.4.2009, 18:18

)

Согласись, что так намного наглядней.

Извращенцев в сад!

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

xvr

Дата 13.4.2009, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Функция obhod спроектированна несколько кривовато. Лучше ей передать корень дерева и на сколько спустится, а вернуть количество вершин.

Код


int obhod(btree* root, int levels)
{
 if (!root) return 0;
 if (!levels) return 1;
 return obhod(root->left,levels-1)+obhod(root->right,levels-1);
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »