Лабораторна робота № 16 (2 год)
Тема: Реалізація абстрактного типу даних «Бінарне дерево».
Мета: формування навичок роботи з абстрактними типами даних
Література:
Архангельский А.Я. Язык Pascal и основы программирования в Delphi
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.
Культин Н.Б. Turbo Pascal в задачах и примерах
М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.
Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0
Меженный О.А. Turbo Pascal
Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal
Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.
Павловская Т.А. Паскаль. Программирование на языке высокого уровня
Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
Короткі теоретичні відомості
Концептуально важливими теоретичними поняттями, сформованими у рамках структурного програмування, стали поняття структури даних і абстрактного типу даних (АТД).
Структура даних складається з трьох основних компонент:
Набір предметно-орієнтованих операцій для обробки специфічних типів абстрактних об’єктів предметної області, що описується.
Структура пам’яті, у якій зберігаються дані, що описують абстрактні об’єкти.
Інтерпретація (реалізація) кожної з операцій у термінах структури пам’яті.
Перша компонента визначення – набір операцій над абстрактними об’єктами – називається абстрактним типом даних. Друга і третя компоненти разом складають реалізацію структури даних.
АТД визначає, що робить структура даних – які операції вона підтримує, але не розкриває, як вони виконуються.
Бінарне (бінарне) дерево (binary tree) - це упорядковане дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: у лівому піддереві містяться тільки ключі, що мають значення, менші, ніж значення даного вузла, а в правому піддереві містяться тільки ключі, що мають значення, більші, ніж значення даного вузла.
Бінарне дерево є рекурсивної структурою, оскільки кожне його піддерево сама є бінарним деревом і, отже, кожен його вузол в свою чергу є коренем дерева.Вузол дерева, що не має нащадків, називається листом.
Схематичне зображення бінарного дерева:
Бінарне дерево може представляти собою порожній безліч.Бінарне дерево може виродитися в список:

Організація даних за допомогою бінарних дерев часто дозволяє значно скоротити час пошуку потрібного елементу. Пошук елемента в лінійних структурах даних зазвичай здійснюється шляхом послідовного перебору усіх елементів, присутніх у даній структурі. Пошук по дереву не вимагає перебору всіх елементів, тому займає значно менше часу. Максимальне число кроків при пошуку по дереву одно висоті даного дерева, тобто кількості рівнів в ієрархічній структурі дерева.
Задачі для самостійного розв’язування
На міжміської телефонної станції картотека абонентів, що містить відомості про телефони та їх власників, організована як бінарне дерево. Скласти програму, яка:
Забезпечує початкове формування картотеки у вигляді бінарного дерева;
виробляє висновок всієї картотеки;
вводить номер телефону і час розмови;
виводить повідомлення на оплату телефонної розмови.
Програма повинна забезпечувати діалог за допомогою меню і контроль помилок при введенні.
Розрахувати максимальну глибину побудованого бінарного дерева
Побудувати бінарне дерево (дерево пошуку), а потім з нього видалити гілку, що починається з деякого ключа M.
Створити бінарне дерево будь-якого розміру, заповнити числами, вирівняти гілки (щоб по довжині вони відрізнялися не більше ніж на 1). Потім записати в файл значення цього дерева в порядку зростання.