Определение одинаковых элементов в заданном бинарном дереве (Лабораторная работа № 3)

Министерство образования и науки

Российской Федерации

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

Кафедра ПМт

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

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

Студент: Рак А.В.

Группа: ПМ-85

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

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

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

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

Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента.

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

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

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

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

  2)  Результат: поиск одинаковых элементов в бинарном дереве.

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

Складываем  левое  поддерево в стек, и сравниваем корень дерева с элементами из стека. Если нашли одинаковые элементы выдаем сообщение о том, что есть одинаковые элементы, если не нашли, то пишем «нет». Повторяем эти действие с правым поддеревом.

3. Структуры  данных

Внешнее представление:

                    Входные данные: в файле  "wert.txt",  последовательностью  символов представлено дерево

                    Выходные данные:  если есть одинаковые элементы, то выводим  "odinakovie est'” , если одинаковых элементов нет то выводим  "net".

Внутреннее представление:

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

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

struct btree

{

 char elem;

 btree *left, *right;

};

                    Выходные данные:

Если есть одинаковые элементы в заданном  дереве то выводим "odinakovie est'”, если элементов нет то печатаем "net".

4. Алгоритмы

Главный модуль:

 

void  poisk:

void sravnenie:

sravnenie (d->left,x,F,h); sravnenie (d->right,x,F,h);

btree *build_tree.

 

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

#include <stdio.h>

#include <conio.h>

struct btree

{

 char elem;

 btree *left, *right;

};

btree *build_tree(FILE *fp)

{

 char a;

 btree *d;

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

      switch (a)

      {

       case '(':{d=new btree;

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

                 d->elem=a;

                 d->left=build_tree(fp);

                 d->right=build_tree(fp);

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

                 return d;}

       case '0':return NULL;

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

                 return d;

      }

}

void sravnenie (btree *d, char x,int *F,btree*h)

{

 if (d!=NULL)

 {

  if (x==d->elem && d!=h) *F=1;

  sravnenie (d->left,x,F,h);

  sravnenie (d->right,x,F,h);

 }

}

void poisk (btree *d,int*F,btree *h)

{

 if (d!=NULL)

 {

  sravnenie (h,d->elem,F,d);

  poisk (d->left,F,h);

  poisk (d->right,F,h);

 }

}

void main ()

{

 clrscr();

 FILE *fp;

 btree *d;

 d=NULL;

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

 d=build_tree(fp);

 int n=0;

 poisk (d,&n,d);

 if (n==1)printf("odinakovie est'");

 else printf ("net");

 getch ();

}

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

№	Дано	Результаты
1	(a,(b,(d,0,0),0),(c,(e,0,(g,0,0)),(f,(h,0,0),(i,0,0))))	нет
2	(a,(b,(d,0,0),0),(c,(e,0,(g,0,0)),(f,(с,0,0),(а,0,0))))	есть
3	(a,0,0)	нет

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

      Программа выдала желаемый результат на всех тестах.