Міністерство освіти Республіки Білорусь
Установа освіти
Білоруський державний університет інформатики і радіоелектроніки
Факультет безперервного та дистанційного навчання
Кафедра програмного забезпечення інформаційних технологій
Контрольна робота
Бінарні дерева
Мінськ - 2011
Введення
Мета роботи:
) Вивчити нелінійні динамічні структури даних у вигляді бінарного дерева. p align="justify">) Навчитися вирішувати прикладні задачі за допомогою структури даних бінарне дерево.
Побудувати дерево двійкового пошуку, вивести його на екран комп'ютера будь-яким способом (графічно, вкладеними дужками або відступами)
Текст програми розміщений у додатку. br/>
бінарний дерево комп'ютер програма
Побудова дерева
Побудова дерева полягає в послідовному введенні простих чисел з масиву в наступній послідовності: 5, 4, 8, 6, 1, 7, 3, 9. Дерево будується, починаючи з кореня. Алгоритм побудови:
Якщо вузол порожній, то число поміщається в нього.
Якщо ж він непорожній, то вхідний число порівнюється з числом вузла. У разі, якщо він більше, то він рекурсивно переноситься в праве піддерево, якщо ж менше - в ліве. p align="justify"> Таким чином, ми отримаємо бінарне дерево пошуку (рис. 1).
В
Рисунок 1 - Побудоване бінарне дерево
У поданні дерева застосовувалися відступи. Перед поданням необхідно визначити висоту дерева. Висота дерева визначається як максимальний шлях її проходження зверху-вниз. У даному випадку висота дерева (змінна h) дорівнює 4. p align="justify"> Подання дерева будується на двох масивах і на циклі, починаючи зі значення висоти дерева до 1. При даній ітерації з одного масиву у вихідний рядок з встановленими відступами за допомогою функції sc (s), де s - число, яке визначається значенням ітерації (рівнем дерева) залежно від місця розташування вузла (листа) в дереві, виносяться вузли (листя) дерева одного рівня. При цьому нащадки цих вузлів заносяться в інший масив (тобто в масив поміщаються вузли і листя наступного рівня по ітерації). Спочатку в один масив заноситься корінь дерева, а його нащадки в інший масив. Якщо у вузла немає нащадка, в масив заноситься цифра 0 (або два нулі, якщо це лист). Якщо ж замість вузла - 0, то тут перевіряється чи останній рівень дерева. У разі негативної відповіді - в масив поміщаються два нуля. Це необхідно, щоб коректно розрахувати кількість відступів на даному рівні дерева, зокрема між листям 3 і 7. У кінцевому рахунку, отримуємо уявлення дерева, показане на рис. 2
В
Рисунок 2 - Представлення дерева
Реалізувати три обходу дерева: зверху-вниз, зліва-направо і знизу-вгору. Вивести обходи на екран комп'ютера. Рекурсивні алгоритми проходження бінарного дерева по кожному із способів обходів включають 3 однакових процедури, де потрібно пройти корінь поддерева, ліве піддерево поточного кореня і праве піддерево поточного кореня. Напрямок обходу однозначно визначає послідовність виконання зазначених процедур.Сверху-вниз. Прямий порядок проходження означає обхід в напрямку зверху-вниз, коли після відвідин чергового розгалуження продовжується проходження вглиб дерева, поки не пройдені всі нащадки досягнутого вузла. З цієї причини прямий порядок проходження часто називають низхідним, або проходженням в глибину. br/>В
Рисунок 3 - Обхід зверху-вниз
Зліва-направо. При симетричному порядку дерево проходиться ліворуч-праворуч, породжуючи лексіграфіческі упорядковану послідовність ключів вузлів. Симетричність порядку виражається в тому, що якщо бінарне дерево відобразити щодо вертикальної осі, помінявши місцями ліві і праві вузли, то симетричний порядок проходження заміниться на протилежний лексіграфіческій. br/>В
Рисунок 4 - Обхід ліворуч-праворуч
Знизу-вгору. Якщо застосовується кінцевий порядок проходження, то виходить обхід дерева знизу-вгору, коли в момент відвідування будь-якого вузла всі його нащадки вже пройдені, а корінь дерева проходиться останнім. Через цю особливість обходу, кінцевий порядок часто називають висхідним або зворотним щодо прямого. br/>В
Рисунок 5 - Обхід знизу-вгору
Виконати сімметрічноправую прошивку дерева.
Під прошивкою дерева розуміється заміна за певним правилом порожніх покажчиків на синів ...
