8-9. Дерева і алгоритми їх обробки

Перелік алгоритмів, що розглядаються

  • побудова ідеально збалансованого дерева;
  • виведення на екран бінарного дерева;
  • обходи дерев;
  • пошук із включенням у дереві пошуку.

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

Питання для повторення

  1. Особливості роботи з покажчиками.

Постановка задачі

Двійкове дерево – це скінченна множина вершин, яка або порожня, або складається з кореня з двома окремими двійковими деревами, які називають лівим і правим піддеревом кореня.

Необхідно:

  • побудувати ідеально збалансоване дерево, тобто дерево, у якого число вершин у лівих і правих під деревах відрізняється не більше, ніж на 1;
  • здійснити обхід дерева, тобто перелічити вершини дерева у певному порядку;
  • реалізувати алгоритми побудови і зміни дерево пошуку, тобто дерево, для кожної вершини ti якого справедливе твердження, що всі ключі лівого піддерева ti  менше ключа ti, а всі ключі правого піддерева ti  більше нього.

Опис алгоритмів

Опис структури даних
  • набір комірок, кожна з яких містить елемент списку (дані) і покажчики на ліве і праве піддерево;
  • комірка (корінь), яка містить покажчик на перший елемент списку.

1. Побудова ідеально збалансованого дерева

Ідея

Взяти одну вершину як корінь і побудувати тим самим способом спочатку ліве піддерево з n1=n / 2 вершинами (n — кількість вершин у початковому дереві), а потім праве піддерево з n2=n—n1—1

Псевдокод функції TreeBalans(кількість_вершин)
якщо кількість_вершин == 0
  то вузол = NULL
  інакше
  {
    n1=n/2
    вузол.дані = чергове число
    ліве = TreeBalans (n1)
    праве = TreeBalans (n — n1 — 1)
  }
повернути вузол

2.Обходи дерева

Ідея
Процес обходу розбивається на три частини: відвідання кореня, обхід лівого піддерева та обхід правого піддерева. Різні обходи відрізняються порядком виконання цих кроків.
Псевдокод

Лівий_обхід (корінь)
{
  відвідати корінь
  якщо корінь.ліве != NULL, то Лівий_обхід (корінь.ліве)
  якщо корінь.праве != NULL, то Лівий_обхід (корінь.праве)
}

Симетричний_обхід (корінь)
{
  якщо корінь.ліве != NULL, то Симетричний_обхід (корінь.ліве)
  відвідати корінь
  якщо корінь.праве != NULL, то Симетричний_обхід (корінь.праве)
}

Правий_обхід (корінь)
{
  якщо корінь.ліве != NULL, то Правий_обхід (корінь.ліве)
  якщо корінь.праве != NULL, то Правий_обхід (корінь.праве)
  відвідати корінь
}

3. Пошук із включенням у дереві пошуку

Ідея
Порівняти шуканий елемент з коренем, якщо він менший значення, то перейти до лівого піддерева, інакше перейти до правого піддерева. Процес припиняється, коли відповідне піддерево є порожнім.
Псевдокод процедури Пошук (ключ, корінь)
якщо корінь = NULL
  то створити нову термінальну вершину зі значенням ключ
  інакше
     якщо ключ < корінь.дані
       то Пошук (ключ, корінь.ліве)
       інакше Пошук (ключ, корінь.праве)

Завдання для виконання

Постановка задачі

Скласти програми, що забезпечують виконання операцій з деревами. Програма повинна забезпечувати
  • автоматичну генерацію послідовності чисел як майбутніх вершин дерева
  • побудову дерева із зазначеними властивостями;
  • виведення дерева на екран;
  • виконання вказаних викладачем дій з деревом.

Технічні умови

  • елементи дерева є цілими числами.

Хід роботи

  1. Скласти програму BalanceTree.cpp для побудови і виведення на екран ідеально збалансованого дерева.
  2. Виконати програму в покроковому режимі для 7 значень
  3. Здійснити вказаний викладачем обхід побудованого дерева.
  4. Скласти програму SearchTree.cpp для побудови і виведення на екран дерева пошуку.
  5. Виконати в покроковому режимі вказану викладачем процедуру роботи з деревом пошуку.

Запитання для самоконтролю

  1. Яка структура називається двійковим деревом?
  2. Які властивості має ідеально збалансоване дерево?
  3. Поясніть, у чому полягає обхід дерева. У чому відмінність різних обходів дерева.
  4. Яке дерево називається деревом пошуку?
  5. Як здійснюється пошук елемента у дереві пошуку із включенням?