двійкові дерева
Мета роботи: Вивчити способи ефективного зберігання та обробки інформації на прикладі бінарних дерев.
Загальні відомості
Бінарне дерево - це ієрархічна динамічна структура даних, що складається з вузлів і з'єднують їх дуг. У кожен вузол, крім одного, веде рівно одна дуга. Цей єдиний вузол називається коренем дерева. З кожною вершиною дерева зв'язується кінцеве число окремих дерев, званих піддеревами. На малюнку зображено дерево, у вузлах якого розташовуються символи: Вершина Y, що знаходиться безпосередньо нижче вершини X, називається безпосереднім нащадком X, а вершина X називається предком Y. Якщо вершина не має нащадків, то вона називається листом, якщо має, то називається внутрішньої вершиною . Наприклад, вершини D, E є безпосередніми нащадками вершини B; вершини H, I, J є листям. Очевидно, що для опису дерева потрібні посилання. Наведемо бінарне дерево як структуру типу Record, що містить як мінімум два поля - покажчики на ліве і праве піддерева, і поле даних, наприклад типу Integer: Основні операції над деревом До основних операцій над деревами відносяться: • занесення елемента в дерево; • обхід дерева; • видалення елемента з дерева.
Вставка елемента в дерево. Створити і вивести на екран дерево, елементи якого вводяться з клавіатури і мають цілий тип. Причому для кожної вершини дерева у всіх лівих вершинах повинні перебувати числа менші, а в правій великі, ніж числа, що зберігаються в цій вершині. Таке дерево називається деревом пошуку. Опишемо процедуру вставки в дерево нової вершини. При вставці в дерево вершина вставляється або як поддерево вже існуючої вершини або як єдина вершина дерева. Тому і ліва, і права зв'язку нової вершини повинні бути рівні nil. Коли дерево порожньо, значення переданої у вигляді параметра посилання одно nil. В цьому випадку потрібно змінити її так, щоб вона вказувала на нову вершину, яка була вставлена як коренева. При вставці другого елементу переданий з основної програми параметр ANode вже не буде дорівнює nil, і треба приймати рішення про те, в яке поддерево необхідно вставити нову вершину. Висновок елементів дерева. Опишемо процедуру виведення значень елементів двійкового дерева на екран. Для цього необхідно виконати повний обхід дерева. При обході дерева його окремі вершини відвідуються в певному порядку. Висновок двійкового дерева можна виробляти рекурсивно, виконуючи для кожної вершини три дії: • висновок числа, що зберігається в вузлі; • обхід лівого піддерева; • обхід правого піддерева. Порядок виконання цих дій визначає спосіб обходу дерева. Способи обходу: • прямий обхід (зверху вниз); • симетричний обхід (зліва направо); • зворотний обхід (від низу до верху). Процедура симетричного виведення дерева має наступний вигляд: Видалення з дерева. Безпосереднє видалення елемента з упорядкованого дерева реалізується досить просто, якщо ця вершина є кінцевою: або з неї виходить тільки одне ребро: Для цього потрібно змінити відповідне посилання у попередньої вершини. Якщо ж з видаляється вершини виходить дві гілки, то потрібно знайти підходящу вершину дерева, яку можна було б вставити на місце видаляється вершини. В цьому випадку видаляється елемент потрібно замінити або на самий правий елемент його лівого піддерева, або на самий лівий елемент його правого піддерева. Такі елементи не можуть мати більше одного нащадка. Нехай задана наступна структура: Допоміжна процедура Del викликається тільки в третьому випадку. Вона «спускається» уздовж самої правої гілки лівого піддерева видаляється вузла q ^ і потім замінює дані (поле Data) в q ^ відповідними значеннями самого правого вузла R ^ цього лівого піддерева, після чого від R ^ можна звільнитися. На малюнку задано початкове дерево (а), з якого послідовно видаляються вузли зі значеннями 13, 15, 5, 10. Отримані дерева показані на рис. b - e.
Контрольні питання
1. Що таке рекурсивний алгоритм? 2. З яких частин будується визначення рекурсивного алгоритму? 3. Що є обов'язковим в будь-якому рекурсивном алгоритмі? 4. Чи можна рекурсию замінити итерацией? Чи можна ітерацію замінити рекурсією? 5. Який принцип побудови динамічної структури «дерево»? 6. Перерахуйте подібності та відмінності динамічних структур типу «лінійний список», «стек», «дерево». 7. Перерахуйте структури, які можна представити у вигляді дерева, які зустрічаються в повсякденному житті. 8. Закінчіть фразу: «Список - це дерево, в якому ...».
У всіх завданнях маються на увазі дерева двійкового поіска.1. Написати рекурсивну числову функцію, підраховують суму елементів дерева. 2. Написати функцію, яка знаходить найбільший елемент дерева. 3. Написати функцію, яка знаходить найменший елемент дерева. 4. Напишіть процедуру, яка видаляє з дерева все парні елементи. 5. Написати рекурсивну процедуру, яка визначає число входжень заданого елемента в дерево. 6. Написати рекурсивну процедуру, яка друкує елементи з усіх листів дерева. 7. Написати процедуру, яка виводить на екран дерево, показуючи глибину вузлів відступом від лівого краю екрана. Наприклад, дерево буде виведено так: 1 група 1 курс 2 група ФМІ 3 група 2 курс 4 група 8. Написати рекурсивну функцію, яка визначає глибину заданого елемента на дереві і повертає -1, якщо такого елемента немає. 9. Написати процедуру, яка друкує (по одному разу) всі вершини дерева. 10. Написати процедуру, яка по заданому n вважає число всіх вершин глибини n в заданому дереві. 11. Написати процедуру, яка вважає глибину дерева. 12. Відсортувати масив А шляхом включення його елементів в дерево і скопіювати відсортовані дані назад в А. 13. Задана послідовність слів. Визначити частоту входження кожного з слів в послідовність. Вказівка. Для вирішення завдання будь-яке слово шукається в дереві, яке на початковому етапі порожньо. Якщо слово знайдено, то лічильник його входжень збільшується на одиницю, якщо немає, то слово включається в дерево з одиничним значенням лічильника. Назад На головну