Порядок виконання роботи

Кафедра ЕОМ

Структура даних

БІНАРНЕ ДЕРЕВО ПОШУКУ

Методичні вказівки

до лабораторної роботи № 6

для студентів напряму

6.050102 “Комп’ютерна інженерія”

Львів – 2010

Методичні вказівки до лабораторної роботи "Структура даних БІНАРНЕ ДЕРЕВО ПОШУ-КУ" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 16 с.

Укладач: Лисак Т.А., ст. викладач каф.ЕОМ

Відповідальний

за випуск: Мельник А.О., д-р техн. наук, проф.

Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ

Юрчак І.Ю., доцент кафедри САПР, к.т.н.

МЕТА РОБОТИ

Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач.

2. Теоретичні відомості

Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з одного або більше вузлів (nodes), яка задовольняє наступним вимогам:

­ існує один відокремлений вузол - корень (root) дерева

­ інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T_1, ..., T_m і кожна з цих множин в свою чергу є деревом. Дерева T_1, ..., T_m мають назву піддерев (subtrees) даного кореня.

З цього визначення випливає, що кожний вузлів є в свою чергу коренем деякого піддерева. Кількість піддерев вузла має назву степеня (degree) цього вузла. Вузол степеню нуль називається кінцевим (terminal) або листком (leaf). Не корінь і некінцевий вузол також має назву вершини розгалуження (branch node). Нехай x - довільний вузол дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вузли на цьому шляху називаються предками (ancestors) x; якщо деякий вузол y є предком x, то x називається нащадком (descendant) y.

ПОРЯДОК ВИКОНАННЯ РОБОТИ

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

2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.

3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого текстового редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.

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

5. Написати контрольне опитування по темі.

6. Оформити звіт по роботі.

Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.

Дата добавления: 2015-11-16