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. Поэтому корень дерева – это узел, не имеющий предков, а листья – это узлы, не имеющие потомков.

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

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

Дата добавления: 2014-01-06