Дерево як структура даних.

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

• Існує єдиний елемент (вузол або вершина), на який не посилається ніякий інший елемент, – він називається коренем.

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

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

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

Алгоритм перетворення дерева в бінарне.

Правило побудови бінарного дерева з будь-якого дерева:

1. В кожному вузлі залишити тільки гілку до старшого сина;

2. З’єднати горизонтальними ребрами всіх братів одного батька;

3. Таким чином перебудувати дерево за правилом:

лівий син – вершина, розташована під даною;

правий син – вершина, розташована праворуч від даної (тобто на одному ярусі з нею).

4. Розвернути дерево так, щоб усі вертикальні гілки відображали лівих синів, а горизонтальні – правих.

У результаті перетворення будь-якого дерева, в бінарне, виходить дерево у вигляді лівого піддерева, підвішеного до кореня.

У процесі перетворення правий покажчик кожного вузла бінарного дерева буде вказувати на сусіда по рівню. Якщо такого немає, то правий покажчик – NULL. Лівий покажчик буде вказувати на вершину наступного рівня. Якщо такої немає, то покажчик встановлюється на NULL.

Представлення дерев у пам’яті.

Дерева можна представляти за допомогою зв’язних списків і масивів (або послідовних списків).

Частіше всього використовується зв’язне представлення дерев, так як воно дуже сильно нагадує логічне. Зв’язне зберігання полягає в тому, що задається зв’язок від батька до синів. В бінарному дереві є два покажчики, тому зручно вузол представити у вигляді структури в якій left – покажчик на ліве піддерево, right – покажчик на праве піддерево, inf – містить інформацію, яка зв’язана з вершиною і має наперед визначений тип – data.

Операції над деревами.

Над деревами визначені наступні основні операції:

1) Пошук вузла із заданим ключем.

2) Додавання нового вузла.

3) Видалення вузла (піддерева).

4) Обхід дерева в певному порядку:

Низхідний обхід;

Змішаний обхід;

Висхідний обхід.