Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     

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

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

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

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

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

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

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

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

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

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.