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