Бинарные деревья

Самым наглядным способом представления информации является ее представление рисунками или графиками. Поэтому при решении многих математических задач используются специальные рисунки (схемы), называемые графами.

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

Термин графвпервые появился в работах венгерского математикаД.Кенигав 1936 году, хотя ряд задач по теории графов был решен ещеЛ.ЭйлервXVIIIвеке.

Примером графа может служить схема линии метрополитена, карта автомобильных или железных дорог. Эти дороги можно рассматривать как ребра, соединяющие города или станции – вершины такого графа.

Вершины графа обычно нумеруются или обозначаются прописными латинскими буквами: A. B, C, …Любой граф можно описать или задать перечислением вершин и ребер. Наиболее удобный способ такого задания – с помощьюматрицы смежности, в которой строки и столбцы соответствуют вершинам графа, а значения элементов – длине ребер, соединяющих эти вершины. Если длина ребер не задается, то наличие ребра обозначается единицей, а его отсутствие – нулем.

Например, граф:

задается матрицей смежности:

0	1	1	0
1	0	0	1
1	0	0	1
0	1	1	0

A B C D

A

B

C

D

Как видно, это симметричнаяматрица.

Граф называется ориентированным(орграф), если на каждом его ребре указано направление, то есть о каждой его вершине можно сказать, какие ребра из нее выходят, а какие входят:

Для этого ориентированного графа матрица смежности имеет вид:

A B C D

0	1	1	0
0	0	0	1
0	0	0	1
0	0	1	0

A

B

C

D

Говорят, что две вершины соединены путем, если из первой вершины можно пройти по ребрам во вторую вершину. Путей между вершинами может быть несколько, поэтому они обозначаются перечислением вершин, которые встречаются на данном пути. Например, вершиныA иC графа:

соединены путями ABC, AC, ADC, AEDC, ABDC, AEDBC.

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

Связный граф, в котором нет циклов, называется деревом:

Одной из основных отличительных черт дерева является то, что в нем любые две вершины соединены единственнымпутем.

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

Из вершины Aвыходят три ребра –AB,ACиAЕ, в вершинуDвходит одно ребро –ED. Этот же граф можно описать следующей матрицей смежности:

A B C D E

	1	1		1
			1

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:

Если информационные поля элементов дерева являются данными целого типа, то дерево можно описать, например, следующим образом:

Type TRebro = ^TUzel;

TUzel = Record

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

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

End;