Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Обхід дерев
|
|
Означення 3.1. Об'єкт називають рекурсивним, якщо він містить сам себе чи його означено за допомогою самого себе.
Приклад 3.1. Означення повного бінарного дерева через рекурсію:
а) о (ізольована вершина) – повне бінарне дерево;
б) якщо А та В – повні бінарні дерева, то конструкція, зображена на рис. 3.1, – повне бінарне дерево.
Рис. 3.1 Схема рекурсії
Приклад 3.2. Рекурсивне означення функції п! для невід'ємних цілих чисел має такий вигляд:
а) 0! =1;
б) якщо п > 0, то п! =п(п- 1)!.
Рис. 3.2 Обхід m -арного дерева
|
 Рис. 3.3 Обхід m -арного дерева
|
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 Бінарне дерево