1 Задание 2 Программу на языке программирования C++ 3 Описание использованных алгоритмов

1.Задание.
2.Программу на языке программирования C++.
3.Описание использованных алгоритмов.
4.Скриншоты с результатами выполнения программы.
5.Ответы на контрольные вопросы.
6.Выводы о проделанной работе.

Задание.
Отсортировать массив А путем включения его элементов в дерево и скопировать отсортированные данные обратно в А.

Программа на языке С++.
# include <iostream>
# include <conio.h>

using namespace std;

//Наша структура
struct node
{
int info; //Информационное поле
node *l, *r;//Левая и Правая часть дерева
};
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
if ((*t)==NULL) //Если дерева не существует
{
(*t)=new node; //Выделяем память
(*t)->info=a; //Кладем в выделенное место аргумент a
(*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
return; //Заложили семечко, выходим
}
//Дерево есть
if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
else push(a,&(*t)->l); //Иначе кладем его влево
}
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int &u,int *A)
{
if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
else //Иначе
{
print(t->l,u,A);//С помощью рекурсивного посещаем левое поддерево
A[u]=t->info;
u++;
cout<<t->info<<endl; //И показываем элемент
}
print(t->r,u,A); //С помощью рекурсии посещаем правое поддерево
}

void main ()
{
setlocale(LC_ALL,»RUSSIAN»);

int n; //Количество элементов
cout<<«введите количество элементов «;
cin>>n; //Вводим количество элементов
int *a=new int[n];//Динамический массив А
for (int i=0;i<n;++i)
{
cout<<«ведите число «;
cin>>a[i]; //Считываем элемент за элементом

push(a[i],&tree); //И каждый кладем в дерево
}
cout<<«nВаше деревоn»;
int k=0;
print(tree,k,a);
cout<<«nОтсортированный массив:n»;
for(int i=0;i<n;i++)cout<<a[i]<<» «;
getch();
}

Описание использованных алгоритмов.
Структура каждой вершины дерева:
struct node
{
int info; //Информационное поле
node *l, *r;//Левая и Правая часть дерева
};
Добавление вершины в дерево:
void push(int a,node **t)
{
if ((*t)==NULL) //Если дерева не существует
{
(*t)=new node; //Выделяем память
(*t)->info=a; //Кладем в выделенное место аргумент a
(*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
return;
}
Обход дерева в прямом порядке:
void print (node *t,int &u,int *A)
{
if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
else //Иначе
{
print(t->l,u,A);//С помощью рекурсивного посещаем левое поддерево
A[u]=t->info;
u++;
cout<<t->info<<endl; //И показываем элемент
}
print(t->r,u,A); //С помощью рекурсии посещаем правое поддерево
}
Для того чтобы обратно скопировать отсортированные элементы в массив, будем передавать его в качестве аргумента, так же счетчик номера элемента.
Выводить на экран дерево и тут же записывать элемент в массив, повышая счетчик.

Скриншоты работы программы.

Ответы на контрольные вопросы.
Что такое дерево, двоичное дерево, поддерево?
Дерево – это структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов ( рис. 31.1). Каждый элемент дерева называется вершиной (узлом) дерева. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви.
Каждое дерево обладает следующими свойствами:
существует узел, в который не входит ни одной дуги (корень);
в каждую вершину, кроме корня, входит одна дуга.
Деревья особенно часто используют на практике при изображении различных иерархий. Например, популярны генеалогические деревья.

Рис. 31.1. Дерево
Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Для каждого предка может быть выделено несколько. Уровень потомка на единицу превосходит уровень его предка. Корень дерева не имеет предка, а листья дерева не имеют потомков.
Высота (глубина) дерева определяется количеством уровней, на которых располагаются его вершины. Высота пустого дерева равна нулю, высота дерева из одного корня – единице. На первом уровне дерева может быть только одна вершина – корень дерева, на втором – потомки корня дерева, на третьем – потомки потомков корня дерева и т.д.
Поддерево – часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева.
Степенью вершины в дереве называется количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень нуль. По величине степени дерева различают два типа деревьев:
двоичные – степень дерева не более двух;
сильноветвящиеся – степень дерева произвольная.
Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждой вершины, упорядочены по определенному критерию.
Деревья являются рекурсивными структурами, так как каждое поддерево также является деревом. Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:
либо пустой структурой;
либо элементом, с которым связано конечное число поддеревьев.
Действия с рекурсивными структурами удобнее всего описываются с помощью рекурсивных алгоритмов.
Списочное представление деревьев основано на элементах, соответствующих вершинам дерева. Каждый элемент имеет поле данных и два поля указателей: указатель на начало списка потомков вершины и указатель на следующий элемент в списке потомков текущего уровня. При таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева.
Для того, чтобы выполнить определенную операцию над всеми вершинами дерева необходимо все его вершины просмотреть. Такая задача называется обходом дерева.
Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.
При обходе все вершины дерева должны посещаться в определенном порядке. Существует несколько способов обхода всех вершин дерева. Выделим три наиболее часто используемых способа обхода дерева ( рис. 31.2):
прямой;
симметричный;
обратный.

Рис. 31.2. Обходы деревьев
Существует большое многообразие древовидных структур данных. Выделим самые распространенные из них: бинарные (двоичные) деревья, красно-черные деревья, В-деревья, АВЛ-деревья, матричные деревья, смешанные деревья и т.д.
Бинарные деревья
Бинарные деревья являются деревьями со степенью не более двух.
Бинарное (двоичное) дерево – это динамическая структура данных, представляющее собой дерево, в котором каждая вершина имеет не более двух потомков ( рис. 31.3). Таким образом, бинарное дерево состоит из элементов, каждый из которых содержит информационное поле и не более двух ссылок на различные бинарные поддеревья. На каждый элемент дерева имеется ровно одна ссылка.

Рис. 31.3. Бинарное дерево и его организация
Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:
информационное поле (ключ вершины);
служебное поле (их может быть несколько или ни одного);
указатель на левое поддерево;
указатель на правое поддерево.
По степени вершин бинарные деревья делятся на ( рис. 31.4):

Рис. 31.4.
строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);
нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).
В общем случае у бинарного дерева на k -м уровне может быть до 2k-1 вершин. Бинарное дерево называется полным, если оно содержит только полностью заполненные уровни. В противном случае оно является неполным.
Дерево называется сбалансированным, если длины всех путей от корня к внешним вершинам равны между собой. Деревоназывается почти сбалансированным, если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу.
Бинарное дерево может представлять собой пустое множество. Бинарное дерево может выродиться в список ( рис. 31.5).

