Основні визначення

Дерево - це граф, що характеризується наступними властивостями:

- існує єдиний елемент (вузол, вершина), на який не посилається ніякий інший елемент - який називається коренем;

- починаючи з кореня і переміщаючись по визначеній послідовності покажчиків, що зберігаються в елементах, можна здійснити доступ до будь-якого елемента структури;

- на кожен елемент, крім кореня, мається єдине посилання, тобто кожен елемент адресується єдиним покажчиком.

Назва "дерево" пішло з логічної еквівалентності деревоподібної структури в теорії графів абстрактному дереву. Лінії зв'язку міжду парою вузлів дерева називається віткою. Ті вузли, що не посилаються на інші вузли дерева, називаються листами (або термінальними вершинами). Вузол, що не є листом або коренем, вважається проміжним або вузлом розгалуження (нетермінальною або внутрішньою вершиною).

Число ребер орієнтованого графа, що виходять з деякої початкової вершини V, називається напівступенем виходу цієї вершини. Число ребер, для яких вершина V є кінцевою, називається напівступенем заходу вершини V, а сума напівступенів виходу і заходу вершини V називається повним ступенем цієї вершини. Орієнтоване дерево - це такий ациклический орграф (орієнтований граф), у якого одна вершина, називана коренем, має напівступінь заходу, рівний 0, а інші - напівступені заходу рівні 1. Орієнтоване дерево повинне мати принаймні одну вершину. Ізольована вершина також являє собою орієнтоване дерево. Сукупність дерев називається лісом. На рис 7.14 подано приклад дерева, на рис. 7.15 - лісу.

Рис. 7.14. Дерево Рис. 7.15. Ліс

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

Вершина орієнтованого дерева, напівступінь виходу якої дорівнює нулю, називається кінцевою (висячою) вершиною або листом; всі інші вершини дерева називають вершинами розгалуження. Довжина шляху від кореня до деякої вершини називається рівнем (номером ярусу) цієї вершини. Рівень кореня орієнтованого дерева дорівнює нулеві, а рівень будь-якої іншої вершини дорівнює відстані (тобто модулеві різниці номерів рівнів вершин) між цією вершиною і коренем. Орієнтоване дерево є ациклическим графом, усі шляхи в ньому елементарні.

У багатьох додатках відносний порядок проходження вершин на кожнім окремому ярусі має значення. При представленні дерева в ЕОМ такий порядок вводиться автоматично, навіть якщо він сам по собі довільний. Порядок проходження вершин на деякому ярусі можна легко ввести, позначаючи одну вершину як першу, іншу - як другу і т.д. Замість впорядкування вершин можна задавати порядок на ребрах. Якщо в орієнтованому дереві на кожнім ярусі заданий порядок проходження вершин, то таке дерево називається упорядкованим деревом.

Уведемо ще деякі поняття, зв'язані з деревами. Вузол X називається предком (або батьком), а вузли Y і Z називаються спадкоємцями (або синами) їх відповідно між собою називають братами; причому лівий – молодшим. Число піддерев даної вершини називається ступенем цієї вершини. У прикладі рис. 7.16 вершина X має 2 піддерева, отже ступінь вершини X дорівнює 2.

Рис.7.16. Дерево

Якщо з дерева забрати корінь і ребра, що з'єднують корінь з вершинами першого ярусу, то вийде деяка кількість незв'язаних дерев - ліс. І навпроти, ліс може бути перетворений в дерево (алгоритм перетворення дано нижче).