16. Деревья. Поддеревья. Типы деревьев.

Дерево является одним из важных и интересных частных случаев графа, поэтому оно рассматривается отдельно от графов других видов.

Деревом называется орграф, для которого:

1) существует узел, в который не входит ни одной дуги (корень);

2) в каждую вершину, кроме корня, входит одна дуга.

Вершины дерева подразделяют на следующие три группы:

– корень – вершина, в которую не входит ни одной дуги;

– узлы – вершины, в которые входит одна дуга и выходит одна или более дуг;

– листья – вершины, в которые входит одна дуга и не выходит ни одной дуги.

Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина – корень, на втором – потомки корня, на третьем – потомки потомков корня и т. д.

Поддеревом называется вершина со всеми ее потомками.

По величине степени дерева часто различают два типа деревьев:

– двоичные – степень дерева не более двух;

– сильноветвящиеся – степень дерева произвольная.

Существует несколько способов обхода (просмотра) всех вершин дерева. Три наиболее часто используемых способа обхода называются (рис. 5):

– в прямом порядке;

– в обратном порядке;

– в симметричном (внутреннем) порядке.

Все три способа обхода рекурсивно можно определить следующим образом:

1) если дерево Tree является пустым деревом, то в список обхода заносится пустая запись;

2) если дерево Tree состоит из одной вершины, то в список обхода записывается эта вершина;

3) если Tree – дерево с корнем n и поддеревьями Tree1, Tree2, …,Treek, то:

Спецификация двоичных деревьев

Двоичные (бинарные) деревья – это деревья со степенью не более двух (рис. 6).

По степени вершин двоичные деревья бывают:

– строгие – вершины дерева имеют степень нуль (у листьев) или два (у узлов);

– нестрогие – вершины дерева имеют степень нуль (у листьев), один или два (у узлов).

17. Последовательный (линейный) поиск

Последовательный поиск – самый простой из известных. Суть его заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо).

Оформим описанный алгоритм в виде функции на Паскале.

function LineSearch(Key: ItemType, n: integer;

var A: array[1..n] of ItemType): boolean;

{Функция линейного поиска,}

{если элемент найден, то возвращает значение true, иначе – false}

var

i: integer;

begin

i := 1;

while (i <=n ) and (A[i]<>Key) do i := i + 1;

if A[i]=Key then LineSearch := true

else LineSearch := false;

end;

После завершения цикла требуется дополнительная проверка того, был ли найден искомый элемент, или «барьер».

Тогда функция поиска будет выглядеть так:

function LineSearchWithBarrier(Key: ItemType, n: integer;

var A: array[1..n+1] of ItemType): boolean;

{Функция линейного поиска с барьером,}

{если элемент найден, то возвращает значение true, иначе – false}

var

i: integer;

begin

I := 1;

A[n+1] := Key;

while A[i]<>Key do I := I + 1;

if I <= n then LineSearchWithBarrier := true

else LineSearchWithBarrier := false;

end;

Надо сказать, что хотя такая функция будет работать быстрее, но временная сложность алгоритма остается такой же – O(n). Гораздо больший интерес представляют методы, не только работающие быстро, но и реализующие алгоритмы с меньшей сложностью. Один из таких методов – бинарный поиск.