ОБХІД БІНАРНОГО ДЕРЕВА передбачає відвідування усіх вершин бінарного дерева, при цьому кожна з вершин відвідується тільки один раз.

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

• прямий порядок (preorder) наступної послідовності:

1. відвідати корень
2. відвідати ліве піддерево
3. відвідати праве піддерево

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

• зворотний порядок (postorder) наступної послідовності:

1. відвідати ліве піддерево
2. відвідати праве піддерево
3. відвідати корень

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

• центрований (центральний) порядок (inorder) наступної послідовності:

1. відвідати ліве піддерево
2. відвідати корень
3. відвідати праве піддерево

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

Приклад

---

Binary_tree.png

Для цього бінарного дерева, Прямий порядок: 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

Програмування

Tree traversal | Przechodzenie drzewa