28. Навести визначення та способи зображення дерев.

Дерево (англ. tree) — одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:

існує один відокремлений вузол — корінь (root) дерева

інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1…Tm і кожна з цих множин в свою чергу є деревом. Дерева T1…Tm мають назву піддерев (subtrees) даного кореня.

Це визначення є рекурсивним. Дерево визначається через само себе.

Графічно дерево можна зображувати і деякими іншими способами. Деякі з них представлені на рис. 4. Згідно з визначенням дерево є системою вкладених великих множин, де ці множини або не перетинаються або повністю містяться одна в одній. Такі множини можна зображувати як області на площині (рис. 4а). На рис. 4б представлення дерева у вигляді вкладених дужок . Рис. 4б також можна розглядати як схему деякої формули алгебри, що містить вкладені дужки. Рис. 4в дає ще один популярний спосіб зображення деревовидної структури у вигляді списку з уступами.

Рис. 4. Інші способи зображення деревовидних структур : (а) вкладені множини; (б) вкладені дужки; (в) список з уступами .

29. Навести опис впорядкованого та бінарного дерева.

Впорядковані дерева

Дерево вважається орієнтованим, якщо воно задовольняє наступним вимогам:

– у дерева існує один корінь;

– кожен вузол дерева може бути досягнутий із кореня.

Дерево вважається впорядкованим, якщо порядок його елементів є фіксованим.

Наприклад, структура папок і файлів є орієнтованим впорядкованим деревом.

Бінарні дерева

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

В дереві пошуку можна знайти елемент за ключем, рухаючись від кореня і переходячи на ліве або праве піддерево в залежності від значення ключа в кожному вузлі. Такий спосіб набагато ефективніший пошуку по списку, так як час виконання операції пошуку визначається висотою дерева. Дерево є рекурсивною структурою даних, так як кожне піддерево є також деревом. Дії з такими структурами даних простіше всього описувати за допомогою рекурсивних алгоритмів.

Бінарне дерево

30.Навести алгоритм прямого порядку (preorder) обходу дерева.

-відвідати корінь

-відвідати ліве піддерево

-відвідати праве піддерево

Procedure PreoderTraversal (<apr.>);

Begin

DoSomething (<apr.>); //проходження корення

If <існує ліве дерево> then

PreoderTraversal (<apr.>); //прох. Правого дерева

If <існує праве дерево> then

PreoderTraversal (<apr.>);

End.