Обхід дерева
Матеріал з Вікіпедії — вільної енциклопедії.
ОБХІД БІНАРНОГО ДЕРЕВА передбачає відвідування усіх вершин бінарного дерева, при цьому кожна з вершин відвідується тільки один раз.
Існують три види таких обходів, кожний яких визначається рекурсивно:
- прямий порядок (preorder) наступної послідовності:
- відвідати корінь
- відвідати ліве піддерево
- відвідати праве піддерево
Тобто, в такому порядку обходу кожна вершина відвідується до того, як будуть відвідані її діти.
- зворотний порядок (postorder) наступної послідовності:
- відвідати ліве піддерево
- відвідати праве піддерево
- відвідати корінь
Тобто, в такому порядку кожна вершина відвідується лише після того, як будуть відвідані її діти.
- центрований (центральний) порядок (inorder) наступної послідовності:
- відвідати ліве піддерево
- відвідати корінь
- відвідати праве піддерево
В такому порядку кожна вершина відвідується між відвіданням лівої та правої дитини. Такий порядок особливо часто застосовується в бінарних деревах пошуку, тому що дає можливість обходу вершин у порядку збільшення їхніх порядкових номерів.
[ред.] Приклад
![]() |
Для цього бінарного дерева,
|


