Структури даних дерева

1.1. Визначення структури: дерево

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

а) є один спеціально позначений елемент, званий коренем даного дерева;

б) інші елементи містяться в m> 0 попарно непересічних безлічі T1. Tm. кожне з яких в свою чергу є деревом; дерева T1. Tm називаються піддерев даного кореня (ріс.1.а).

Рис.1. види дерев

Якщо має значення відносний порядок піддерев T1. Tm, то кажуть, що дерево є впорядкованим. Число піддерев даного вузла називається ступенем цього вузла. Вузол з нульовим ступенем називається кінцевим вузлом (або листом або термінальним вузлом), всі інші елементи - внутрішні вузли (нетермінальні). Максимальний ступінь всіх вершин називається ступенем дерева. Корінь дерева має рівень рівний 0. Решта вершини мають рівень на одиницю більше рівня безпосереднього предка. Максимальний рівень будь-якої з вершин називається глибиною або висотою дерева. Мінімальна висота при заданому числі вершин досягається, якщо на всіх рівнях, крім останнього, поміщається максимально можливе число вершин. Максимальне число вершин в дереві заввишки h досягається в тому випадку, якщо з кожної вершини, за винятком рівня h, виходять d піддерев, де d-ступінь дерева: на 0-му рівні 1 вершина, на 1-му - d нащадків, на 2 -м - d 2 нащадків, на 3-му рівні d 3 нащадків і т.д.

Найбільш широко використовуються виконавчі (бінарні) дерева (ріс.1.б). Бінарне дерево це кінцеве безліч елементів, яке або порожня, або складається з кореня і з двох непересічних бінарних дерев, званих лівим і правим піддеревами даного кореня. Таким чином, кожен елемент бінарного дерева має 0, 1 або 2 поддерева. Бінарне дерево - впорядковане дерево, так як в ньому розрізняють ліве і праве піддерева.

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

Структуру даних - дерево можна уявити як в статичній, так і в динамічної пам'яті.

У статичної пам'яті дерево можна уявити масивом, для якого визначено поняття порожнього елемента:

Рис.2. двоичное дерево представлене у вигляді масиву

Вершини двійкового дерева розташовуються в масиві таким чином (див. Рис.2.): Якщо k - індекс вершини дерева, то її нащадки знаходяться в елементах масиву з індексами 2k + 1 і 2 (k + 1); корінь дерева знаходиться в елементі з індексом 0 (при індексації в масиві від 1 до N індекси нащадків k-ї вершини: 2k і 2k + 1, корінь має індекс 1).

У динамічної пам'яті дерево представляється ієрархічним списком. Задати елемент двійкового дерева можна як елемент списку з трьома полями: два довідкових поля, що містять покажчики на його ліве (L) і праве (R) піддерева, і інформаційне поле (E):

Визначення типу елемента бінарного динамічного дерева:

btree * left, * right;>

Тут type - тип інформаційного поля (якщо інформаційне поле має складну структуру, то type може бути типом - покажчик на об'єкт, що містить значення елемента дерева).

Щоб визначити дерево як єдину структуру, треба задати покажчик на корінь дерева:

Рис.3. Двійкове динамічне дерево

На рис.3 представлено двоичное динамічне дерево d відповідно до визначення типу елемента, зробленим вище. Елементи дерева зі ступенем 0 і 1 мають два або одне Посилальне поле зі значенням рівним порожньому вказівником (NULL).

Обробляючи дерево, доводиться переглядати його елементи - ця операція називається обхід дерева (або проходження дерева).