ВСТУП

З розвитком інформаційних технологій (ІТ), стає все більший попит на ринку праці на професію програміст. На цю спеціальність навчають як в коледжах, так і у вищих навчальних закладах. Ця спеціальність пов'язана з автоматизацію різних галузей за допомогою програмного забезпечення(ПЗ). А в основі будь якого ПЗ, стоїть алгоритм, послідовність дій яка приводить до певного результату.

Предмет «Алгоритми і структури даних» розпочинають вивчати на перших курсах у коледжі та в університеті, і саме цей предмет відіграє важливу роль в подальшому розвитку студента в цій галузі. Але цей предмет для більшості є в значній мірі незрозумілим по різним причинам, однією з таких причин є відсутність візуального прикладу який би моделював той матеріал лекції, і ті приклади що були наведені на дошці.

В основному саме для полегшення сприйняття однієї із теми предмету «Бінарні дерева та методи їх підходу» призначений програмний продукт розроблений у даній дипломній роботі.

За допомогою нього на мою думку студенти зможуть краще сприймати матеріал лекції, переглянувши візуальний приклад який моделює матеріал із лекції про побудову і методи обходу бінарних дерев.

1. ПОСТАНОВКА ЗАДАЧІ

Потрібно створити програмний додаток за допомогою якого можна створювати бінарне дерево та виконувати обхід по дереві за вибраним методом.

Програмний додаток повинен відповідати вказаним критеріям:

- створювати повне бінарне дерево вказаної кількості рівнів;

- візуально відображати метод обходу бінарного дерева;

- надавати довідку користувачеві про створення та методи обходу дерева;

- мати зручний, графічний інтерфейс;

- працювати під управлінням ОС Windows XP/7.

Проаналізувавши ринок програмного забезпечення, ми не знайшли програми яка б відповідала поставленим критеріям. Так як більшість програм мають командний інтерфейс і не володіють хорошою візуальністю при створенні бінарного дерева, та моделюванні методу його обходу.

Тому виникла потреба у розроблені такого програмного додатку який буде відповідати вказаним критеріям.

2. АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ

Після отримання критерій щодо створюваного програмного продукту приступили до аналізу предметної області.

Дерева

У повсякденному житті ми дуже часто зустрічаємо приклади дерев, і вже напевно знайомі з цією концепцією.

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

Другий приклад - це структура великої організації; використання деревоподібної структури для представлення її «ієрархічної структури» нині широко використовується в багатьох комп'ютерних завданнях.

Третій приклад - це граматичне дерево; спочатку воно служило для граматичного аналізу комп'ютерних програм, а нині широко використовується і для граматичного аналізу літературної мови.

Бінарні дерева

Найпростіші з дерев вважаються бінарні дерева.

Бінарне дерево - це кінцева множина елементів, яка або порожня, або містить один елемент, званий коренем дерева, а інші елементи множини діляться на дві непересічні підмножини, кожна з яких сама є бінарним деревом. Ці підмножини називаються лівим і правим піддеревом вихідного дерева.

Кожен елемент бінарного дерева називається вузлом дерева.

На рис. 2.1 зображений загальноприйнятий спосіб зображення бінарного дерева.

Рисунок 2.1 - Бінарне дерево

Це дерево складається з семи вузлів, А-корінь дерева. Його ліве піддерево має корінь В, а праве - корінь С. Це зображується двома гілками, що виходять із А: лівим - до В і правим - до С. Відсутність гілки позначає пусте піддерево - такий вузол називають листом.

Бінарні дерева з корінням D, E, F і G мають порожні ліві і праві піддерева і являються листами дерева.

Властивість 1. Строго бінарне дерево з n листами завжди містить 2n-1 вузлів.

Рівень вузла в бінарному дереві може бути визначений таким чином. Корінь дерева має рівень 0, і рівень будь-якого іншого вузла дерева має рівень на 1 більше рівня свого батька.

Наприклад, в бінарному дереві на рис. 1 вузол B - вузол рівня 1, а вузол D - рівня 2.

Глибина бінарного дерева - це максимальний рівень листа дерева, що дорівнює довжині найдовшого шляху від кореня до листа дерева.

Стало бути, глибина дерева на рис. 2.2 дорівнює 3.

Повне бінарне дерево рівня N - це дерево, в якому кожен вузол рівня N є листом і кожен вузол рівня менше N-1 має непусті ліве і праве піддерево (рис. 2.2).

Рисунок 2.2 - Повне бінарне дерево

