Тема: Графи і дерева
Поняття про графи і дерева
Зображення таблиці двійковим деревом
Шукання запису в дереві
Поняття про графи і дерева
Графом називають скінченну множину точок - вершин графа, для деяких пар якої налагоджені зв'язки - ребра графа. Розглянемо використання графів для зображення динамічних структур. Нехай є деяка структура, що складається з записів, пов'язаних між собою системою вказівок, причому кожен запис може містити вказівки на декілька інших записів. Тепер зіставимо вершини графа із записами, а ребра - з вказівками, поставивши у відповідність цій структурі граф. Ребра такого графа будуть характеризуватися напрямами, що відповідають тим вказівкам, які вони відображають. Такий граф називається орієнтованим. З будь-якого графа завжди можна виділити дерево - сукупність (підмножину) ребер графа, що пов'язує всі вершини, однак не утворює замкнутих контурів (циклів). Дерева можна вибирати багатьма способами.
Для зображення таблиці використовуватимемо двійкові дерева. Двійкове дерево характеризується тим, що з кожної вершини виходить не більше двох стрілок, і є одна вершина - корінь дерева, в який не напрямлена жодна стрілка. У всі ж інші вершини напрямлено по одній стрілці. Приклад двійкового дерева показаний на рис. 1.
51
35 84
96
32 65
102
62 91
Рис. 1. Двійкове дерево.
Ліва і права стрілки не є взаємозамінними, тому наступні два двійкові дерева різні (рис. 2).
Рис. 2. Незбіжні елементи двійкового дерева.
Під час формування дерева записів ліва стрілка відповідає вказівці на запис з меншим ключем, права - на запис з більшим ключем.
1. Зображення таблиці двійковим деревом. У цьому випадку кожна вершина дерева - це запис, що містить чотири поля: ключ запису, вказівку на ліву вершину, вказівку на праву вершину і вказівку на текст запису, який зберігається окремо (як прийнято для таблиць).
Двійкове дерево наведемо у вигляді таких описів типу:
type
Tekst={iм'я або задання типу запису з текстом};
RT=^Tekst;
L=^Node; Node=record
Key: Char;
Left, Right: L;
TXT: RT;
end;
2. Шукання запису в дереві. Опишемо логічну функцію шукання запису в дереві за ключем з побічним ефектом - вказівкою на вершину, що містить відшуканий запис. Формальні параметри функції: k - ключ; Tree - вказівка на дерево, у якому ведуть шукання; Res - вказівна змінна, що містить вказівку на знайдений вузол.
program Form9;
type
Tekst=Char;
RT=^Tekst;
L=^Node;
Node=record
Key: Char;
Left,
Right: L;
TXT: RT;
end;
function SeekTree(k: Char; Tree: L; var Res: L): Boolean;
var p, q: L;
b: Boolean;
begin
b:=false;
p:=Tree;
If p<>nil then repeat
if p^.key=k then b:=True else
if p^.key<k then p:=p^.Right else p:=p^.Left
until b or (p=nil);
SeekTree:=b;
Res:=p;
end;
begin
end.
Наведена функція побудована на ітеративному методі.