Крім лінійних структур існують і нелінійні, за допомогою яких задаються ієрархічні зв'язку даних. Для цього використовуються графи, а серед них мережеві і деревовидні структури. Розглянемо один вид дерев - бінарне дерево.
Бінарне (двійкове) дерево - це кінцеве безліч елементів, яке або порожня, або містить один елемент, званий коренем дерева, а інші елементи безлічі діляться на два непересічних підмножини, кожне з яких саме є бінарним деревом. Ці підмножини називаються правим та лівим піддеревами вихідного дерева.
Мал. 8 Двійкове дерево
На рис. 8 показаний найбільш поширений спосіб подання бінарного дерева. Воно складається з дев'яти вузлів. Коренем дерева є вузол А. Ліве піддерево має корінь В, а праве піддерево - корінь С. Вони з'єднуються відповідними гілками, що виходять із А. Відсутність гілки означає порожнє поддерево. Наприклад, у поддерева з коренем З немає лівого піддерева, воно порожньо. Пусто і праве піддерево з коренем Е. Бінарні піддерева з корінням D. G. H і I мають порожні ліві і праві піддерева. Вузол, що має порожні праве і ліве піддерева, називається листом. Якщо кожен вузол бінарного дерева, який не є листом, має непорожній праве і ліве піддерева, то дерево називається строго бінарним
Рівень вузла в бінарному дереві визначається наступним чином: рівень кореня завжди дорівнює нулю, а далі номера рівнів при русі по дереву від кореня збільшуються на 1 по відношенню до свого безпосереднього предка. Глибина бінарного дерева - це максимальний рівень листа дерева, інакше кажучи, довжина найдовшого шляху від кореня до листа дерева. Вузли дерева можуть бути пронумеровані за наступною схемою (див. Рис. 9)
Мал. 9 Схема нумерації вузлів двійкового дерева
Номер кореня завжди дорівнює 1, лівий нащадок отримує номер 2, правий - номер 3. Лівий нащадок вузла 2 повинен отримати номер 4, а правий - 5, лівий нащадок вузла 3 отримає номер 6, правий - 7 і т.д. Неіснуючі вузли не нумеруються, що, однак, не порушує зазначеного порядку, так як їх номери не використовуються. При такій системі нумерації в дереві кожен вузол отримує унікальний номер.
Повний бінарне дерево рівня n - це дерево, в якому кожен вузол рівня n є листом і кожен вузол рівня менше n має непусті праве і ліве піддерева.
Майже повне бінарне дерево визначається як бінарне дерево, для якого існує невід'ємне ціле k таке, що:
1) кожен лист в дереві має рівень k або k +1;
2) якщо вузол дерева має правого нащадка рівня k +1, тоді все його ліві нащадки, які є листами, також мають рівень k +1.
Розглядаючи дії над деревами, можна сказати, що для побудови дерева необхідно формувати вузли, і, визначивши попередньо місце включення, включати їх в дерево. Кількість вузлів визначається необхідністю. Алгоритм включення повинен бути відомий і постійний. Вузли дерева можуть бути використані для зберігання будь-якої інформації.
Може виникнути завдання і знищення дерева в той момент, коли необхідність в ньому (в інформації, записаної в його елементах) відпадає. У ряді випадків може знадобитися знищення поддерева.
Для того, щоб сукупність вузлів утворила дерево, необхідно якимось чином формувати і використовувати зв'язку вузлів зі своїми предками і нащадками. Все це дуже нагадує дії над елементами списку.
Розглянемо приклад формування двійкового дерева. Припустимо, що потрібно сформувати бінарне дерево, вузли (елементи) якого мають таке значення ознаки: 20, 10, 35, 15, 17, 27, 24, 8, 30. В цьому ж порядку вони і будуть надходити для включення в двійкове дерево. Першим вузлом в дереві (коренем) стане вузол із значенням 20. Звернути увагу: пошук місця підключення чергового елемента завжди починається з кореня. До кореня зліва підключається елемент 10. До кореня справа підключається елемент 35. Далі елемент 15 підключається справа до 10, проходячи шлях: корінь 20 - наліво - елемент 10 - направо - підключення, так як далі шляху немає. Процес триває до вичерпання включаються елементів. Результат представлений на рис. 10.
Мал. 10 Побудова бінарного дерева.
Значення елементів дерева: 20, 10, 35, 15, 17, 27, 24, 8, 30
При створенні двійкового дерева окремо вирішується питання з можливістю включення елементів з дублюючими ознаками. Алгоритм двійкового пошуку дозволяє при включенні коректно розташувати вузли в дереві, однак при пошуку вже включених елементів виникають складності, так як при стандартному варіанті пошуку буде вибиратися тільки один з дублів. Для виявлення всіх дублів повинен бути застосований алгоритм такого обходу дерева, при якому кожен вузол дерева буде обраний один раз.
Наведемо приклад опису полів і елементів, необхідних для побудови дерева.
При роботі з двійковим деревом можливі такі основні завдання:
1) створення елемента, вузла дерева,
2) включення його в дерево за алгоритмом довічного пошуку,
3) знаходження в дереві вузла з заданим значенням ключової ознаки,
4) визначення максимальної глибини дерева,
5) визначення кількості вузлів дерева,
6) визначення кількості листя дерева,
7) ряд інших завдань.
Наведемо приклади процедур, що реалізують основні завдання роботи з бінарним деревом.
ПРИМІТКА: елемент з дублюючим ключовою ознакою в дерево не включається.
Даний алгоритм руху по дереву може бути покладено в основу завдання визначення максимального рівня (глибини) двійкового дерева, визначення, чи є в дереві елемент із заданим значенням ключової ознаки і т.д. тобто таких завдань, вирішення яких грунтується на алгоритмі довічного пошуку по дереву.
Однак не всі завдання можуть бути вирішені із застосуванням довічного пошуку, наприклад, підрахунок загального числа вузлів дерева. Для цього потрібно алгоритм, що дозволяє одноразово відвідувати кожен вузол дерева.
При відвідуванні будь-якого вузла можливо одноразове виконання наступних трьох дій:
1) опрацювати вузол (конкретний набір дій при цьому не важливий). Позначимо цю дію через О (обробка);
2) перейти по лівій посиланням (позначення - Л);
3) перейти по правій посиланням (позначення - П).
Можна організувати обхід вузлів двійкового дерева, одноразово виконуючи над кожним вузлом цю послідовність дій. Дії можуть бути скомбіновані в довільному порядку, але він повинен бути постійним у конкретному завданні обходу дерева.
На прикладі дерева на рис. 10 проілюструємо варіанти обходу дерева.
1) Обхід виду ОЛП. Такий обхід називається «в прямому порядку», «в глибину». Він дасть наступний порядок відвідування вузлів:
20, 10, 8, 15, 17, 35, 27, 24, 30
2) Обхід виду ЛОП. Він називається «симетричною» і дасть наступний порядок відвідування вузлів:
8, 10, 15, 17, 20, 24, 27, 30, 35
3) Обхід виду ЛПО. Він називається «в зворотному порядку» і дасть наступний порядок відвідування вузлів:
8, 17, 15, 10, 24, 30, 27, 35, 20
Якщо розглядати завдання, що вимагають суцільного обходу дерева, то для частини з них порядок обходу, в цілому, не важливий, наприклад, підрахунок числа вузлів дерева, числа листя / не листя, елементів, що володіють заданою інформацією і т.д. Однак таке завдання, як знищення бінарного дерева зі звільненням пам'яті, вимагає використання тільки обходу «в зворотному порядку».
Розглянемо засоби, за допомогою яких можна забезпечити варіанти обходу дерева.
При роботі з бінарним деревом з точки зору програмування оптимальним варіантом побудови програми є використання рекурсії. Базисний варіант рекурсивної процедури обходу бінарного дерева дуже простий.
Для практичного опрацювання дії механізму рекурсії при реалізації варіантів обходу дерева можна скористатися вже побудованим деревом з рис.10.
Приклад використання рекурсивної процедури при вирішенні завдання підрахунку листя двійкового дерева.
На закінчення слід сказати про те, що рекурсивний обхід дерева застосуємо в більшості завдань, проте необхідно все ж розрізняти варіанти ефективного застосування довічного пошуку і суцільного обходу.