Структура бінарного дерева при реалізації

Структура бінарного дерева побудована з вузлів.

Вузол дерева містить поле даних і два поля з покажчиками.

Поля покажчиків називаються лівим покажчиком і правим покажчиком, оскільки вони вказують на ліве і праве піддерево, відповідно. Значення nil є ознакою порожнього дерева.

Тоді бінарне дерево можна буде представити в наступному вигляді рис 2.3.

Размещено на http://www.allbest.ru/

Рисунок 2.3 - Структура бінарного дерева

Тоді дерево що зображено на рис 2.1. Можна зобразити в наступному вигляді рис. 2.4.

Размещено на http://www.allbest.ru/

Рисунок 2.4 - Структура бінарного дерева у вигляді реалізації

Методи обходу бінарних дерев

Над бінарним деревом є операція - його проходження, тобто потрібно обійти все дерево, зазначивши кожен вузол один раз.

Існує 3 основних методи обходу бінарного дерева:

1. в прямому порядку;

2. в симетричному порядку;

3. у зворотному порядку.

Методи обходу дерева детально описані в розділі Опис алгоритму.

3. ОПИС АЛГОРИТМУ

Як було сказано вище, існує 3 основні методи обходу бінарного дерева:

- в прямому порядку;

- в симетричному порядку;

- у зворотному порядку.

Прямий метод

Алгоритм обходу бінарного дерева у прямому порядку має наступний вигляд:

1. Потрапити в корінь;

2. Пройти в прямому порядку ліве піддерево;

3. Пройти в прямому порядку праве піддерево.

На рис. 3.1 змодельований прямий метод обходу дерева.

Результат обходу: 1-2-4-5-3-6-7

Рисунок 3.1 - Прямий метод обходу

Зворотній метод

Алгоритм обходу бінарного дерева у зворотному порядку наступний:

1. Пройти в зворотному порядку ліве піддерево;

2. Пройти в зворотному порядку праве піддерево;

3. Потрапити в корінь.

На рис. 3.2 змодельований зворотній метод обходу дерева.

Результат обходу: 4-5-2-6-7-3-1

Рисунок 3.2 - Зворотній метод обходу

Симетричний метод

Алгоритм обходу бінарного дерева у симетричному порядку наступний:

1. Пройти в симетричному порядку ліве піддерево;

2. Потрапити в корінь;

3. Пройти в симетричному порядку праве піддерево.

На рис. 3.3 змодельований симетричний метод обходу дерева.

Результат обходу: 4-2-5-1-6-3-7

Рисунок 3.3 - Симетричний метод обходу

Кожен з вище описаних методів виконується з використанням рекурсії.

Рекурсією називається ситуація, коли підпрограма викликає сама себе. Саме три кроки що описані в кожному методі, використовують рекурсію для виконання обходу всього дерева. Без використання рекурсії за допомогою вищеописаних алгоритмів можна було б пройти лише бінарне дерево що складається з трьох вузлів, а така задача виконується дуже рідко. Тому рекурсія допомагає нам обійти всі вузли дерева за вказаними правилами.

4. ВИБІР ЗАСОБІВ РЕАЛІЗАЦІЇ

Для розробки нашого дипломного проекту на тему «Система моделювання методів обходу бінарних дерев» ми скористаємось середовищем швидкої розробки (RAD) Delphi 7 фірми Borland.

В Delphi 7, нам найбільш подобається швидкість та простота розробки додатку, без затрати часу на підготовчі дії такі як ініціалізацію(реєстрацію класу вікна, організацію обробки повідомлень і т.д.). При створенні проекту на Delphi ми більшу увагу приділяємо алгоритмам. Ми обрали Delphi за його набір компонентів для роботи з малюванням, ці компоненти знадобляться для створення та відображені бінарного дерева, та моделюванні методів його обходу. А також за можливість встановлення нових компонентів для покращення інтерфейсу користувача.

Основною перевагою при виборі для нас стало:

- швидкість розробки програми (RAD);

- висока продуктивність розробленого додатка;

- низькі вимоги розробленого додатка до ресурсів комп'ютера.

Для створення красивого дизайну Delphi - програми призначений AlphaControls - це набір стандартних і деяких унікальних компонентів, підтримуючих скіни AlphaSkins, чим забезпечують красивий інтерфейс додатка. Перевагою є те, що для жителів країн СНД всі компоненти є безкоштовними незалежно від того - комерційний проект чи ні.

