Студопедия

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

КАТЕГОРИИ:

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






Обхід дерев






Означення 3.1. Об'єкт називають рекурсивним, якщо він містить сам себе чи його означено за допомогою самого себе.

Приклад 3.1. Означення повного бінарного дерева через рекурсію:

а) о (ізольована вершина) – повне бінарне дерево;

б) якщо А та В – повні бінарні дерева, то конструкція, зображена на рис. 3.1, – повне бінарне дерево.

Рис. 3.1 Схема рекурсії

 

Приклад 3.2. Рекурсивне означення функції п! для невід'ємних цілих чисел має такий вигляд:

а) 0! =1;

б) якщо п > 0, то п! =п(п- 1)!.

Рис. 3.2 Обхід m -арного дерева  
Важливість рекурсії пов'язана з тим, що вона дає змогу означити нескінченну множину об'єктів за допомогою скінченного висловлювання. Проте найдоцільніше використовувати рекурсивні алгоритми тоді, коли розв’язувану задачу, обчислювану функцію чи оброблювані дані задано за допомогою рекурсії. Чимало задач можна моделювати з використанням кореневих дерев. Поширене таке загальне формулювання задачі: виконати задану операцію D з кожною вершиною дерева. Тут D — параметр загальнішої задачі відвідування всіх вершин, або так званого обходу дерева. Розглядаючи розв'язування цієї задачі як єдиний послідовний процес відвідування вершин дерева в певному порядку, можна вважати їх розміщеними одна за одною. Опис багатьох алгоритмів істотно спрощується, якщо можна говорити про наступну вершину дерева, маючи на увазі якесь упорядкування. Є три принципи впорядкування вершин, які природно випливають зі структури дерева. Як і саму деревоподібну структуру, їх зручно формулювати за допомогою рекурсії.

Рис. 3.3 Обхід m -арного дерева  
Звертаючись до бінарного дерева, де R – корінь, А та В – ліве та праве піддерева (рис. 3.1), можна означити такі впорядкування:

1. Обхід у прямому порядку (preorder)

або зверху вниз: R, А, В:

a) відвідати корінь;

b) відвідати ліве піддерево;

c)

Рис. 3.3 Обхід m -арного дерева  
відвідати праве піддерево.

В такому порядку обходу кожна вершина відвідується до того, як будуть відвідані її діти (рис.3.2).

2. Обхід у внутрішньому порядку (inorder) або зліва направо: А, R, В:

a) відвідати ліве піддерево;

b) відвідати корінь;

c)

Рис.3.5 Бінарне дерево
відвідати праве піддерево.

Кожна вершина відвідується між відвіданням лівої та правої дитини. Такий порядок особливо часто застосовується в бінарних деревах пошуку, тому що дає можливість обходу вершин у порядку збільшення їхніх порядкових номерів (рис.3.3).

3. Обхід у зворотному порядку (postorder) або знизу вверх: А, В, R:

a) відвідати ліве піддерево;

b) відвідати праве піддерево;

c) відвідати корінь.

Кожна вершина відвідується лише після того, як будуть відвідані її діти (рис.3.4).

Приклад 3.3. Записати прямий порядок обходу дерева (рис.3.5).

Крок 1: Корінь – А;

Крок 2: Лівий син А – В;

Крок 3: Лівий син В – С;

Крок 4: Повертаємось на крок 2 і вибираємо

наступного сина А – D;

Крок 5: Лівий син D – E;

Крок 6: Правий син D – F.

Прямий порядок: A B C D E F.

Приклад 3.4. Обходи бінарних дерев (рис.3.6-3.7):

Прямий порядок: 2, 7, 2, 6, 5, 11, 5, 9, 4;   Зворотний порядок: 2, 5, 11, 6, 7, 4, 9, 5, 2;   Внутрішній порядок: 2, 7, 5, 6, 11, 2, 5, 4, 9.

Рис.3.6 Бінарне дерево

Прямий порядок:

a b d e h o c f m p q;

 

Зворотний порядок:

d h o e b f p q m c a;

Внутрішній порядок:

d b h e o a f c pm q.

 

Рис.3.7 Бінарне дерево

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал