Деревья

В ряде задач линейной структуры данных, какой является динамический массив, оказывается недостаточно. Представьте себе хотя бы разветвленную структуру каталогов на жестком диске компьютера. А как хранить в памяти генеалогическое дерево? данные о структуре сложного изделия, содержащего сотни узлов и подузлов? календарь игр между командами на чемпионате мира? Таким образом, существует необходимость в древовидной структуре для хранения информации (Рис. 10.6).

Рис. 14.6. Дерево.

Кстати, компьютерное дерево, в отличие от нормального, растет корнем вверх…

В большинстве задач из каждого узла дерева выходят ровно две ветки. Такие деревья называются бинарными(Рис. 10.7).

Рис. 14.7. Бинарное дерево.

Структура данных для представления вершины бинарного дерева должна включать не одно, а два поля с указателями – для двух выходящих из вершины веток:

TYPE Ptr =^Tnode;
Tnode = RECORD
data: STRING:
left, right: Ptr
END;

Еще лучше, если двоичное дерево будет упорядоченным. В упорядоченном дереве значение левой вершины всегда меньше или равно значения правой вершины.

Важный вопрос – алгоритм поиска нужного значения в дереве. Дерево ветвится и, казалось бы, трудно написать алгоритм, который бы перебирал все его вершины. Однако существует простой прием, упрощающий обход дерева. К дереву добавляется дополнительная вершина, называемая барьером и все конечные элементы исходного дерева "замыкаются" на вершину–барьер (Рис. 10.8).

Рис. 14.8. Добавление барьера к двоичному дереву.

Тогда функция поиска значения в упорядоченном двоичном дереве выглядит следующим образом:

FUNCTION Locate(x:WORD; t:Ptr):Ptr;

{ x – искомое значение; t – указатель на корень дерева }
BEGIN
WHILE (t<>NIL) AND (t^.data<>x) DO

IF t^.data<x THEN
t := t^.right
ELSE
t := t^.left;
Locate :=t
END.