Delphi - це інтегроване середовище швидкої розробки 32-х бітного програмного забезпечення для роботи під управлінням ОС Microsoft Windows. Середовище підтримує розробку Windows - застосунків на мові програмування Delphi, яка є наступницею мови Object Pascal.

В склад Delphi входять засоби, необхідні для розробки, тестування та встановлення програм, включаючи велику за обсягом бібліотеку компонентів (VCL - Visual Components Library), засоби візуального проектування, шаблони програм і форм. Середовище проектування Delphi є відкритою системою і дозволяє використовувати як компоненти VCL, так і компоненти від сторонніх розробників, саме завдяки цієї можливості ми використали набір допоміжних компонентів AlphaControls.

Delphi в основному використовується для розробки настільних додатків та корпоративних СКБД, проте цей інструмент можна використовувати для розробки будь-якого загального програмного забезпечення.

Елементами мови є набори компонентів, які дозволяють створювати додатки за найрізноманітнішими тематиками. Компоненти володіють наборами властивостей, що характеризують їх особливості. Крім властивостей, компоненти містять методи - програмний код, який обробляє значення властивостей та події - повідомлення, які компонент приймає від програми.

Також була розроблена сторінка довідки для користувача засобами html та css.

HTML (HyperText Markup Language)

Мова розмітки гіпертексту - це система верстки, яка визначає, як і які елементи повинні розташовуватися на веб-сторінці. Інформація на сайті, спосіб її подання та оформлення залежать виключно від розробника і тих цілей, які він перед собою ставить.

CSS (Cascading Style Sheets)

HTML задає основну структуру веб-сторінки, а також вказує, які елементи на ній присутні. Само оформлення веб-сторінки, положення і вид елементів покладено на стилі або CSS (Cascading Style Sheets, каскадні таблиці стилів). Коли говорять про верстку веб-сторінок, мається на увазі синергія HTML і CSS. що таке синергія? Сам HTML не представляє окремого інтересу, в силу своєї простоти і обмеженості. Також і CSS не грає окремої ролі, оскільки прив'язується до певних елементів коду і задає їх оформлення.

Тому працюючи разом в одній зв'язці, вони перетворюють скромну сторінку в той документ, який придумав і намалював дизайнер. Таке взаємне посилення властивостей, загальний ефект і є синергія.

Будь-яка веб-сторінка це, по суті, комбінація HTML-коду і CSS-коду.

4.2 ВИБІР ТЕХНІЧНИХ ЗАСОБІВ

Система моделювання методів обходу бінарних дерев

Специфікація

482.ТБЕК.3 234.006-01

Листів 2

Розробник: Савченко О.О.

Керівник: Бойко С.В.

Тальне 2013

ДОДАТОК Б

СИстема моделювання методів обходу бінарних дерев

Текст програми

482.ТБЕК.3 234-01 12 01

Листів 14

Розробник Савченко О.О.

Тальне 2013

АНОТАЦІЯ

В даному документі представлена частина тексту програми, за допомогою якої створюється бінарне дерево, та моделюється три методи обходу дерева.

Документ складається із 14 сторінок.

unit Main; {Головний модуль}

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, sSkinManager, StdCtrls, sRadioButton, sLabel, sEdit, sSpinEdit,

Buttons, sBitBtn, sGroupBox, ExtCtrls, sPanel, sSpeedButton, ComCtrls,

sStatusBar, Math, sMemo;

type

TNode = class(TImage) //Клас вузла що спадкується від класу TImage

public value: integer; //значення вузла

public l:integer; //вказівник на лівого нащадка

public r:integer; //вказівник на правого нащадка

public Prt: integer; //вказівник на предка

constructor Create(i: Integer);

end;

TForm1 = class(TForm)

sStatusBar1: TsStatusBar;

panelRight: TsPanel;

sGroupBox1: TsGroupBox;

sLabel1: TsLabel;

sSkinManager1: TsSkinManager;

sGroupBox2: TsGroupBox;

radioDirectMethod: TsRadioButton;

radioFeedbackMethod: TsRadioButton;

seHeightTree: TsSpinEdit;

radioSymmetricMethod: TsRadioButton;

btnBypassTree: TsBitBtn;

btnCreateTree: TsBitBtn;

Image1: TImage;

lCountNode: TsLabel;

sPanel1: TsPanel;

sLabel2: TsLabel;

resultPath: TsMemo;

sWebLabel1: TsWebLabel;

sWebLabel2: TsWebLabel;

