Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ. Методичні вказівки до лабораторної роботи з Структура даних. Робота № 518727

Перехід до торгівельного партнера Binance

Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Комп'ютерна інженерія

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2010

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

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

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 6 для студентів напряму 6.050102 “Комп’ютерна інженерія” Львів – 2010 Методичні вказівки до лабораторної роботи "Структура даних БІНАРНЕ ДЕРЕВО ПОШУ-КУ" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 16 с. Укладач: Лисак Т.А., ст. викладач каф.ЕОМ Відповідальний за випуск: Мельник А.О., д-р техн. наук, проф. Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ Юрчак І.Ю., доцент кафедри САПР, к.т.н. 1. МЕТА РОБОТИ Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ТЕОРЕТИЧНІ ВІДОМОСТІ Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з одного або більше вузлів (nodes), яка задовольняє наступним вимогам: існує один відокремлений вузол - корень (root) дерева інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1, ..., Tm і кожна з цих множин в свою чергу є деревом. Дерева T1, ..., Tm мають назву піддерев (subtrees) даного кореня. З цього визначення випливає, що кожний вузлів є в свою чергу коренем деякого піддерева. Кількість піддерев вузла має назву степеня (degree) цього вузла. Вузол степеню нуль називається кінцевим (terminal) або листком (leaf). Не корінь і некінцевий вузол також має назву вершини розгалуження (branch node). Нехай x - довільний вузол дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вузли на цьому шляху називаються предками (ancestors) x; якщо деякий вузол y є предком x, то x називається нащадком (descendant) y. 3. ПОРЯДОК ВИКОНАННЯ РОБОТИ 1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики. 2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі. 3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого текстового редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму. 4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати. 5. Написати контрольне опитування по темі. 6. Оформити звіт по роботі. Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається. 4. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ 4.1. Вибір варіанта індивідуального завдання № варіанта = [(місяць народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 20 + 1 4.2. Варіанти завдань Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Виконати індивідуальне завдання згідно з варіантом. Варіанти завдань: Cтворити дзеркальне до заданого дерево. Вилучити з дерева всi листки. Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка. Вилучити з дерева всi вузли, що мають двох синів. Додати до дерева листки так, щоб воно стало строго бінарним деревом. Побудувати два бінарних дерева пошуку та визначити, чи є вони дзеркальним відображенням одне одного. Побудувати два бінарних дерева пошуку та визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї з його вершин. Знайти середнє геометричне значення всіх вузлів дерева. Знайти середнє арифметичне значення всіх листків дерева. Добудувати дерево до строго бінарного дерева. Добудувати дерево до повного бінарного дерева. Визначити, чи побудоване дерево є строго бінарним деревом. Визначити, чи побудоване дерево є повним деревом. Визначити, чи заданий вузол дерева є коренем, чи листком, чи вершиною. Знайти найближчого спільного предка двох заданих вузлів дерева. Знайти рівень заданого вузла дерева. Знайти вузли, у яких кількість нащадків у лівому піддереві не дорівнює кількості нащадків у правому піддереві. Знайти вузли, для яких висота лівого поддерева не дорівнює висоті правого піддерева. Знайти довжину мінімального шляху між листами. Знайти максимальний шлях між вузлами дерева. 6. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта. II. В звіті мають бути відображені наступні пункти: 1. Мета роботи 2. Постановка задачі 3. Динаміка вмісту БД пошуку 3.1. Послідовність 10 чисел 3.2. Схематичне зображення БД пошуку після обробки кожного числа з вхідної послідовності 3.3. Реалізація БД пошуку на базі масиву розмірністю 17 3.4. Обхід БД пошуку: а) послідовність вершин дерева при проходженні його у прямому порядку; б) послідовність листків дерева при проходженні його у зворотньому порядку; в) послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. 4. Алгоритм розв’язання задачі 5. Результати виконання програми Висновки Додатоки (тексти програм з коментарями). 7. КОНТРОЛЬНІ ЗАВДАННЯ 1. Для заданого на Мал.1 бінарного дерева (БД) дайте відповіді на наступні питання: Кількість вузлів БД. Глибина БД. Степінь БД. Степінь вузла 6. Рівень вузла 2. Всі вузли 3 рівня. Корінь БД . Всі листки БД. Всі вершини БД. Безпосередні нащадки вузла 4. Нащадки вузла 4. Безпосередні предки вузла 6. Предки вузла 8. Батько вузла 2. Сини вузла 4. Брат вузла 6. 2. Запишіть послідовність вузлів при проходження БД : у прямому порядку, у симетричному порядку, у зворотньому порядку. 3. Домалюйте це БД до найближчого строго БД. 4. Домалюйте це БД до найближчого повного БД. 5. Домалюйте це БД до найближчого майже повного строго БД. 6. Перемалюйте це БД після вилучення з нього вузла 4. 7. Для заданого на Мал.1 БД намалюйте його представлення на базі масиву розмірністю n=15. 8. Побудуйте бінарне дерево пошуку , згідно заданої послідовності. 5 , 1 , 8 , 3 , 8 , 9 , 6 , 0 , 7 , 1 , 4 , 6 , 2 , 0 , 1 , 7 , 9 , 5 . СПИСОК ЛІТЕРАТУРИ Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999. Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с. Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999. Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982 Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с ЗМІСТ Мета роботи……………………………………..……………………………………………3 Теоретичні відомості..........….………………………………………………………….…. .3 Порядок виконання роботи..............………………………………………..……..………...8 Завдання на лабораторну роботу ....………………………………………..……..………...8 Вибір індивідуального завдання ...…………………………………………………………13 Вимоги до оформлення звіту.......................……...……..…………………………………. 13 Контрольні завдання................………..……………………………………………………. 14 Список літератури ………...……….....................…………………………………………...14 НАВЧАЛЬНЕ ВИДАННЯ МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” Укладач Т.А.Лисак, ст. викладач каф.ЕОМ Редактор Комп’ютерне складання Підписано до друку 2010 р. Формат 70 х 100 1/16. Папір офсетний. Друк на різографі. Умовн. друк. арк. ...... Обл.-вид. арк. ...... Наклад ..... прим. Зам. Поліграфічний центр Видавництва Національного університету “Львівська політехніка” вул. Колесси, 2, 79000, Львів

Методичні вказівки до лабораторної роботи Структура даних

roman2013

24.01.2013 01:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись