3.3. Деревья и ордеревья.
1
)Существует
особая вершина (корень дерева), в которую
не входит не одна дуга.
2) во все остальные вершины входит одна единственная дуга
Вершины, из которых ни выходят дуги (не имеющие потомков) называются висячим.
Существует классификация вершин дерева по их расположению от корня.
Если вершину отделяет от корня k дуг, то говорят, что это вершина k-го уровня (яруса). Общее число уровней называется глубиной дерева (иногда высотой)
Опр. Связный граф, не имеющий цикла, называется деревом.
Дерево Не дерево
Понятие корня у дерева отсутствует
Существуют и другие определения дерева.
Теорема: Следующие свойства графа эквивалентны.
Граф является деревом.
Граф связан и Р=В-1
Граф не имеет циклов и Р=В-1
Граф связан, но утрачивает связность при удалении какого либо ребра (вершины остаются)
Граф не имеет циклов, но при добавлении любого нового ребра (но не вершин) циклы появляются.
Предположение: Если в орграфе удалить наконечники стрелок, то получится дерево.
Доказательство.
Так как во все вершины ордерева, кроме корня, входит единственная дуга, то число дуг равно В-1. Так как дуги превращаются в ребра, то теперь Р=В-1.
Так как каждая вершина дерева была соединен с корнем, то получившийся после ликвидации стрелок граф будет связный.
Согласно пункту 2 теоремы, полученный граф является деревом.
Из дерева можно получить ордерево, но уже многими способами.
Возникает впечатление, что у дерева все вершины как бы равноправны, но это не совсем так.
У дерева тоже есть понятие висячие вершины, вершина степени 1 называется висячей.
Классификация вершин дерева.
Опр. Расстояние от данной вершина А дерева до наиболее удаленной от нее вершины называется эксцентриситетом вершины А.
Радиус равен 3
Центр из 2 вершин
Наименьший из эксцентриситетов вершин является радиусом дерева, а множество вершин с этим наименьшим эксцентриситетом называется центром дерева.
Доказано, что центр дерева всегда состоит либо из одной вершины, либо из 2 смежных вершин.
3.4. Бинарные деревья и их представление в памяти.
Опр. Если каждая вершина ордерева имеет не более 2-х потомков, то дерево называют бинарным (двоичным).
Ясно, что возникают понятия левого и правого потомка (левого и правого поддерева)
П
рефиксный
код бинарного ордерева.
Каждой вершине ордерева (кроме корня (мы сопоставим двоичное число. Левому потомку корня мы припишем 0, а правому 1, потомкам 00 и 01 соответственно и т.д.
Достаточно хранить в памяти компьютера не все построенные числа, а только расположенные на висячих вершинах, слева направо.
{000, 010, 011, 10, 110, 1110, 1111} – это и есть префиксный вид бинарного дерева.
Он определяет ордерево однозначною по нему можно восстановить бинарное дерево.
Каждое их чисел В в перфективном коде позволяет однозначно восстановить весь путь от корня до висячей вершины, тем самым все ордерево.
Заметим, что для больших деревьев префексивный код очень объемен. Если у бинарного ордерева 10 уровней, то возникает 10-битовые двоичные числа, в количестве до 1024. Поэтому пробуем получить более компактные способы представление ордеревьев и деревьев в памяти, заодно отказавшись от требования бинарности.
Замечание: аналогично бинарным 3-арные, n-арные деревья, но для них все гораздо сложнее. Желательно иметь более компактные способы кодирования в памяти, пригодные не только для бинарных, но и для любых деревьев ордеревьев.