procedure DrawTree(T : array of TNode); //процедура малювання дерева

procedure pObhod(i : integer); //прямий метод обходу

procedure sObhod(i : integer); //симетричний метод

procedure zObhod(i : integer); //зворотній метод

procedure Delay(Value: Cardinal); //процедура затримки

procedure btnCreateTreeClick(Sender: TObject); //процедура створення дерева

procedure seHeightTreeChange(Sender: TObject); //обрахунок кількості вузлів

procedure btnBypassTreeClick(Sender: TObject); //виконання обходу дерева

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Tree: array of TNode; //дерево

NodesCount, i:integer;

strPath : String; //шлях обходу одного із методів

implementation

{$R *.dfm}

//Реалізація процедури прямий метод обходу

procedure TForm1.pObhod(i:integer);

var resultLine:String;

begin

if i<>-1 then //якщо вузол не лист (-1)

begin

if strPath='' then strPath:=IntToStr(Tree[i].value) //записуємо значення першого вузла

else strPath:=strPath+' - '+IntToStr(Tree[i].value); //будуємо шлях обходу

Delay(4000); //затримка

Tree[i].Picture.LoadFromFile('img\p'+IntToStr(i+1)+'.png'); //змінюємо вигляд пройденого вузла

pObhod(Tree[i].l); //резурсивно обходимо в прямому порядку ліве піддерево

pObhod(Tree[i].r); //резурсивно обходимо в прямому порядку праве піддерево

end;

end;

//Реалізація процедури симетричний метод обходу

procedure TForm1.sObhod(i:integer);

begin

if i<>-1 then //якщо вузол не лист (-1)

begin

sObhod(Tree[i].l); //проходимо в симетричному порядку ліве піддерево

Delay(4000); //затримка

if strPath='' then strPath:=IntToStr(Tree[i].value)

else strPath:=strPath+' - '+IntToStr(Tree[i].value); //записуємо шлях обходу

Tree[i].Picture.LoadFromFile('img\s'+IntToStr(i+1)+'.png'); //змінюємо вигляд вузла який відвідали

sObhod(Tree[i].r); //проходимо в симетричному порядку праве піддерево

end;

end;

//Реалізація процедури зворотній метод обходу

procedure TForm1.zObhod(i:integer);

begin

if i<>-1 then

begin

zObhod(Tree[i].l); //обхід в зворотному порядку ліве піддерево

zObhod(Tree[i].r); //обхід в зворотному порядку ліве піддерево

Tree[i].Picture.LoadFromFile('img\z'+IntToStr(i+1)+'.png'); //змінюємо вигляд вузла який відвідали

Delay(4000);

if strPath='' then strPath:=IntToStr(Tree[i].value) //записуємо шлях обходу

else strPath:=strPath+' - '+IntToStr(Tree[i].value);

end;

end;

//Реалізація процедури затримки (застосовується під час проходу по дереву для того щоб користувач міг переглянути як саме виконується обхід)

procedure TForm1.Delay(Value: Cardinal);

var

F, N: Cardinal;

begin

N := 0;

while N <= (Value div 10) do

begin

SleepEx(1, True);

Application.ProcessMessages;

Inc(N);

end;

F := GetTickCount;

repeat

Application.ProcessMessages;

N := GetTickCount;

until (N - F >= (Value mod 10)) or (N < F);

end;

//Реалізація конструктора нашого класу TNodode(вузла)

constructor TNode.Create(i: integer); //конструктор вузла

begin

inherited Create(nil);

