Подсчет чисел вершин на k-ом уровне в заданном непустом бинарном дереве (Лабораторная работа № 3)

Министерство образования и науки Российской Федерации

Новосибирский государственный технический университет

Кафедра ПМт

Лабораторная  работа №3

по дисциплине

«Структуры данных и алгоритмы»

Факультет: ПМИ

Группа: ПМ-85

Студент: Трифонова А.С.

Преподаватель: Еланцева И.Л.

Новосибирск-2009

1. Условие задачи

В заданном непустом бинарном дереве подсчитать число вершин на k-ом уровне, считая корень вершиной нулевого уровня

2. Анализ задачи

1) Дано: d-дерево; дерево := (значение, левое дерево, правое дерево), kÎN

               Левое  дерево := дерево|пусто

               Правое  дерево := дерево|пусто       значениеÎ{символ}

  2)  Результат: hÎN

  3) Способ решения:

     создать_очередь(st1)

     создать_очередь(st2)

    в _очередь (st2,a)

при k= заданный  уровень

  повторять

        st1=st2;

        создать очередь(st2)

           повторять

              p=из_очереди(st1,a);

              если (левое дерево!=NULL)  в_очередь(st2,левое дерево)

              если (правое дерево!=NULL)  в_очередь(st2,правое дерево)

           пока(!пуста очередь (st1))

   n=n+1

   пока   n!=k

              !пуста очередь (st2)

В задаче можно выделить  подзадачу ввода бинарного дерева

3.Структура основных входных и выходных данных

Внешнее представление входных данных

в файле «tree.txt» последовательностью  символов представлено дерево

Внутреннее представление входных данных

бинарное динамическое дерево представлено нелинейным иерархическим списком

Элемент дерева представлен структурой:

struct btree

{ char elem; btree *left,*right};

Внешнее представление выходных данных

выходные данные представлены в файле   «rezz.txt» целым числом h

Внутренне представление выходных данных

float h
4. Алгоритм решения задачи

5.Текст программы

TRIF2

struct btree

{ char elem;

 btree *left,*right;};

struct dline

{ btree *elem;

  dline *next,*pred;};

void add_elem(dline*b,btree *ss)

{ dline *x;

 b=b->pred;

  x=new dline;

  x->elem=ss;

  x->pred=b;

  x->next=b->next;

  b->next->pred=x;

  b->next=x;

}

int pust(dline *b)

{if (b==b->next) return 1;

  return 0;}

int outline (dline *b,btree **ss)

{dline *r;

r=b->next; *ss=r->elem;

 b->next=r->next;

 r->next->pred=b;

 delete r;return 1;

 }

void New_line(dline**b)

{(*b)=new dline;

(*b)->next=(*b);

(*b)->pred=(*b);

}

void Print_line (dline*b)

{  dline*k;

FILE*fp;

k=b;

fp=fopen("rez1.txt","a");

   do

   {

   fprintf(fp,"%c",b->next->elem);

   b=b->next;

   }

   while (b->next!=k);

fclose(fp);

}

главный модуль

#include <stdio.h>

#include "trif2.cpp"

FILE *fp;

 btree *build_tree()

{ char s;

 btree *d;

   fscanf (fp,"%c",&s);

   switch(s)

  {case '(':{ d=new btree;

              fscanf (fp,"%c",&s); d->elem=s;

              d->left=build_tree();

              d->right=build_tree();  fscanf (fp,"%c",&s);

              return d;}

  case '0': return NULL;

  case ',': d=build_tree(); return d;

  }

}

void main ()

{ FILE *lk;

int k,p,h,n=0;h=0;

dline *st1,*st2;

fp=fopen("tree.txt","r");

lk=fopen("rezz.txt","w");

btree *a=build_tree();

fscanf(fp,"%d",&k);

New_line(&st1);

New_line(&st2);

 add_elem(st2,a);

while((n!=k)&&(pust(st2)!=1))

{ st1=st2; New_line(&st2);

 while (pust(st1)==0)

  {p=outline (st1,&a);

  if (a->left!=NULL) add_elem(st2,a->left);

  if (a->right!=NULL) add_elem(st2,a->right);

  }

  n++;

}

if (k==n ) {while (pust(st2)==0)

           {p=outline(st2,&a);

            h++;

            }

             fprintf(lk,"%d\n",h);

            }

else fprintf(lk,"takogo urovnja net\n");

fclose(lk);

fclose(fp);

}

6.Набор тестов

№	Дано		Результат	Примечания
	дерево	номер уровня
1	(a,(b,(d,0,0),0),(c,(e,0,(g,0,0)),(f,(h,0,0),(i,0,0))))	0	1	на 0-ом уровне всегда одна вершина - корень дерева.
2	(a,(b,(d,0,0),0),(c,(e,0,(g,0,0)),(f,(h,0,0),(i,0,0))))	2	3	общий случай
3	(a,(b,(d,0,0),0),(c,(e,0,(g,0,0)),(f,(h,0,0),(i,0,0))))	6	takogo urovnja net	k>n, такого уровня в данном дереве нет

7.Результаты работы программы

На всех тестах программа выдала желаемый результат, значит, работает корректно.