Page 46 - 6110

- ідеальне бінарне дерево – це повне бінарне дерево, в якому
листя (вершини без дітей) лежать на однаковій глибині (відстані від
кореня).
n
Бінарне дерево на кожному n-му рівні має від 1 до 2 вершин.
Часто виникає необхідність обійти усі вершини дерева для
аналізу інформації, що в них знаходиться. Існують декілька
порядків такого обходу, кожний з яких має певні властивості,
важливі в тих чи інших алгоритмах:
- прямий (preorder);
- центрований (inorder);
- зворотній (postorder).
Реалізація бінарного дерева показана на рис11.2. Кожна
вершина містить вказівники на праву та ліву дитину (left та right).

Рисунок 11.2 – Реалізація бінарного дерева

Існують декілька варіантів конструювання бінарних дерев в
залежності від задач, які вирішуються цими структурами та
можливостей тої чи іншої мови програмування. Реалізація з
використанням вказівників передбачає зберігання в кожній вершині
дерева x разом з даними двох полів з вказівниками (правим та
лівим) right[x] та left[x] на відповідних дітей цієї вершини
(рис.11.3).

45