Тип даних “Дерево”. Основні означення. Обхід дерева в симетричномупорядку

Дерево (tree) – це сукупність елементів, які називаються вузлами та відношень між цими елементами, що утворюють ієрархічну структуру дерева.Початковий вузол дерева називається його коренем (root).

Вершина ступеню нуль має назву кінцевої(terminal) або листа (leaf).

Некінцева вершина також має назву вершини розгалуження (branch node).

Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками.Якщо вершина x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називаєтьсябатьком (parent) до y, а y — дитиною(child) x.Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings).Вершини, що мають дітей, називаються внутрішніми (internal).

Глибиною вершини x називається довжина шляху від кореня до цієї вершини.

Максимальна глибина вершин дерева називається висотою.

Лісом (forest) називають множину дерев, які не перетинаються.

при симетричному обході вузлів дерева T, спочатку відвідуються в симетричному порядку всі вузли під дерева T₁, далі корінь n, а потім послідовно в симетричному порядку всі вузли під дерев T₂,…,T_k.

Тип даних “Дерево”. Основні означення. Обхід дерева в зворотному орядку

Дерево (tree) – це сукупність елементів, які називаються вузлами та відношень між цими елементами, що утворюють ієрархічну структуру дерева.Початковий вузол дерева називається його коренем (root).

Вершина ступеню нуль має назву кінцевої(terminal) або листа (leaf).

Некінцева вершина також має назву вершини розгалуження (branch node).

Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками.Якщо вершина x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називаєтьсябатьком (parent) до y, а y — дитиною(child) x.Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings).Вершини, що мають дітей, називаються внутрішніми (internal).

Глибиною вершини x називається довжина шляху від кореня до цієї вершини.

Максимальна глибина вершин дерева називається висотою.

Лісом (forest) називають множину дерев, які не перетинаються.

при обході в зворотному порядку, спочатку відвідуються всі вузли під дерева T₁, потім послідовно відвідуються всі вузли під дерев T₂,…,T_k, також в зворотному порядку, останнім відвідується корінь n.

 

Порядок вузлів в дереві. Реалізація алгоритмів обходу дерев

Як правило, сини вузла впорядковуються зліва-на-право І такі дерева називаються впорядкованими.Якщо порядок синів ігнорується, то такі дерева називаються невпорядкованими Дерева з мітками. Дерева-вирази

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

Дерево для його кожному із його вузлів поставлено у відповідність певну мітку(label), називається поміченим деревом (labeled tree).

Мітка вузла – це не ім’я вузла, а значення яке в ньому міститься.

Оператори для роботи із АТД “Древо”

PARENT (n, T) – функція повертає предка вузла n в дереві T.

LEFTMOST_CHILD (n, T) – функція повертає самого лівого сина вузла n в дереві T.

RIGHT_SIBLING (n, T) – функція повертає правого брата вузла n в дереві T 

LABEL (n, T) – повертає мітку вузла n дерева T

CREATE (v, T₁, T₂,…,T_i) – створює новий корінь r з міткою v і кожне із під дерев T стає його сином.

ROOT(T) – повертає вузол, що є коренем дерева.

MAKENULL(T) – оператор робить дерево T порожнім.

Реалізація АТД “Дерево” при доомозі массиву

Одним з найпростіших представлень абстрактного типу даних TREE, є лінійний масив A, де кожен елемент A[i]  є вузлом дерева і містить вказівник чи курсор на свого батька.Корінь дерева відрізняється від інших вузлів тим, що має нульовий вказівник, або ж вказує сам на себе.Таке представлення використовує ту особливість дерева, що кожен з його вузлів має лише одного батька, тому батька будь-якого вузла можна знайти за фіксований час.

Для реалізації оператора LABEL (помічені дерева) можна скористатися ще одним масивом L, в якому елемент L[i] буде містити мітку i-го вузла дерева, або ж описати елементи масиву Aяк структуру, що складатиметься із двох полів вказівника на батька та мітки вузла.