3. Дерева

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

1) у графі знайдеться одна вершина, в яку не входить жодне ребро. Ця вершина називається коренем дерева;

2) у будь-яку вершину, крім кореня, входить тільки одне ребро;

3) з кореня можна знайти унікальний шлях до кожної вершини дерева.

Орієнтований граф, що складається з кількох дерев, називається лісом.

Нехай F=(V,E) – граф, що є лісом. Якщо (v, u)  Е, тоді v називають „батьком” вузла u, а u – "сином" вузла v. Якщо є шлях з v в u, тоді v називають „предком2 вузла u, а u – „нащадком” вузла v. Вузол v і його нащадки разом утворюють піддерево лісу F, і вузол v називають коренем цього піддерева.

Глибина вузла v в дереві – це довжина шляху із кореня в v. Висота вузла v в дереві — це довжина найдовшого шляху із v в деякий вузол. Висотою дерева називають висоту його кореня. Рівень вузла v в дереві дорівнює різ­ниці висоти дерева і глибини вузла v.

Впорядкованим деревом називають те, в якому множина синів кожного вузла впорядкована. При зображенні впорядкованих дерев вважають, що множина синів кожного вузла впорядкована зліва направо.

Двійковим (бінарним) деревом називається таке впорядковане дерево, для якого виконуються умови:

1) кожний син довільного вузла ідентифікується або як лівий син, або як правий син;

2) кожний вузол має не більше одного лівого сина і не більше одного правого сина.

Піддерево Т_l, коренем якого є лівий син вузла v (якщо таке існує), нази­вається лівим піддеревом вузла v. Аналогічно визначається праве піддерево вузла Т_r. Відмітимо, що всі вузли Т_l знаходяться ліворуч усіх вузлів у Т_r.

Максимальне число вузлів на рівні і бінарного дерева дорівнює 2ⁱ -1. Також максимальне число вузлів у бінарному дереві глибини k дорівнює 2^k–1, де k>0.

Для багатьох задач, пов'язаних з використанням дерев, виникає потре­ба переглянути всі вузли дерева в певному порядку. Розглянемо основні принципи проходження дерев на прикладі бінарних дерев. Алгоритми обходу мають рекурсивний характер:

I) пряме проходження:

1) відвідати корінь;

2) відвідати згідно з прямим проходженням ліве піддерево кореня;

3) відвідати згідно з прямим проходженням праве піддерево кореня;

II) обернене проходження:

1) відвідати згідно з оберненим проходженням ліве піддерево кореня;

2) відвідати корінь;

3) відвідати згідно з оберненим проходженням праве піддерево кореня;

III) кінцеве проходження:

1) відвідати згідно з кінцевим проходженням праве піддерево кореня;

2) відвідати згідно з кінцевим проходженням ліве піддерево кореня;

3) відвідати корінь.

Візьмемо до розгляду дерево, зображене на рис. 6.

Рис. 6. Бінарне дерево

Тоді перегляд вузлів у прямому напрямку матиме таку послідовність: 1, 2, 4, 5, 7, 8, 10, 3, 6, 9, 11, 12; в оберненому проходженні: 4, 2, 7, 5, 10, 8, 1, 3, 11, 9, 12, 6; в кінцевому порядку: 12, 11, 9, 6, 3, 10, 8, 7, 5, 4, 2, 1.

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