Структури даних, Детальна інформація

tmp := tmp^.next;

end;

writeln;

end;

Орієнтованим графом називається структура G = (V, E), де V – скінченна множина вершин, E – множина ребер, що задається як бінарне відношення на V, тобто E \xF0CD\xF020V \xF0B4\xF020V. Орієнтований граф називається орграфом. Граф може містити ребра - цикли, які сполучають вершину саму з собою. Про ребро (u, v) говорять, що воно виходить із вершини u та входить у вершину v.

В неорієнтованому графі множина ребер E складається із невпорядкованих пар вершин. Про ребро (u, v) неорієнтованого графу говорять, що воно інцидентно вершинам u та v. Якщо в графі G є ребро (u, v), то говорять, що вершина u суміжна з вершиною v. Для неорієнтованого графу відношення суміжності є симетричним.

Степенем вершини в неорієнтованому графі називається кількість інцидентних їй ребер. Для орієнтовних графів розрізняють вхідну та вихідну вершини; сума вхідних та вихідних степеней називається степенем вершини.

Деревом називається зв’язаний граф без циклів. Дерево являє собою скінченну множину елементів Т, які називаються вершинами. Якщо множина вершин Т порожня, то дерево називається порожнім; інакше в дереві повинна бути виділена одна вершина, яка називається коренем (якщо виділеної вершини не існує, то така структура називається деревом без виділеного кореня). Якщо (y, x) є останнім ребром на шляху з кореня до х, то y називається батьком, а x – сином. Корінь є єдиною вершиною, яка не має батька. Вершини, які мають одного спільного батька, називаються братами. Якщо кожна вершина T (батько) сполучається не більше ніж з k іншими вершинами T1, T2, ..., Tk (синами), то таке дерево називається k - арним. Якщо вершина не має синів, то вона називається листом; інакше вершина називається внутрішньою. Кількість синів у вершини дерева називається її степенем. Глибиною вершини називається довжина шляху від кореня до цієї вершини. Висотою дерева називається найбільша довжина від кореня до листа. Повним k - арним деревом називається k - арне дерево, в якому усі листи мають однакову глибину та усі внутрішні вершини мають однаковий степінь.

Властивість дерев. Нехай G = (V, E) – неорієнтований граф. Тоді наступні твердження еквівалентні:

G є деревом без виділеного кореня;

для довільних двох вершин G існує єдиний простий шлях, що їх сполучає;

граф G є зв’язним, але не залишається таким при вилученні хоча б одного ребра;

граф G є зв’язним і |E| = |V| - 1;

граф G є ациклічним і |E| = |V| - 1;

граф G є ациклічним, але додання довільного ребра породжує цикл.

У двійковому дереві кожна вершина може мати не більше двох синів (лівий та правий сини). Кожна вершина окрім кореня, має батька. При представленні двійкового дерева за допомогою вказівників кожна вершина містить ключ Val, вказівники на лівого Left та правого Right синів, а також на батька Up. Якщо сина або батька (для кореня) не існує, то відповідний вказівник містить NIL.

Ключі у двійковому дереві містяться у відповідності до властивості впорядкованості:

Нехай x – довільна вершина двійкового дерева. Якщо вершина y знаходиться в лівому піддереві вершини x, то x.Val > y.Val. Якщо вершина y знаходиться в правому піддереві вершини x, то x.Val < y.Val.

Нехай PTree – вказівник на структуру типу бінарне дерево.

PTree = ^Tree;

Tree = object

Val: integer; /* значення вершини */

Left: PTree; /* вказівник на лівого сина */

Right: PTree; /* вказівние на правого сина */

Up: PTree; /* вказівник на батька */

end;

Об’єкт дерево має наступні методи:

INSERT – вставка елемента до дерева;

DELETE – вилучення елемента з дерева;

FIND – пошук елемента в дереві;