Self.Picture.LoadFromFile('img\'+IntToStr(i+1)+'.png'); //завантажуємо зображення

self.Width:=30; //ширина вузла

self.Height:=30; //висота вузла

end;

//Реалізація процедури малювання дерева

procedure TForm1.DrawTree(T:array of TNode); //малюємо дерево

var i,n,x,h,mid,ShiftH,StepH,W:integer;

begin

PatBlt(Image1.Canvas.Handle, 0, 0, Image1.ClientWidth, Image1. Client Height, WHITENESS);

h:=high(T);

W:=Image1.Width;

begin

mid:=W div 2;

for i:=0 to h do

begin

if i>0 then n:=trunc(ln(i+1)/ln(2))

else n:=0;

x:=i-round(power(2,n))+1;

StepH:=(W div (round(power(2,n))+1));

if n=0 then ShiftH:=0

else ShiftH:=(StepH div 2)+StepH*(x-round(power(2,n)/2));

T[i].Left:= (W div 2) + ShiftH+Image1.Left-10; //розміщення вузлів по осі x

T[i].Top:=n*50+10+Image1.Top+10; //розміщення вузлів по осі y

end;

Image1.Canvas.Pen.Color:=clGray;

for i:=1 to h do //малювання гілок дерева

begin

Image1.Canvas.MoveTo(T[i].Left+14,T[i].Top+15);

Image1.Canvas.LineTo(T[T[i].Prt].Left+14,T[T[i].Prt].Top+15);

end;

end;

end;

//Реалізація процедури створення дерева

procedure TForm1.btnCreateTreeClick(Sender: TObject);

var i,n,x,p:integer;

begin

if seHeightTree.Value>5 then seHeightTree.Value:=5;

if seHeightTree.Text='' then seHeightTree.Value:=2;

if not(sGroupBox2.Enabled) then sGroupBox2.Enabled:=true;

if Length(Tree)>0 then //якщо дерево вже створене

for i:=0 to Length(Tree)-1 do //проходження по всьому дереву

Tree[i].Free; //видалити вузли

NodesCount:=round(power(2,seHeightTree.Value))-1; //кількість вузлів

SetLength(Tree,NodesCount); //створення дерева що містить NodesCount вузлів

for i:=0 to NodesCount-1 do

begin

Tree[i]:=TNode.Create(i); //створення вузла і завантаження його зображення

Tree[i].Parent:=Image1.Parent;

end;

Tree[0].value:=1;

Tree[0].l:=1;

Tree[0].r:=2;

for i:=1 to NodesCount-1 do // присвоєння кожному елементу номера батьківського вузла

begin

n:=trunc(ln(i)/ln(2));

x:=i-round(power(2,n));

p:=trunc(round(power(2,n-1))+ ((x-1)/2));

if p<0 then p:=0;

Tree[i].Prt:=p;

if i<(Power(2,(seHeightTree.Value-1))-1) then //якщо поточний вузол знаходиться на перед останьому рівні

begin

Tree[i].l := Tree[i-1].l+2; // то присоїти його нащадкам індекси елементів на останьому рівні

Tree[i].r := Tree[i].l+1;

Tree[i].value:=i+1;

end

else // якщо вузоз знаходится на останьому рівні позначаємо його як лист (-1)

begin

Tree[i].l:=-1;

Tree[i].r:=-1;

Tree[i].value:=i+1;

end;

end;

DrawTree(Tree); //малюємо дерево

end;

//Реалізація процедури визначення вузлів у дереві вказаної висоти

procedure TForm1.seHeightTreeChange(Sender: TObject);

begin

lCountNode.Caption:='Вузлів: '+floattostr(Power(2,seHeightTree.Value)-1);

end;

//Реалізація процедури яка розпочинає обхід дерева по вказаному методу

procedure TForm1.btnBypassTreeClick(Sender: TObject);

begin

strPath:=''; //шлях на початку пустий

resultPath.Lines.Clear; //очищуємо поле результату

if radioDirectMethod.Checked then //якщо вибраний прямий метод

begin

sStatusBar1.Panels.Items[0].Text:='Режим: обходу дерева';

sStatusBar1.Panels.Items[1].Text:='Метод: Прямий';

resultPath.Lines.Add('Бінарне дерево');

resultPath.Lines.Add('висота дерева: [ '+IntToStr(seHeightTree.Value)+']');

resultPath.Lines.Add('кількість вузлів: [ '+IntToStr(NodesCount)+' ]');

resultPath.Lines.Add('метод обходу: [ прямий ]');

btnBypassTree.Enabled:=false;

pObhod(0); //виконуємо обхід прямим методом

btnBypassTree.Enabled:=true;

sStatusBar1.Panels.Items[0].Text:='';

sStatusBar1.Panels.Items[1].Text:='';

resultPath.Lines.Add('шлях обходу: [ '+strPath+' ]'); //записуємо результат обходу

end

else

if radioFeedbackMethod.Checked then //якщо вибраний зворотній метод

begin

sStatusBar1.Panels.Items[0].Text:='Режим: обходу дерева';

sStatusBar1.Panels.Items[1].Text:='Метод: Зворотній';

resultPath.Lines.Add('Бінарне дерево');

resultPath.Lines.Add('висота дерева: [ '+IntToStr(seHeightTree.Value)+']');

resultPath.Lines.Add('кількість вузлів: [ '+IntToStr(NodesCount)+' ]');

resultPath.Lines.Add('метод обходу: [ зворотній ]');

btnBypassTree.Enabled:=false;

zObhod(0); //виконуємо обхід зворотнім методом

btnBypassTree.Enabled:=true;

sStatusBar1.Panels.Items[0].Text:='';

sStatusBar1.Panels.Items[1].Text:='';

resultPath.Lines.Add('шлях обходу: [ '+strPath+' ]'); //записуємо результат обходу

end

else

if radioSymmetricMethod.Checked then //якщо вибраний симетричний метод

begin

sStatusBar1.Panels.Items[0].Text:='Режим: обходу дерева';

sStatusBar1.Panels.Items[1].Text:='Метод: Симетричний';

resultPath.Lines.Add('Бінарне дерево');

resultPath.Lines.Add('висота дерева: [ '+IntToStr(seHeightTree.Value)+']');

resultPath.Lines.Add('кількість вузлів: [ '+IntToStr(NodesCount)+' ]');

resultPath.Lines.Add('метод обходу: [ симетричний ]');

btnBypassTree.Enabled:=false;

sObhod(0); //виконуємо обхід симетричним методом

sStatusBar1.Panels.Items[0].Text:='';

sStatusBar1.Panels.Items[1].Text:='';

btnBypassTree.Enabled:=true;

resultPath.Lines.Add('шлях обходу: [ '+strPath+' ]'); //записуємо результат обходу

end;

end;

end.

Index.html {Сторінка довідки користувача}

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" >

<head>

<title>Допомога | СММОБД</title>

<meta http-equiv="content-type" content="text/html; charset=utf-8" />

<link rel="stylesheet" type="text/css" href="style.css" />

</head>

<body>

<div id="holder">

<div id="header">

<h1>Сторінка допомоги</h1>

<h2>Система моделювання методів обходу бінарних дерев</h2>

</div>

<div id="menu"></div>

<div id="undermenu"></div>

<div id="content">

<!-- Document starts. -->

<h1>Допомога</h1>

<ul>

<li><a href="#createtree" name="hcreate_tree">Створення дерева</a></li>

<li><a href="#methods">Методи обходу</a></li>

<li><a href="#pmetod">Прямий метод</a></li>

<li><a href="#zmetod">Зворотній метод</a></li>

<li><a href="#smetod">Симетричний метод</a></li>

</ul>

<h3 id="intro"><a name="createtree">Створення дерева</a></h3>

<p class="text">Для цього у правій частині за допомогою лічильника встановлюємо кількість рівнів створюваного повного бінарного дерева.</p><div align="center"><img src="create_tree.png"></div><p class="text">Система підказує нам, що при висоті у 4 рівні дерево матиме 15 вузлів. Для того щоб створити дерево потрібно натиснути кнопку "Створити" на екрані відобразиться створене дерево з вказаними параметрами.</p><div align="center"><img src="tree.png"></div><p class="text">Після створення дерева, стають доступними методи обходу цього дерева.</p>

<h3 id="dancingwithpenuines"><a href="#hcreate_tree" name="methods">Методи обходу</a></h3>

<p class="quote">"Над бінарним деревом є операція - його проходження, тобто потрібно обійти все дерево, зазначивши кожен вузол один раз. Існує 3 основних методи обходу бінарного дерева."</p>

<p class="text">Для того щоб обійти створене дерево одним із основних трьох методів в системі призначена наступна панель</p>

<div align="center"><img src="methods.png"></div>

<h3 id="mouthofthelion"><a href="#hcreate_tree" name="pmetod">Прямий метод</a></h3>

<p class="text">Алгоритм обходу бінарного дерева у прямому порядку має наступний вигляд:</p>

<ol>

<li>Потрапити в корінь</li>

<li>Пройти в прямому порядку ліве піддерево</li>

<li>Пройти в прямому порядку праве піддерево.</li>

</ol>

<p class="text">Для того щоб обійти створене дерево потрібно вибрати прямий метод на панелі вибору методу.</p>

<div align="center"><img src="methods.png"></div>

<p class="text">Після чого натиснути кнопку "Обхід дерева", на екрані буде відображатися покроковий обхід дерева прямим методом. Пройдений вузол позначається червоним кольором.</p>

<div align="center"><img src="pmetod.png"></div>

<h3 id="coughinghairballs"><a href="#hcreate_tree" name="zmetod">Зворотній метод</a></h3>

<p class="text">Алгоритм обходу бінарного дерева у зворотньому порядку має наступний вигляд:</p>

<ol>

<li>Пройти в зворотному порядку ліве піддерево</li>

<li>Пройти в зворотному порядку праве піддерево</li>

<li>Потрапити в корінь</li>

</ol>

<p class="text">Для того щоб обійти створене дерево потрібно вибрати зворотній метод на панелі вибору методу.</p>

<div align="center"><img src="pzmetod.png"></div>

<p class="text">Після чого натиснути кнопку "Обхід дерева", на екрані буде відображатися покроковий обхід дерева зворотнім методом. Пройдений вузол позначається оранжевим кольором.</p>

<div align="center"><img src="zmetod.png"></div>

<h3 id="end"><a href="#hcreate_tree" name="smetod">Симетричний метод</a></h3>

<p class="text">Алгоритм обходу бінарного дерева у зворотньому порядку має наступний вигляд:</p>

<ol>

<li>Пройти в симетричному порядку ліве піддерево</li>

<li>Потрапити в корінь</li>

<li>Пройти в симетричному порядку праве піддерево</li>

<p class="text">Для того щоб обійти створене дерево потрібно вибрати симетричний метод на панелі вибору методу.</p>

<div align="center"><img src="psmetod.png"></div>

<p class="text">Після чого натиснути кнопку "Обхід дерева", на екрані буде відображатися покроковий обхід дерева симетричним методом. Пройдений вузол позначається салатовим кольором.</p>

<div align="center"><img src="smetod.png"></div>

</ol>

<!-- Document ends. -->

</div>

</div>

</body>

</html>

Style.css {стилі довідки користувача}

/* Styles the body. */

body{

background: #777675 url(bg.png) repeat-x;

font: 12px arial, sans-serif;

color: #000;

margin: 0; padding: 0;

margin-bottom: 50px;

}

/* The design-holder. */

#holder{

position: relative;

left: 50%; top: 0;

width: 750px; height: auto;

margin-left: -375px; margin-bottom: 50px;

padding-bottom: 25px;

background-color: #F5F7F9;

border-left: 2px #436C78 solid; border-right: 2px #436C78 solid; border-bottom: 2px #436C78 solid;

}

/* Gives all the below id's the same values. */

#header, #menu, #undermenu, #content, #footer{

position: relative;

left: 0; top: 0;

width: 100%;

}

/* The header (with homepage name..). */

#header{

height: 160px;

background: url(menu-top-bg.png) repeat-x;

}

/* "Homepage name..." text above (bright coloured). */

#header h1{

position: absolute;

left: 20px; bottom: 40px;

margin: 0;

font: 1.4em georgia, serif;

color: #fff;

z-index: 1;

}

/* "Homepage name..." text below (dark coloured). */

#header h2{

position: absolute;

left: 21px; bottom: 19px;

margin: 0;

font: 1.4em georgia, serif;

color: #3E515E;

z-index: 0;

}

/* Fixes the links colours and such in the menu. */

#menu a{ color:#7A96A7; text-decoration:none; font-weight:bold; margin-left:10px; margin-right: 10px; }

#menu a:hover{ color:#000; text-decoration:none; margin-left:10px; margin-right: 10px; }

/* The fade-thingie below the menu. */

#undermenu{

height: 24px;

background: url(menu-bottom-bg.png) repeat-x;

}

/* The content holder */

#content{

height: auto;

background-color: transparent;

}

/* Styles the 'p'-tag. */

p{

margin: 25px 30px 10px 30px;

padding: 0;

text-align: justify;

text-indent: 15px;

font: 1em arial, sans-serif;

line-height: 1.5em;

color: #3E515E;

}

