ЗАВДАННЯ. 8.1.1 Вивчити операції над бінарними деревами

8.1.1 Вивчити операції над бінарними деревами.

8.1.2 Розробить програму знаходження усiх дублiкатiв у списку чисел.

8.1.3 Розробить програму знаходження бiнарних дерев.

8.1.4 Pозробить програму подання виразу, утримуючого операнди та бінарні оператори у виді строго бiнарного дерева.

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

8.2 Описання методики застосування бінарних дерев

8.2.1 Алгоритми і процеси, що використовують бінарні дерева, роспадаються на двi фази. У першій фазi будується бiнарне дерево, а у другій воно проходиться.

8.2.2 Вхідний файл, містить список чисел, який необхiдно надрукувати у возрастающому порядку.

8.2.3 Знаходження дублiкатiв застосовується шляхом використання бiнарного дерева: зчитується перше число та поміщується у вузол, який стає корнем бiнарного дерева. Якщо значення співпадають, тодi це повторюється для пів-дерева ліворуч,а якщо бiльше, тодi для правого продовжується, поки не зустрiнеться дублікат, або пока ми не достигнем пустого дерева в останноьму.

Приклад:

Дана послідовність чисел:

14 15 4 9 7 18 3 5 16 4 20 17 9 14 5

/ \

4 15

/ | \

3 9 18

/ \

7 16

/ \

5 17

Рис. 8.2.1 Бiнарне дерево, побудувано для знаходження дублiкатiв

8.3 Змiст звіту

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

8.3.2 Описання методiв примінення бiнарних дерев.

8.3.3 Алгоритм.

8.3.4 Текст програми.

Контрольнi питання

8.4.1 Яке дерево є бiнарним?

8.4.2 Класiфiкация бiнарних дерев.

8.4.3 Операцiї над бiнарними деревами.

8.4.4 Примінення бiнарних дерев.

8.4.5 Методи проходження бiнарних дерев.

8.4.6 Подання списків у вигляді бiнарних дерев.

8.4.7 Як застосовується пошук заданого елементу, знищення заданого елементу з таблиці?

9 ЛІТЕРАТУРА

Основна:

9.1 Костин А.Е., Шаньгин В.Ф. «Организация и обработка структур даних в вычислительных системах».-М.:Высшая школа,1987,-242 с.

9.2 Вирт Н. «Алгоритмы+структуры данных=программы». -М. Мир, 1985.

9.3 Бертисс А.Т. «Структуры данных»./Пер. с англ. - М.: Статистика, 1974.

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

Додаткова:

9.5 Дрибас В.П. «Реляционные модели баз данных».-Минск: БГУ, 1982.

9.6 Зайцев В.Ф. «Кодирование информации в ЕС ЭВМ». -М.: Радио и связь, 1986.

9.7 Макаровский Б.Н. «Информационные системы и структуры данных».-М.:Статистика, 1980.

9.8 «Данные в языках программирования: Абстракции и топология»./Пер. с англ.-М.:Мир,1982.

9.9 Вегнер П. «Программирование на языке АДА». /Пер. с англ.-М.,Мир,1983.

9.10 Ленгсам И.О. Генстайм М.О. «Структуры данных для персональных ЭВМ».,1992.

9.11 Кнут Д. «Искусство программирования для ЭВМ».-М.:Мир, 1976-1978.