Обхід дерева

Алгоритми пошуку графами та деревами
α–β A* B* Бахромовий Беллмана — Форда Британського музею Борувки В глибину В ширину Гілок та меж D* Двоспрямований Дейкстри Джонсона Едмондса З вертанням зворотний перехід З ітеративним заглибленням З обмеженням глибини IDA* Крускала Лексикографічний у ширину На стрибкових точках Перший-найліпший Прима Променевий SMA* Сходження на вершину Флойда — Воршелла
Переліки
Алгоритми на графах Алгоритми пошуку Список алгоритмів на графах
Пов'язані теми
Динамічне програмування Пошукова гра Пошук по графу Обхід дерева

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

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

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

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

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

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

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

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

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

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

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

Обхід дерева вглиб:

прямий (червоний): F, B, A, D, C, E, G, I, H;

зворотній (зелений): A, C, E, D, B, H, I, G, F;

серединний (жовтий): A, B, C, D, E, F, G, H, I.

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

• прямий порядок (NLR) (англ. preorder) наступної послідовності:
  1. відвідати корінь
  2. відвідати ліве піддерево
  3. відвідати праве піддерево

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

• зворотний порядок (LRN) (англ. postorder) наступної послідовності:
  1. відвідати ліве піддерево
  2. відвідати праве піддерево
  3. відвідати корінь

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

• серединний (центрований) порядок (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

Див. також

• Дерево (структура даних)
• Модель вкладених множин
• Список алгоритмів
• Пошук в глибину
• Пошук у ширину

Література

• Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Вступ до алгоритмів (вид. 3). К.І.С. ISBN 978-617-684-239-2. {{cite book}}: Cite має пустий невідомий параметр: |1= (довідка)