A B C D E

A

B

C

D

E

В незаполненных ячейках должны стоять нули – связи между соответствующими вершинами нет.

Наименование строки – это имя вершины-источника, из которой ребро выходит, а столбца – вершины-приемника, в которую входит. Таким образом, количество ненулевых элементов в матрице смежности ориентированного графа равно количеству ребер в нем.

Среди деревьев наиболее широкое распространение в программировании получили бинарные деревья.

Бинарное дерево – это такое ориентированное дерево, в котором:

· из каждой вершины исходит не более двух ребер,

· имеется только одна вершина – корень дерева, в которую не входит ни одного ребра,

· в каждую вершину, кроме корня, входит только одно ребро.

Бинарные деревья обычно изображаются корнем вверх:

В этом бинарном дереве вершина A является корнем.

Для ребер бинарного дерева, выходящих из одной вершины, имеются две возможности – быть направленными влево-вниз или вправо-вниз: ребро BD направлено влево-вниз, а ребро DH – вправо-вниз.

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

Узел, не являющийся корнем ни одного поддерева, называется листом. В вышеприведенном дереве листьями являются узлы G, H, K. Характеристикой каждого узла является его уровень, определяемый следующим образом: корень дерева имеет нулевой уровень, уровень любого другого узла на единицу больше уровня узла-предшественника: узлы B,C имеют уровень 1, узлы D, E, F – уровень 2, узлы G,H,K (узлы) – уровень 3.

Глубина бинарного дерева – это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева.

Среди узлов различают предков и потомков: узел A является предком для узлов B и C, узлы G и H – потомками узла D. Поэтому корень дерева – это узел, не имеющий предков, а листья – это узлы, не имеющие потомков.

Бинарные деревья – это полезная структура данных в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно решение из двух возможных (альтернатива), например, в алгоритмах сортировки, когда требуется сравнение каждого очередного элемента (числа, слова) со всеми предшествующими. Использование бинарных деревьев позволяет уменьшить количество таких сравнений: берется первый элемент и помещается в исходный узел бинарного дерева, который становится его корнем с пока пустыми левым и правым поддеревьями. Каждый последующий элемент сравнивается с элементом, стоящим в корне дерева: если новый элемент меньше его, то он образует левый узел следующего уровня, а сели больше или равен – то правый. Так продолжается до тех пор, пока сортируемая последовательность элементов не закончится. При этом получается, что самый левый лист будет содержать минимальный элемент из введенной последовательности, а самый правый – максимальный. Любой левый узел будет содержать элемент, меньший, чем элемент в предшествующем узле, а правый – больший или равный элементу в предшествующем узле.

Например, следующая последовательность чисел:

14 15 4 9 7 18 3 5 16 4 20 17 9 14 5

образует бинарное дерево:

В этом дереве самый левый лист содержит наименьшее число 4, а самый правый – наибольшее 20.

Если сейчас просмотреть это дерево в так называемом симметричном порядке – слева направо: левое поддерево - его корень – правое поддерево, то получим отсортированную последовательность:

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20

Бинарное дерево можно представить связным списком, в котором каждое ссылочное поле каждого элемента (узла) должно содержать значения двух ссылок – на элемент (узел) слева внизу и элемент (узел) справа внизу. Если один из узлов отсутствует, то ссылка на него равна Nil. Самые нижние элементы списка (листья) имеют ссылки со значениями Nil:

Data: Integer; информационное поле

Left, Right: TRebro; ссылочные поля

End;

Var root, q, v: TRebro;

Здесь объектами типа TUzel являются записи, в которых каждое ссылочное поле Left или Right равно либо Nil, либо ссылке на конкретную ячейку памяти компьютера, отведенную для объекта типа TUzel.

Дерево можно представить в виде множества объектов типа TUzel, связанных ссылками. Сами эти объекты соответствуют узлам дерева, а ссылки – его ребрам. Если при этом поле Left (Right) некоторого узла равно Nil, то это значит, что в дереве из этого узла не исходит ребро, направленное влево-вниз (вправо-вниз). Переход от вышестоящего к нижестоящему узлу совершается, как и в связных списках, присваиванием ссылочной переменной значения ее ссылочного поля, левого или правого. Этим способом можно просмотреть все узлы дерева сверху вниз. Включение нового узла в дерево осуществляется, как и включение нового элемента в связный список, изменением значений ссылочных полей соответствующих узлов. Вместе с каждым деревом рассматривается переменная, значением которой является ссылка на корень дерева (в нашем примере это root). Если в дереве нет ни одного узла, то значение этой переменной равно Nil.

Корень дерева можно создать, например, так: