Завдання на лабораторну роботу

4.1. Вибір варіанта індивідуального завдання

№ варіанта = [(місяць народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 20 + 1

4.2. Варіанти завдань

Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:

1. послідовність вершин дерева при проходженні його у прямому порядку;
2. послідовність листків дерева при проходженні його у зворотньому порядку;
3. послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.

Виконати індивідуальне завдання згідно з варіантом.

Варіанти завдань:

1. Cтворити дзеркальне до заданого дерево.

2. Вилучити з дерева всi листки.

3. Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка.

4. Вилучити з дерева всi вузли, що мають двох синів.

5. Додати до дерева листки так, щоб воно стало строго бінарним деревом.

6. Побудувати два бінарних дерева пошуку та визначити, чи є вони дзеркальним відображенням одне одного.

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

8. Знайти середнє геометричне значення всіх вузлів дерева.

9. Знайти середнє арифметичне значення всіх листків дерева.

10. Добудувати дерево до строго бінарного дерева.

11. Добудувати дерево до повного бінарного дерева.

12. Визначити, чи побудоване дерево є строго бінарним деревом.

13. Визначити, чи побудоване дерево є повним деревом.

14. Визначити, чи заданий вузол дерева є коренем, чи листком, чи вершиною.

15. Знайти найближчого спільного предка двох заданих вузлів дерева.

16. Знайти рівень заданого вузла дерева.

17. Знайти вузли, у яких кількість нащадків у лівому піддереві не дорівнює кількості нащадків у правому піддереві.

18. Знайти вузли, для яких висота лівого поддерева не дорівнює висоті правого піддерева.

19. Знайти довжину мінімального шляху між листами.

20. Знайти максимальний шлях між вузлами дерева.

6. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ

I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.

II. В звіті мають бути відображені наступні пункти:

1. Мета роботи

2. Постановка задачі

3. Динаміка вмісту БД пошуку

3.1. Послідовність 10 чисел

3.2. Схематичне зображення БД пошуку після обробки кожного числа з вхідної послідовності

3.3. Реалізація БД пошуку на базі масиву розмірністю 17

3.4. Обхід БД пошуку:

а) послідовність вершин дерева при проходженні його у прямому порядку;

б) послідовність листків дерева при проходженні його у зворотньому порядку;

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

4. Алгоритм розв’язання задачі

5. Результати виконання програми

Висновки

Додатоки (тексти програм з коментарями).

7. КОНТРОЛЬНІ ЗАВДАННЯ

1. Для заданого на Мал.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.

СПИСОК ЛІТЕРАТУРИ

1. Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.

2. Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.

3. Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.

4. Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982

5. Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с

ЗМІСТ

1. Мета роботи……………………………………..……………………………………………3

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

3. Порядок виконання роботи..............………………………………………..……..………...8

4. Завдання на лабораторну роботу....………………………………………..……..………...8

5. Вибір індивідуального завдання...…………………………………………………………13

6. Вимоги до оформлення звіту.......................……...……..…………………………………. 13

7. Контрольні завдання................………..……………………………………………………. 14

Список літератури ………...……….....................…………………………………………...14

Навчальне видання

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

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

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

з дисципліни

“Програмування. Частина IIІ. Структури даних та алгоритми"

для підготовки студентів напряму

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

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

Редактор

Комп’ютерне складання

Підписано до друку 2010 р.

Формат 70 х 100 ¹/₁₆. Папір офсетний.

Друк на різографі. Умовн. друк. арк....... Обл.-вид. арк.......

Наклад..... прим. Зам.

Поліграфічний центр

Видавництва Національного університету “Львівська політехніка”

вул. Колесси, 2, 79000, Львів

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