/* Use this (with the 'h4'-tag as header) if you want to quote something. */

.quote{

margin: 0 30px 10px 50px;

font: italic 0.8em verdana, sans-serif;

background-color: #fff;

padding: 5px;

text-indent: 0;

border: 1px #aaa dotted;

}

/* Use this if you don't want first lines on all paragraph to be moved 15px inn */

.noindent{

text-indent: 0;

}

/* The biggest font. */

h1{

font: 2em "times new roman", serif;

margin: 25px 0 0 30px;

padding: 0;

color: #3E515E;

}

/* The font below the biggest font. */

h2{

font: 0.8em georgia, serif;

margin: -3px 0 0 35px;

padding: 0;

color: #aaa;

}

/* Use this for paragraph titles. */

h3{

font: 1.4em verdana, serif;

text-decoration: underline;

margin: 20px 0 0 30px;

padding: 0;

color: #3E515E;

}

/* Use this on all paragraphs (but not #quote) wich are part of the article/documentation/etc.. */

.text{

margin: 15px 30px 10px 30px;

}

/* The title to be used when displaying a quote with '#quote'. */

h4{

font: 1.2em georgia, serif;

margin: 0 0 0 50px;

padding: 0;

color: #3E515E;

}

/* Italic text. */

i{

font: 1em arial, sans-serif;

font-style: italic;

color: #000;

}