Рис. 31.5. Список как частный случай бинарного дерева
Структура дерева отражается во входном потоке данных так: каждой вводимой пустой связи соответствует условный символ, например, ‘*’ (звездочка). При этом сначала описываются левые потомки, затем, правые. Для структуры бинарного дерева, представленного на следующем рисунке 6, входной поток имеет вид: ABD*G***CE**FH**J**.

Рис. 31.6. Адресация в бинарном дереве
Бинарные деревья могут применяться для поиска данных в специально построенных деревьях (базы данных), сортировки данных, вычислений арифметических выражений, кодирования (метод Хаффмана) и т.д.

Приведите два способа хранения деревьев в памяти ЭВМ, укажите их недостатки и достоинства.
Обозначим через n(р) объем памяти, занимаемой представлением бинарного дерева, где р — число узлов. Наиболее часто используются следующие представления бинарных деревьев.
1.              Списочные структуры: каждый узел представляется записью типа N, содержащей два поля (l и r) с указателями на левый и правый узлы и еще одно поле i для хранения указателя на информацию об узле. Дерево представляется .указателем на корень. Тип N обычно определяется следующим образом: 
 N = record i : info; l,r : N  end record. Для этого представления n(р) = Зр.
 
ЗАМЕЧАНИЕ Поскольку в бинарном дереве, как и в любом другом, q = р — 1, то из 2р указателей, отводимых для хранения дуг, р + 1 всегда хранит значение nil, то есть половина связей не используется.
 
2.      Упакованные массивы: все узлы располагаются в массиве, так что все узлы поддерева данного узла располагаются вслед за этим узлом. Вместе с каждым узлом хранится индекс узла, который является последним узлом поддерева данного узла. Дерево Т обычно определяется следующим образом: Т : array [l..p] of record i : info, k : l..p end record. Для этого представления n(р) = 2р.
3.      Польская запись: аналогично, но вместо связей фиксируется «размеченная степень» каждого узла (например, 0 означает, что это лист, 1 — есть левая связь, но нет правой, 2 — есть правая связь, но нет левой, 3 — есть обе связи). Дерево Т определяется следующим образом: Т : array [l..p] of record i : info, d : 0..3 end record. Для этого представления n(р) — 2р. Если степень узла известна из информации, хранящейся в самом узле, то можно не хранить и степень. Такой способ представления деревьев называется польской записью и обычно используется для представления выражений. В этом случае представление дерева оказывается наиболее компактным: объем памяти n(р) = р.

Нарисуйте бинарное дерево, в котором вы хранили бы список R S T U V W X Y и Z для последующего поиска.
120015324485R

R

46443904391025Z

Z

23964902143125V

V

29584652705100W

W

35204403267075X

X

40824153829050Y

Y

12439651085850T

T

18059401647825U

U

681990523875S

S

Нарисуйте схему, показывающую, как дерево, приведенное ниже, хранится в памяти с использованием указателей на левых и правых потомков. Затем нарисуйте схему последовательного хранения элементов дерева с использованием альтернативной системы хранения.

37966652291715NULL
NULL
32727902291715NULL
NULL
11868152310765NULL
NULL
3200404044315NULL
NULL
-1943104044315NULL
NULL
32004024726902825114103441511868151034415-1943103368040W
W
32727901615440Z
Z
6724651615440X
X
2053590186690Y
Y

Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

14 + три =

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Adblock detector