Министерство образования и науки, молодежи и спорта Украины
Вузол = record
лівий, правый: зв ’язок;
дані: тип_даних;
end;
Перегляд двійкового дерева може проводитись рекурсивно - для кожного
вузла можна використовувати три дії. Для позначення операції, яку
потрібно виконувати над кожним вузлом дерева, будемо використовувати
термін "дослідити". Це буде виглядати таким чином:
1. дослідити вузол;
2. переглянути ліве піддерево;
3. переглянути праве піддерево.
Приклад: написати рекурсивну процедуру, яка виконує перегляд двійкового дерева.
Procedure перегляд(Vаг дерево :зв 'язок);
Begin
If дерево <> NIL then
Begin
New(дерево);
Дослідити (дерево);
Перегляд(дерево^. ліве);
Перегляд(дерево^. праве);
End;
End.
Така процедура здійснює прямий перегляд дерева. Інші види перегляду можуть бути одержні шляхом перестановки трьох операторів, що входять в внутрішній складний оператор.
Приклад: розглянемо процедуру, яка додає до двійкового дерева пошуку один вузол, зберігаючи порядок елементів дерева.
Procedure вставити(Var дерево:зв’язок, нові дані);
Begin
If дерево <> NIL men
Begin
New (дерево);
With дерево^ do
Begin
Лiвe: =NIL;
Праве: =NIL;
Дані: = нові_дані;
End;
End
Else with дерево^ do
If нові_дані< дані then
Вставити(ліве, нові_дaні)
Else
If нові_дaнi>дaні then
Bcтaвuтu(npaвe, нoвi_дaні);
End.
Приклад: написати функцію, що видає в результаті роботи вказівник на
вузол дерева, який містить необхідні дані або порожній вказівник, якщо
потрібна інформація в дереві відсутня.
Function знайти (Var дерево;зв'язок, ключ:тип_даних):зв’язок;
Begin
If дерево: =Nil then
Знайти: =Nil
Else
With дерево^ do
If ключ<дані then
Знайти: = знайти (ліве, ключ);
Else
If ключ>дані then
Знайти:=знайти(праве, ключ)
Else
Знайти: =дерево;
End.
Елементи двійкового дерева пошуку можуть бути переглянуті в правилъній послідовності за допомогою зворотнъого перегляду. Єдиною операцією, що потребує значних зусилъ являється операція вилучення вузла, що не являється листом дерева.
Двійкове дерево пошуку представляє собою більш зручну структуру для
зберігання та пошуку даних, ніж масив.
При роботі з такими деревами потрібно попередньо впевнитись, що нові
дані не надходять в порядку зростання чи спадання, так як в цьому випадку дерево вироджується у лінійний список.
ДЕРЕВА ЗАГАЛЬНОГО ВИГЛЯДУ.
Розглянемо проблему представлення дерев, вузли яких можуть містити вказівник більш ніж на два піддерева. Якщо максимальне число піддерев обмежено деяким достатньо малим значенням, то практично є можливістъ для вказання на піддерева, користуючись масивом вказівників. В цьому paзі описані структури даних будуть виглядати наступним чином:
Const макс_число_вузлів=6;
Туре зв'язок=^ вузол;
Вузол=record
Підвузол:array[1.. макс_чис_вузлів]оf зв'язок;
Дані: тип_даних;
End;
Тут зарані встановлено значення максимального числа вузлів (ми вносимо в програму доволі серйозні обмеження). Якщо зробити це значення дуже малим, то виникне ситуація, коли дерево представити неможливо, якщо ж значення максимального числа піддерев дуже збільшити, то зросте об'єм пам'яті, що втрачається iз-зa присутності невикористаних зсилок. Можна запропонувати альтернативний розв'язок, який полягає в тому, що кожен вузол дерева повинен мати зсилку на зв'язний список його піддерев.
При такому представленні кожен вузол буде містити тільки дві зсилки: 1. зсилка на найближчий з вузлів відростків даного вузла;
2. на один iз кількох вузлів того ж рівня, що i даний.
На даному малюнку зсилки на піддерева-відростки показані вертикальними лініями, а горизонтальними - зсилки на піддерева, що
починаються від вузлів, які мають спільний попередній вузол з даними.
Так ми перетворили наше дерево в двійкове.
Двійкове дерево можна застосовувати для представления алгебраїчних виразів.
Кожен вузол дерева буде містити операції: +,-,*, /, а також зсилки на два підвирази
Виконав ст.гр. ПЗ-99-1
Матненко А
Програма до рубіжного контролю
Завдання: написати програму, яка б виводила кількість вузлів дерева, починаючи з N-гo рівня
uses crt;
type
derevo=^derev; derev=record
d:array [1..2] of integer;
l,r:derevo;
end;
var
al:derevo;
x,i,n,kilk,level,yl,yr:integer; xx,yl,y2,y3,y4,y5,y6,y7:integer;
procedure print(a:derevo;lev:integer);{npoцедypa переглядає дерево i виводить його у вигляді піраміди (дерева)}
begin
if a<>nil then begin
if a^.l<>nil then print(a^.l,lev);
{write(‘piвень’,a^.d[2],’:’);}
if a^.d[2]>=lev then inc(kilk); { якщо рівень вузла більше/дорівнює заданному, кількість вузлів збільшується}
if a^.d[2]=0 then begin gotoxy(30,3);inc(xx);end; {якщо вузол нульового piвня - виводиться у перщому рядку}
if a^.d[2]=l then begin gotoxy(yl,4);yl:=yl-20;end; {якщо вузол першого рівня - виводиться у другому рядку}
if a^.d[2]=2 then begin gotoxy(y2,5);y2:=y2-10;end;{ якщо вузол другого рівня - виводиться у третьому рядку}
if a^.d[2]=3 then begin gotoxy(y3,6);y3:=y3-5;end; {якщо вузол третього piвня - виводиться у четвертому рядку}
if a^.d[2]=4 then begin gotoxy(y4,7);y4:=y4-4;end; {якщо вузол четвертого piвня - виводиться у п'ятому рядку}
if a^.d[2]=5 then begin gotoxy(y5,8);y5:=y5-5;end; {якщо вузол п'ятого piвня - виводиться у шостому рядку}
if a^.d[2]=6 then begin gotoxy(y6,6);y6:=y6-5;end; {якщо вузол шостого piвня - виводиться у сьомому рядку}
if a^.d[2]=7 then begin gotoxy(y7,6);y7:=y7-4;end; {якщо вузол сьомого рівня - виводиться у восьмому рядку}
write(a^.d[l]:3);
if a^.r<>nil then print(a^.r,lev);
end;end;
procedure dobavl(var a:derevo;y:integer); {процедура додає елемент у дерево}
var k,kk: integer;
begin
write('Введите число ');
readln(k);{ вводиться елемент , який треба додати}
if a=nil then
begin new(a);a^.l:=nil;a^.r:=nil;a^.d[l]:=k;a^.d[2]:=y; end;{cтвopeння нульового вузла дерева}
write('Є ліва гілка 1-да 2-Нет ');{чи буде ліва гілка}
read(kk);
if kk=l then begin inc(yl);dobavl(a^.l,yl);end;{додав елемента у ліву гілку дерева}
write('Є права гілка 1-да 2-Нет ');{чи буде права гілка}
read(kk);
if kk=l then begin inc(yr);dobavl(a^.r,yr);end;{додав елемента у праву гілку дерева}
end;
begin
al:=nil;
clrscr;
write('введіть рівень, починаючи з якого буде вестися підрахунок');
read (level); { вводиться piвень, починаючи з якого буде вестися підрахунок }
writeln('Введіть елементи дерева: ');
dobavl(a1,0); {вводяться елементи дерева}
clrscr;
у1:=40;у2:=45;уЗ:=47;
у4:=50;у5:=53;у7:=64;
у6:=59;
writeln('Елементи дерева А1: ');
print(al, level); {виводиться дерево}
gotoxy(l,20);
writeln('кількість вузлів починаючи з рівня ',level,' = ',kilk);{ виводиться кількість вузлів}
end.
Інструкція користувача.
Система програмування Турбо Паскалю, розроблена американською корпорацією Воrland, що залишається одною із самих популярних систем програмування в світі. Цьому сприяють, з одного боку — труд і талант співробітників Воrland на чолі з ідеологом і твірцем Турбо Паскаля Андерсоном Хейлсбергом, який приклав чимало зусиль до її вдосконалювання. Придуманий швейцарським вченим Нікласом Віртом як засіб для навчання студентів програмуванню, мова Паскаль стараннями А. Хейлсберга перетворилася в потужну сучасну професійну систему програмування, якій по плечу любі задачі — від створення простих програм, призначених для розв'язування нескладних обчислювальних задач, до розробки складних систем управління базами даних. Мій курсовий проект призначений для студентів першого курсу кафедри “Програмного забезпечення “, які мають .мету оволодіти азами програмування на мові Паскаль та спробувати свої сили в розв'язуванні відносно нескладних задач на практиці.
ВИКОРИСТАНА ЛІТЕРАТУРА.
Васильєв П.П. Турбо Паскаль — мой друг.М.:Компьютер, ЮНИТИ,1995.-96с.
Зуев Е.А. Язык программирование Тиrbоо Раsсаl 6.0. —М.:Унитех, 1992.-198с.
Фаронов В.В. Программирование на персональном компьютере ЭВМ в
среде Турбо Паскаль. - М.:Изд-во НГТУ, 1990 - 580с.
Федоров А. Особенности программирования на Воrland Раsсаl. Киев:
Диалектика, 1994. -144с.
Фаронов В.В. Турбо Паскаль 7.0. Начальний курс. Учебное пособие. -М.: "Нолидж",1999.-616.,ил.
«НАЦИОНАЛЬНЫЙ ГОРНЫЙ УНИВЕРСИТЕТ»
Кафедра АОТ
Лекция №3
доц. Алексеенко С.А.
