Page 45 - 6110

(праве та ліве), що не перетинаються, або є пустою множиною
вершин (на відміну від звичайного дерева, яке не може бути
пустим).
Важливими операціями над деревами є:
- обхід вершин в різному порядку;
- перенумерація вершин;
- пошук елемента;
- додавання елемента у визначене місце в дереві;
- видалення елемента;
- видалення цілого фрагмента дерева;
- додавання цілого фрагмента дерева;
- трансформації (повороти) фрагментів дерева;
- знаходження кореня для будь-якої вершини.
Найбільшого розповсюдження ці структури даних набули в тих
задачах, де необхідне маніпулювання з ієрархічними даними,
ефективний пошук в даних, їх структуроване зберігання та
модифікація.

11.1 Бінарне дерево
В програмуванні бінарне дерево – це дерево структури даних, в
якому кожна вершина має не більше двох дітей. Зазвичай такі діти
називаються правим та лівим. На базі бінарних дерев будуються
такі структури, як бінарні дерева пошуку та бінарні купи.
На рис.11.1 показана узагальнена структура бінарного дерева.

Рисунок 11.1 – Узагальнена структура бінарного дерева

Різновиди бінарних дерев:
- бінарне дерево (кореневе дерево, в якому кожна вершина має
не більше двох дітей);
- повне (закінчене) бінарне дерево (бінарне дерево, в якому
кожна вершина має нуль або двох дітей);
44