Введення
древо бінарний програмний
Об'єктом розробки в курсовій роботі є структура даних - бінарне дерево пошуку.
Метою роботи є вивчення даної структури, а потім розробка програми на мові програмування C # з її реалізацією у вигляді класу.
В ході курсової роботи була розроблена Довідково-інформаційні системи на мові програмування C # , що описує структуру бінарного дерева пошуку і дозволяє виконувати з ним основні операції (додавання, видалення, пошук і так далі).
У пояснювальній записці розібрані основні поняття, пов'язані з бінарними деревами. Також описана робота з інтерфейсом користувача. У підрозділах «Опис розробленого програмного продукту» наведені структура та компоненти програмних засобів.
Організація даних за допомогою бінарних дерев пошуку дозволяє значно скоротити час пошуку потрібного елемента. Пошук елемента в лінійних структурах даних зазвичай здійснюється шляхом послідовного перебору всіх елементів, присутніх в даній структурі. Пошук по дереву не вимагає перебору всіх елементів, тому займає значно менше часу.
У даному курсовому проекті головною метою є розробка довідково-інформаційної системи на мові програмування C # , який надає спосіб організації даних у вигляді «бінарне дерево». Більше того в програму має бути закладено принцип, зручності, простоти і якості, що має на увазі відсутність у користувача переліку певних навичок, за винятком найпростішої комп'ютерної етики.
Розроблюваний програмний продукт відмінно підійде для організацій, які у своєму професійному середовищі стикаються з великою кількістю інформації.
Виходячи із завдань, актуальністю створюваної програми є скорочення часу роботи, раціональний розподіл часу, що дозволяє виконати великий обсяг роботи за більш короткі терміни.
1. Бінарне дерево
1.1 Деревовидна структура - «Бінарне дерево пошуку»
Бінарне (двійкове) дерево - це впорядкована дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: у лівому поддереве містяться тільки ключі, що мають значення, менші, ніж значення даного вузла , а в правому поддереве містяться тільки ключі, що мають значення, більші, ніж значення даного вузла [1].
Бінарне дерево є рекурсивної структурою, оскільки кожне його піддерево саме є бінарним деревом і, отже, кожен його вузол у свою чергу є коренем дерева.
Вузол дерева, що не має нащадків, називається листом.
Приклад бінарногодерева представлений на малюнку 1.1.
Малюнок 1.1 - Схематичне зображення бінарногодерева
Глибина бінарного дерева - це максимальний рівень листа дерева, інакше кажучи, довжина найдовшого шляху від кореня до листа дерева [2].
Можливі випадки, коли бінарне дерево може являти собою порожня множина або бінарне дерево може виродитися в список (малюнок 1.2), в даному випадку таке дерево буде називатися виродженим.
Малюнок 1.2 - виродження бінарне дерево
Бінарне дерево буде являти собою порожня множина, тільки у випадках відсутності кореня.
1.2 Термінологія
Термінологія, застосовувана для опису бінарних дерев [3]:
) вузол - це точка, де може виникнути гілка;
) корінь - «верхній» вузол дерева;
) гілка - відрізок, що описує зв'язок між двома вузлами;
) лист - вузол, з якого не виходять гілки, тобто не має піддерев;
) батьківським - називається вузол, який знаходиться безпосередньо над іншим вузлом;
) дочірнім - називається вузол, який знаходиться безпосередньо під іншим вузлом;
) предки даного вузла - це всі вузли на шляху вгору від даного вузла до кореня;
) нащадки - всі вузли, розташовані нижче даного;
) внутрішній вузол - вузол, який не є листом;
) порядок вузла - кількість його дочірніх вузлів;
) глибина вузла - кількість його предків плюс одиниця;
) глибина (висота) дерева - максимальна глибина всіх вузлів;
) довжина шляху до вузла - кількість гілок, які потрібно пройти, щоб дійди від кореня до даного вузла;
) довжина шляху дерева (довжина внутрішнього шляху) - су...
