Обхід дерева

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

Види обходів дерев

На відміну від пов'язаних списків, одновимірних масивів та інших лінійних структур даних, для яких існує канонічний обхід за допомогою лінійного порядку, дерева можна обходити у різні способи. Їх можна обходити вглиб або вшир. Існує три найпоширеніші способи їх проходження вглиб: прямий (pre-order), зворотній (post-order) та серединний (in-order)^[1]. Окрім цих основних обходів, можливі різні складніші або гібридні схеми, такі як глибокі пошукові запити, подібні до ітеративного поглиблення глибинного пошуку. Останній, як і пошук вшир, також може бути використаний для обходу нескінченних дерев, див. нижче.

Структури даних для обходу дерева

Обхід дерева передбачає ітераційний перегляд усіх вузлів. Оскільки з довільного вузла можна потрапити до більше ніж одного можливого наступного вузла (оскільки, це не лінійна структура даних), то, припускаючи послідовне обчислення (не паралельне), деякі вузли повинні бути відкладені, тобто, збережені якимось чином для подальшого відвідування. Це часто робиться з використанням таких структур як стек (LIFO) або черга (FIFO). Оскільки дерево є структурою даних, яка визначена рекурсивно, то обхід може бути визначений за допомогою рекурсії або, що є більш витонченим, корекурсії, у природній і зрозумілий спосіб; при використанні рекурсії відкладені вузли неявно зберігаються у стеці викликів.

Пошук вглиб легко реалізується через стек, в тому числі рекурсивно (через стек викликів), тоді як пошук вшир легко реалізується через чергу, в тому числі корекурсію.

Пошук вглиб у двійковому дереві

Докладніше: Пошук у глибину

Такий пошук називаються пошуком вглиб (англ. depth-first search, DFS), оскільки по дереву пошуку просуваються максимально глибоко для кожного нащадка, перед тим, як перейти до наступного брата. Для двійкового дерева вони визначаються як операції доступу на кожному вузлі, починаючи з поточного вузла, алгоритм якого такий^[2]^[3]:

Загальний рекурсивний підхід для обходу двійкового дерева такий:

Спустіться на один рівень до рекурсивного аргументу `N`. Якщо `N` існує (тобто, не є порожнім), то виконуються наступні три операції у певному порядку:
(L)	Рекурсивно обійти для `N` ліве піддерево.
(R)	Рекурсивно обійти для `N` праве піддерево.
(N)	Обробити поточний вузол `N`.
Повернутися, піднявшись на один рівень і прибути до батьківського вузла `N`.

У прикладах здебільшого (L) виконується перед (R). Але можливе виконання (R) перед (L), див. (RNL).

Існують три види таких обходів, кожний з яких визначається рекурсивно:

прямий порядок (NLR) (англ. preorder) наступної послідовності:
1. відвідати корінь
2. відвідати ліве піддерево
3. відвідати праве піддерево
Тобто, в такому порядку обходу кожна вершина відвідується до того, як будуть відвідані її діти.
зворотний порядок (LRN) (англ. postorder) наступної послідовності:
1. відвідати ліве піддерево
2. відвідати праве піддерево
3. відвідати корінь
Тобто, в такому порядку кожна вершина відвідується лише після того, як будуть відвідані її діти.
серединний^[4] (центрований) порядок (LNR) (англ. inorder) наступної послідовності:
1. відвідати ліве піддерево
2. відвідати корінь
3. відвідати праве піддерево
В такому порядку кожна вершина відвідується між відвіданням лівої та правої дитини. Такий порядок особливо часто застосовується в бінарних деревах пошуку, тому що дає можливість обходу вершин у порядку збільшення їхніх порядкових номерів.

Приклад

Для цього бінарного дерева,

Прямий порядок: 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

Див. також

Примітки

↑ Lecture 8, Tree Traversal. Архів оригіналу за 5 серпня 2018. Процитовано 2 травня 2015.
↑ Архівована копія (PDF). Архів оригіналу (PDF) за 28 серпня 2017. Процитовано 25 жовтня 2020.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
↑ Preorder Traversal Algorithm. Архів оригіналу за 11 квітня 2019. Процитовано 2 травня 2015.
↑ Вступ до алгоритмів, 2019, с. 302.

Література

Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.

[holtenotes-1] Lecture 8, Tree Traversal. Архів оригіналу за 5 серпня 2018. Процитовано 2 травня 2015.

[2] Архівована копія (PDF). Архів оригіналу (PDF) за 28 серпня 2017. Процитовано 25 жовтня 2020.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)

[3] Preorder Traversal Algorithm. Архів оригіналу за 11 квітня 2019. Процитовано 2 травня 2015.

[FOOTNOTEВступ_до_алгоритмів2019302-4] Вступ до алгоритмів, 2019, с. 302.

[1]

[2]

[3]

[4]