Деревом називається динамічна структура, у якій кожен вузол містить не один, а декілька вказівників на декілька інших вузлів.

Кореневий вузол (корінь дерева) – це самий верхній вузол (вузол a – кореневий) . Якщо з деякого вузла (наприклад, вузла а) вказівники вказують на інші вузли (в нашому випадку на вузли b та c), то такий вузол називають предком. Вузли ж на які вказують вказівники від предка називаються потомками.

Все сказане вище ілюструє малюнок 1, якщо його розглянути то можна зробити висновки про те, що:

· Лівий потомок вузла а – вузол b

· Правий потомок – вузол c.

· Вузли b та c мають спільного предка – вузол а

Якщо вузол не має потомків, то такий вузол називають листком дерева, тому згідно малюнка вершини d, g та f – є листками.

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

2.1. РЕАЛІЗАЦІЯ БІНАРНОГО ДЕРЕВА ЗА ДОПОМОГОЮ ДИНАМІЧНИХ ЗМІННИХ

Розглянемо динамічну змінну b, що має таку структуру, як показано на малюнку 2. А саме, змінна b є записам з 5 полів:

Parent –вказівник на предка

Left – вказівник на лівого потомка

Right – вказівник на правого потомка

Data – поле даних (наприклад, прізвище)

Key – ключ (цілочисельне значення), по якому ідентифікується елемент.

Тип такої динамічної змінної виглядає наступнич чином:

type

BinarTree=^node;

node=record

key:integer;

data:string;

left,right,
parent:BinarTree;

end;

Сформуємо дерево керуючись таким принципом: ключ кожного лівого потомка менший за ключ предка, а ключ правого потомка – більший або рівний ключа предка.

Наприклад, бінарне дерево з трьох вузлів (Іванов (ключ=5), Петров (ключ=3) та Сидоров (ключ=8)) має вигляд як показано на мал.3. Добавимо в дерево елемент Ільїн з ключем 6. Цей елемент буде лівим потомком елемента Сидоров (так як 6>5 та 6<8). Якби ключ елемента Ільїн був рівний 4, то він був би правим потомком елемента Петров (бо 4<5 та 4>3)

При вставці кожного наступного елемента (нехай вказівник b_new вказує на цей елемент) в дерево (b вказує на корінь цього дерева), ми повинні спочатку знайти листок (нехай на нього вказує вказівник b_parent), який буде предком елемента що вставляєть.

Для пошуку такого листка використаємо деякий проміжний вказівник b_buf, який спочатку буде вказувати на корінь дерева b, а потім крок за кроком приймати значення b_buf^.left або b_buf^.right в залежності від значенні ключа елемента що вставляється (b_new) до тих пір, поки не дойде до листка дерева.

Програмний код пошуку елемента b_parent.

b_buf:=b;