Порядок та властивості обходу дерева.

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

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

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

1. відвідати корінь;

2. відвідати ліве піддерево;

3. відвідати праве піддерево.

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

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

1. відвідати ліве піддерево;

2. відвідати праве піддерево;

3. відвідати корінь.

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

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

1. відвідати ліве піддерево;

2. відвідати корінь;

3. відвідати праве піддерево.

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

<== попередня сторінка	\|	наступна сторінка ==>
Перехід від дерева до бінарного дерева	\|	Приклад

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.