/* Bold text. */

b{

font-weight: bold;

color: #3E515E;

}

/* The list ('li') holder. */

ul{

background-color: #fff;

}

/* Lists. */

li{

margin: 0 0 0 5px;

padding: 0;

}

/* Styles all links on the page (without the menu, wich allready have been styled). */

a{

color: #000;

font-weight: bold;

text-decoration: underline;

}

/* Same as above, exept this is the hover (mouse-over) effect. */

a:hover{

color: #3E515E;

text-decoration: none;

}

ДОДАТОК В

Система моделювання методів обходу бінарних дерев

Інструкція користувачеві

482.ТБЕК.3 234-01 34 01

Листів 7

Розробник Савченко О.О.

Тальне 2013

АНОТАЦІЯ

Даний документ містить відомості про призначення системи, а також інформацію, необхідну для розуміння функцій програми та її експлуатації.

Розглянуто основні принципи, можливості та загальні методи користування програмою.

Документ складається із 7 сторінок.

Запуск додатку

Для запуску додатку потрібно двічі натиснути праву кнопку миші по піктограмі додатку(рис В.1).

Рисунок В.1 - Піктограма додатку

При запуску програми для користувача відображається вікно програми що зображене на рис. В.2.

Рисунок В.2 - Вікно програми

Праворуч розташовані основні функції програми, знизу текстова область в якій відображаються результати створення та обходу дерева вибраним методом.

По середині розміщена робоча область в якій буде відображатися створене бінарне дерево.

Для прикладу створимо повне бінарне дерево кількість рівнів якого рівна 4 та обійдемо його за допомогою прямого методу обходу. Всі дії розбиті на два етапи.

Перший етап. Побудова дерева

Для цього у правій частині за допомогою лічильника встановлюємо значення 4 (рис. В.3). Система підказує нам, що при висоті у 4 рівні дерево матиме 15 вузлів.

Рисунок В.3 - Створення бінарного дерева

Після натиснення кнопки «Створити», система побудує бінарне дерево із вказаними параметрами (рис. В.4).

Рисунок В.4 - Бінарне дерево 4 рівнів

Другий етап. Обхід дерева вибраним методом

Після того як побудоване дерево переходимо до вибору методу обходу (рис. В.5)

Рисунок В.5 - Вибір методу обходу бінарного дерева

Для того щоб дізнатися більше про методи обходу потрібно натиснути на посилання під назвою допомога, відкриється браузер який вказаний по замовчуванню, із завантаженою сторінкою інструкції користувача на якій описані методи обходу бінарних дерев (рис В.6).

Рисунок В.6 - веб-сторінка інструкції користувача

Щоб нам наприклад переглянути допомогу про прямий метод обходу потрібно натиснути на посилання «Прямий метод» яке є якорем на описаний нижче метод (рис В.7).

Рисунок В.7 - веб-сторінка допомоги, опис прямого методу

Після того як ми вибрали метод обходу потрібно натиснути кнопку «Обхід дерева» розпочнеться обхід дерева, у стрічці стану відобразиться режим і метод обходу (рис. В.8).

Рисунок В.8 - Стрічка стану при обході бінарного дерева

А в полі результату відобразиться інформація про дерево і вибраний метод обходу (рис В.9).

Рисунок В.9 - інформація про створене дерево

При цьому в робочій області користувач переглядає візуально як відбуватиметься обхід дерева. Система при перегляді вузла дерева позначає його іншим кольором і після невеликої затримки переходить до наступного вузла дерева(рис В.10а, рис. В.10б).

Рисунок В.10а - Початок обходу дерева прямим методом

Рисунок В.10б - Закінчення обходу дерева прямим методом

По закінченню обходу дерева поле для виведення результату матиме наступний вигляд (рис. В.11).

Рисунок В.11 - Результат обходу дерева прямим методом

Остання стрічка містить шлях за яким був здійснений обхід 4-рівневого дерева за допомогою прямого методу обходу.

Размещено на Allbest.ru