Дерева

Для дерев характерно:

• Складаються з вузлів того самого типу.

• Існує один виділений вузол, а саме корінь (root) даного дерева, інші вузли розподілені між М (М≥0) непересічними безлічами, кожне з який у свою чергу теж є деревом, і називається піддерево.

• Вузли дерева за умови виключення кореня утворять ліс.

• Зв'язок між вузлами і доступ до дерев здійснюється за допомогою типізованих вказівників.

• Кількість вузлів дерева за раніше не задається. Воно може змінюватися в процесі виконання програми. Розмір одного вузла дерева не може перевищувати 64 Кбайт.

• При описі типу - дерево, використовується рекурсія.

• Доступ до вузлів дерева послідовний, рух до вузла йде від кореня дерева.

Відома така термінологія деревоподібних структур: Кожен вузол називається батьком (parent) коренів його піддерев, а самі корені називаються братами-сестрами (siblings), а також нащадками (children) свого батька.

Існує досить багато типів дерев. Найбільше часто використовують бінарні дерева.

Бінарним деревом - називають дерево, кожен вузол якого має не більш двох нащадків і одного батька.

Бінарні дерева часто застосовують для сортування й організації швидкого пошуку інформації.
Існує досить багато алгоритмів роботи з деревоподібними структурами, у яких часто зустрічається поняття обходу (traversing) дерева чи "проходу" по дереву. При такому методі дослідження дерева кожен вузол відвідується тільки один раз, а повний обхід задає лінійне упорядкування вузлів, що дозволяє спростити алгоритм, тому як при цьому можна використовувати поняття "наступний" вузол, тобто вузол стоячий після даного при обраному порядку обходу.
Існує три принципово різні способи обходу дерева: у прямому порядку (), у центрованому порядку (), у зворотному порядку (). Розглянемо їх на прикладі нижчеподаного бінарного дерева.

[ Назад | Зміст]