Дерево - це нелінійна структура даних. використовувана при поданні ієрархічних зв'язків, що мають відношення «один до багатьох».
Термінологія (взята з ботаніки і генеалогії)
Дерево це сукупність елементів, називаемихузламіілівершінамі, і відносин ( «батьківських») між ними, що утворюють ієрархічну структуру вузлів.
Відносини між вузлами дерева (з генеалогії):
верхній вузол (вершина) називається батьком (предком).
нижній - нащадком (сином або дочірньої вершиною).
Визначення вузлів - з ботаніки.
Сама верхня вершина - корінь. а самі нижні вершини - листя. Вершини, які не мають нащадків, - термінальні (через відносини) або листя (через визначення). Нетермінальні вершини - внутрішні.
брати Вузол - син (нащадок)
вершина (лист) лист
Дерева визначаються рекурсивно. т. е. дерево з базовим типом Т - це
або порожня структура (пусте дерево, одінкорень);
або вузол типу Т з кінцевим числом деревовидних структур цього ж типу Т. називаються піддерев.
Т.ч. - дерево без гілок з однією вершиною - це пусте або нульове дерево.
Корінь дерева лежить на нульовому рівні.
Максимальний рівень будь-якої вершини дерева -глибина (від кореня до вузла) або висота (від вузла до максимально віддаленого листа). Звідси макс. рівень кореня = 0.
Максимальний рівень всіх вершин називається глибиною дерева.
Число безпосередніх нащадків у вершини (вузла) дерева називається ступенем вершини (вузла).
Максимальний ступінь всіх вершин є ступенем дерева.
Число гілок від кореня до вершини є довжина шляху до цієї вершини.
Т. о. корінь має довжину шляху, що дорівнює 0, довжина шляху його прямих (т. е. пов'язаних з ним однією гілкою) нащадків дорівнює 1 і т.д. Вершина на рівні i має довжину шляху i.
Довжина внутрішнього шляху дерева - це сума довжин шляхів для кожної його вершини.
Довжина зовнішнього шляху дерева - це сума довжин шляхів всіх спеціальних вершин, які доповнюють дерево так, щоб мірі всіх вершин були рівні ступеня дерева:
довжина зовн. шляху дерева =
Глибина дерева = 3.
Максимальний ступінь дерева = 3.
Довжина внутрішнього шляху дерева дорівнює 36.
Довжина зовнішнього шляху дерева дорівнює 120.
Подання деревовидної структури
а
б) Дужковий (у виразах)
Подання дерев в пам'яті
У пам'яті дерева можна представити у вигляді:
Подання цього дерева:
а) у вигляді курсорів на батьків: