Обхід дерева

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

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

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

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

Спустіться на один рівень до рекурсивного аргументу 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. відвідати корінь

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

• серединний[4] (центрований) порядок (LNR) (англ. inorder) наступної послідовності:
  1. відвідати ліве піддерево
  2. відвідати корінь
  3. відвідати праве піддерево

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