Обхід дерева

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Обхід бінарного дерева передбачає відвідування усіх вершин бінарного дерева, при цьому кожна з вершин відвідується тільки один раз.

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

  • прямий порядок (англ. preorder) наступної послідовності:
    1. відвідати корінь
    2. відвідати ліве піддерево
    3. відвідати праве піддерево
    Тобто, в такому порядку обходу кожна вершина відвідується до того, як будуть відвідані її діти.
  • зворотний порядок (англ. postorder) наступної послідовності:
    1. відвідати ліве піддерево
    2. відвідати праве піддерево
    3. відвідати корінь
    Тобто, в такому порядку кожна вершина відвідується лише після того, як будуть відвідані її діти.
  • центрований (центральний) порядок (англ. 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

Див. також[ред.ред. код]