Говорят, что две вершины соединены путем, если из первой вершины можно пройти по ребрам во вторую вершину. Путей между вершинами может быть несколько, поэтому они обозначаются перечислением вершин, которые встречаются на данном пути. Например, вершины A и C графа:
соединены путями ABC, AC, ADC, AEDC, ABDC, AEDBC.
Граф называется связным, если любые две его вершины соединены некоторым путем. Если в графе можно найти замкнутый путь, то граф называется циклическим, а сам замкнутый путь – циклом.
Связный граф, в котором нет циклов, называется деревом:
Одной из основных отличительных черт дерева является то, что в нем любые две вершины соединены единственным путем.
Дерево называется ориентированным, если на каждом его ребре указано направление. Следовательно, о каждой его вершине можно сказать, какие ребра в него входят, а какие из нее выходят. Точно так же о каждом ребре можно сказать, из какой вершины оно выходит, и в какую входит:
Из вершины A выходят три ребра – AB, AC и AЕ, в вершину D входит одно ребро – ED. Этот же граф можно описать следующей матрицей смежности:
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. Поэтому корень дерева – это узел, не имеющий предков, а листья – это узлы, не имеющие потомков.
Бинарные деревья – это полезная структура данных в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно решение из двух возможных (альтернатива), например, в алгоритмах сортировки, когда требуется сравнение каждого очередного элемента (числа, слова) со всеми предшествующими. Использование бинарных деревьев позволяет уменьшить количество таких сравнений: берется первый элемент и помещается в исходный узел бинарного дерева, который становится его корнем с пока пустыми левым и правым поддеревьями. Каждый последующий элемент сравнивается с элементом, стоящим в корне дерева: если новый элемент меньше его, то он образует левый узел следующего уровня, а если больше или равен – то правый. Так продолжается до тех пор, пока сортируемая последовательность элементов не закончится. При этом получается, что самый левый лист будет содержать минимальный элемент из введенной последовательности, а самый правый – максимальный. Любой левый узел будет содержать элемент, меньший, чем элемент в предшествующем узле, а правый – больший или равный элементу в предшествующем узле.
