Page 95 - 4656

Алгоритми і структури даних. Лабораторний практикум.

Лабораторна робота № 12.
Дерева

Мета: ознайомитись із поняття дерева у програмуванні.
Навчитися створювати бінарні дерева за допомогою мови Джава.

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

Концептуально важливими теоретичними поняттями,
сформованими у рамках структурного програмування, стали
поняття структури даних і абстрактного типу даних (АТД).
Структура даних складається з трьох основних компонент:
 набір предметно-орієнтованих операцій для обробки
специфічних типів абстрактних об’єктів предметної області, що
описується;
 структура пам’яті, у якій зберігаються дані, що описують
абстрактні об’єкти;
 інтерпретація (реалізація) кожної з операцій у термінах
структури пам’яті.
Перша компонента визначення – набір операцій над
абстрактними об’єктами – називається абстрактним типом даних.
Друга і третя компоненти разом складають реалізацію структури
даних.
АТД визначає, що робить структура даних – які операції
вона підтримує, але не розкриває, як вони виконуються.
Бінарне (бінарне) дерево (binary tree) - це упорядковане
дерево, кожна вершина якого має не більше двох піддерев,
причому для кожного вузла виконується правило: у лівому
піддереві містяться тільки ключі, що мають значення, менші, ніж
значення даного вузла, а в правому піддереві містяться тільки
ключі, що мають значення, більші, ніж значення даного вузла.

93