LAB / _2017-ЛАБОРАТОРНЫЕ РАБОТЫ 2 КУРС / _5_TREE
.docx
ЛАБОРАТОРНАЯ РАБОТА 5
Древовидные структуры
1.Общие понятия
Дерево по определению - зто граф без циклов. Если ребра дерева имеют направление, то граф называется ориентированным. Набор несвязанных деревьев называется лесом. Деревья являются удобным инструментом как для организации иерархических структур хранения информации, так и для решения целого ряда задач.
В качестве элементов древовидных структур удобно выбирать так называемые сложные записи, т.е такие записи, которые состоят из двух-главной, стоящей на более высоком уровне иерархии, и подчиненной, находящейся на более низком уровне иерархии. Главная запись имеет ссылки на все подчиненные записи. В бинарных деревьях таких ссылок имеется не более двух. Одна и та же запись в дереве может выступать в качестве главной по отношению к записям, находящимся на более нижнем уровне иерархии, и-подчиненной по отношению к записи на более высоком уровне иерархии. Это обстоятельство дает возможность непрерывного просмотра по маршруту(ветви) от самого высокого уровня иерархии до самого низкого.
2.Цель работы
Целью работы является изучение и отработка приемов и навыков использования деревьев в организации алгоритмических структур и структур хранения информации. Машинная реализация этих структур планируется на языке Турбо Паскаль или С++. При упрощенном варианте выполнение работы должно занимать не более 4-х часов времени. При усложненном варианте -6 часов.
3. Варианты заданий на выполнение работы
При выполнении заданий следует задействовать стандартные операции
работы с деревьями, каждая из которых должна быть оформлена в виде отдельной
функции или процедуры. Кроме этих операций должны быть процедуры, позволяющие выполнить конкретное задание. Ниже приведен список заданий на эту работу.
1. Построить бинарное дерево, подсчитать число листьев этого дерева и раз-
работать процедуру модификации элементов.
2. Построить бинарное дерево и разработать процедуру выделения поддерева
в отдельное дерево.
3. Построить бинарное дерево и разработать процедуру включения поддерева
в дерево.
4. Построить бинарное дерево, все элементы которого дополнительно связаны
между собой по горизонтали.
5. Построить два бинарных дерева и объединить их, избегая дублирования
элементов в суммарном дереве.
6. Построить два бинарных дерева, одно из которых, являясь деревом поиска, по структуре идентично другому, и использовать это обстоятельство для ускорения поиска нужного элемента в другом дереве.
7. Построить два бинарных дерева и на их основе построить дерево, полученное в результате операции вычитания.
8. Построить дерево, бинаризовать его и использовать бинаризованное дерево
для поиска нужного элемента в исходном дереве.
9. Построить на основе дерева простейшую базу данных.
10. Из древовидной структуры вывести список студентов, получивших на экзамене одинаковые оценки.
11. Разработать процедуру сортировки последовательности элементов, используя дерево поиска.
12. Используя бинарное дерево, разработать процедуру формирования кодов
Хаффмана.
13. Используя бинарное дерево, разработать процедуру раскодирования кодов
Хаффмана.
14. На основе бинарных дереьев разработать автомат для игры в "крестики-нолики".
15. Составить дерево для грамматического разбора арифметического выражения.
16. Программно реализовать алгоритм пирамидальной сортировки.
17. На основе произвольной последовательности построить дерево поиска и затем сбалансировать его.
18. Разработать алгоритм записи на диск и восстановления в динамической памяти почти полного бинарного дерева.
19. Разработать алгоритм записи на диск и восстановления в динамической памяти произвольного бинарного дерева.
20. Объединить пункт 17 и 18.
21. Объединить пункт 17 и 19.
4. Пояснения к выполнению лабораторной работы
Бинарное дерево, на основе которого построены все вышеперечисленные задания, по сути дела, является специально организованным двухсвязным списком, в котором каждый элемент потенциально может ссылаться на два
других элемента с иерархией на пункт ниже. Это свойство бинарных деревьев, к которым, как известно, можно свести произвольное дерево, широко используется для разработки стандартных процедур для бинарных деревьев. Число этих
процедур существенно больше, чем для ранее рассмотренных структур (см. предыдущие лабораторные работы). Особенностью использования деревьев является то обстоятельство, что как правило решение конкретной задачи не требует полного набора стандартных задач. Поэтому один из элементов выполнения вышепредставленных заданий - это определение круга стандартных операций,
необходимых для решения данной задачи. Второй особенностью этой лабораторной работы является более сильная зависимость от теоретических знаний, без хорошего знания которых практически невозможно выполнить ни одного
задания. Следует также обратить внимание на то. что алгоритмы: построения дерева, поиска нужного элемента, просмотра дерева и др. носят рекурсивный характер и другим образом их построить чрезвычайно трудно. Ниже приведены основные стандартные операции с деревьями:
-построение хорошо сбалансированного дерева;
-построение дерева поиска;
-построение общего бинарного дерева;
-поиск элемента в дереве поиска;
-последовательный просмотр элементов дерева (правый обход,
левый, смешанный);
-включение элемента на нижний уровень иерархии;
-выключение элемента с нижнего уровня иерархии;
-включение элемента в произвольный уровень иерархии;
-выключение элемента из произвольного уровня иерархии;
и т. д.
ПРИЛОЖЕНИЕ 1
Пример программы с использованием дерева
Пусть требуется создать структуру хранения данных о предках персоны по
главной линии. Такая структура хорошо вписывается в полное бинарное дерево.
На нулевом уровне этого дерева находится информация о персоне; на первом
уровне-информация о родителях; на втором уровне-информация о бабушках и де-
душках и т.д. При заданной глубине поиска m число вершин n высчитывается по
по формуле
m+1
n=2 -1 .
Для того , чтобы указанное дерево было деревом поиска, надо соответствую-
щим образом сформировать значения ключей элементов. Для полного бинарного
дерева их можно сформировать автоматически(см. функцию contree). В общем
случае это сделать достаточно сложно.
Далее приведен текст на Турбо Паскале.
program tree;
uses crt;
type
indtype=^per;
key=integer;
per =record {ЛИЧНОСТЬ}
key: byte;
fam : string[9];
nam : string[9];
left: indtype;
right: indtype;
end;
var
ch:char;
n,m,mm,n0:integer;
glub,lev,kod:byte;
tr,root:indtype;
flag:boolean;
{*****************************************************************
Конструирование хорошо сбалансированного бинарного дерева
******************************************************************}
function kontree(n:integer;var i:integer):indtype;
var
x,nl,nr : integer;
newnode: indtype;
begin
if n=0 then
kontree:=nil
else
begin
nl:=n div 2;
nr:=n-1-nl;
new(newnode);
newnode^.fam:=' ';
newnode^.nam:=' ';
{формирование ключа производится в данной задаче автоматически:в результате
для полного бинарного дерева получаем дерево поиска }
x:=nl+1+i;
newnode^.key:=x;
newnode^.left:=kontree(nl,i);
i:=i+1;
newnode^.right:=kontree(nr,i);
kontree:=newnode;
end;
end;
{****************************************************************
Поиск места элемента дерева по ключу: если элемент с заданным
ключом отсутствует, то образуется новый элемент с указателем chtree;
переменная root,передаваемая в функцию-это указатель корня дерева
(вершины с самым высоким уровнем иерархии)
****************************************************************}
function chtree(n:integer;root:indtype):indtype;
var chtr:indtype;
begin
chtr:=root;
chtree:=root;
while(chtr<>nil) and (chtr^.key<>n) do
if chtr^.key<n then
begin
chtr:=chtr^.right;
chtree:=chtr;
end
else
chtr:=chtr^.left;
chtree:=chtr;
if(chtr=nil) and (chtr^.key<>n) then
chtr^.key:=n;
end;
{*********************************************************
ввод данных в запись(элемент дерева) с задан-
ным указателем "d"
*********************************************************}
procedure inptree(var d:indtype);
begin
with d^ do
begin
writeln('Введите фамилию ');
readln(fam);
writeln('Введите имя ');
readln(nam);
end;
writeln;
end;
{*********************************************************
вывод данных из записи(элемента дерева) с задан-
ным указателем "d"
*********************************************************}
procedure outtree(var d:indtype);
begin
with d^ do
begin
write(key:2,' ');
write(fam,' ');
writeln(nam,' ');
end;
writeln;
end;
{***************************************************************************
Просмотр заданного уровня иерархии дерева
***************************************************************************}
procedure seetree(n,glub,lev:integer;root:indtype);
var
i0,i,nn,m :byte;
begin
writeln('Уровень иерархии : ',lev:1);
{формирование ключа первого просматриваемого элемента(переменная "м")}
nn:=glub-lev;
m:=1;
while nn>0 do
begin
nn:=nn-1;
m:=m*2;
end;
i0:=2*m;{формирование шага между просматриваемыми элементами}
while n>=m do {поиск нужного элемента и его просмотр}
begin
tr:=chtree(m,root);
outtree(tr);
m:=m+i0;
end;
end;
{**** программа ******}
BEGIN
clrscr;
{Конструирование дерева}
writeln('Введите глубину поиска родственников: ');
read(glub);
m:=glub+1;
{расчет числа вершин}
mm:=1;
while m>0 do
begin
m:=m-1;
mm:=mm*2;
end;
n:=mm-1;
n0:=0;
root:=kontree(n,n0);
repeat
{просмотр исходного дерева по уровням иерархии}
lev:=0;
while lev<glub+1 do
begin
seetree(n,glub,lev,root);
lev:=lev+1;
end;
writeln('ВВедите ключ элемента, в который вводятся данные ');
readln(kod);
tr:=chtree(kod,root); {поиск элемента с ключом "код"}
inptree(tr); { ввод информации в элемент с ключом "код"}
outtree(tr); { вывод элемента с ключом "код"}
writeln('Для окончания работы нажмите - ESC');
until readkey=#27;
END.
ПРИЛОЖЕНИЕ 2
Пример программы с использованием дерева
на языке С++
В этом приложении на языке С++ приведен текст программы, позволяющий
решить задачу, указанную в Приложении 1.
!!=========================!!
!! древовидные структуры !!
!!=========================!! */
#include <dos.h>
#include <alloc.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <mem.h>
typedef
struct tree{
int key;
char fam[10];
char nam[10];
struct tree *left;
struct tree *right;
};
struct tree *kontree(int n,int *i) ;
struct tree *chtree(int n,struct tree *root);
void inptree(struct tree *d);
void outtree(struct tree *d);
void seetree(int n,int glub,int lev,struct tree *root);
/* {**** программа ******} */
main()
{
char ch;
int n,m,mm,n0,glub,lev,kod;
struct tree *root,*d,*tr;
char flag,syb;
/* {Конструирование дерева} */
printf("Введите глубину поиска родственников:\n ");
scanf(" %d",&glub);
m=glub+1;
/* {расчет числа вершин} */
mm=1;
while (m>0)
{
m=m-1;
mm=mm*2;
}
n=mm-1;
n0=0;
syb='0';
root=kontree(n,&n0);
while((syb!='y')&&(syb!='Y'))
{
/* {просмотр исходного дерева по уровням иерархии} */
lev=0;
while (lev<glub+1)
{
seetree(n,glub,lev,root);
lev=lev+1;
}
printf("ВВедите ключ элемента, в который вводятся данные \n");
scanf("%d",&kod);
tr=chtree(kod,&*root); /*поиск элемента с ключом "код"*/
inptree(&*tr); /* ввод информации в элемент с ключом "код"*/
outtree(&*tr); /* вывод элемента с ключом "код"*/
scanf("%c",&syb);
}
}
/* {*****************************************************************
Конструирование хорошо сбалансированного бинарного дерева
******************************************************************}*/
struct tree *kontree(int n,int *i)
{
int nl,nr ,x,j;
struct tree *newnode;
if (n==0)
/* kontree=NULL;*/
return(NULL);
else
{
nl=n / 2;
nr=n-1-nl;
newnode=(struct tree*)malloc(sizeof(struct tree));
for(j=0;j<11;j++)
{ newnode->fam[j]=0;
newnode->nam[j]=0;
}
/*{формирование ключа производится в данной задаче автоматически:в результате
для полного бинарного дерева получаем дерево поиска }*/
x=nl+1+*i;
newnode->key=x;
newnode->left=kontree(nl,&*i);
*i=*i+1;
newnode->right=kontree(nr,&*i);
return(newnode);
}
}
/* ****************************************************************
Поиск места элемента дерева по ключу: если элемент с заданным
ключом отсутствует, то образуется новый элемент с указателем chtree;
переменная root,передаваемая в функцию-это указатель корня дерева
(везшины с самым высоким уровнем иерархии)
**************************************************************** */
struct tree *chtree(int n,struct tree *root)
{
struct tree *chtr;
chtr=root;
while((chtr!=NULL)&&(chtr->key!=n))
if (chtr->key<n )
chtr=chtr->right;
else
chtr=chtr->left;
return(chtr);
if((chtr==NULL)&&(chtr->key!=n))
chtr->key=n;
}
/* {*********************************************************
ввод данных в запись(элемент дерева) с задан-
ным указателем "d"
*********************************************************} */
void inptree(struct tree *d)
{ gets(d->fam);
printf("Введите фамилию\n ");
gets(d->fam);
printf("Введите имя\n");
gets(d->nam);
printf("\n");
}
/* {*********************************************************
вывод данных из записи(элемента дерева) с задан-
ным указателем "d"
*********************************************************} */
void outtree(struct tree *d)
{
printf("%d %s %s",d->key,d->fam,d->nam);
printf("\n");
}
/*{***************************************************************************
Просмотр заданного уровня иерархии дерева
************************************************************************* */
void seetree(int n,int glub,int lev,struct tree *root)
{
int i0,i,nn,m;
struct tree *tr;
printf("Уровень иерархии :%d \n",lev);
/* {формирование ключа первого просматриваемого элемента(переменная "м")} */
nn=glub-lev;
m=1;
while (nn>0)
{
nn=nn-1;
m=m*2;
}
i0=2*m; /*{формирование шага между просматриваемыми элементами} */
while (n>=m) /* {поиск нужного элемента и его просмотр}*/
{
tr=chtree(m,root);
outtree(tr);
m=m+i0;
}
}