Деревья

Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).

Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчиненности: директор — заместители директора — учителя — ученики.

Иерархическую структуру имеют системы, элементы которых связаны отношением «входит в состав».

На рис. 2.32 изображен граф иерархической системы, представляющий состав прикладного программного обеспечения (ПО) компьютера.

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

Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порожденных вершин, называются листьями.

Древовидными являются схемы отношений «является разновидностью», используемые для наглядного представления классификации объектов (рис. 2.33).

Иерархию легко изобразить «лесенкой» — в виде многоуровневого списка. Объекты одного уровня иерархии располагаются на одном уровне в списке. Чем ниже уровень иерархии, тем правее находится соответствующий уровень списка:
Рептилии
Черепахи
Крокодилы
Клювоголовые
Чешуйчатые
Ящерицы
Змеи

Родственные связи между членами семьи удобно изображать с помощью схемы, называемой генеалогическим или родословным деревом. На рисунке 2.34 показана родословная Романовых. Здесь корень дерева находится снизу. Изображать дерево отношений можно в любом направлении — это дело вкуса разработчика модели.

По иерархическому принципу организована система хранения файлов во внешней памяти.

Вы знаете, что по определенному признаку (принадлежность, назначение, содержимое, время создания и т. д.) файлы целесообразно объединять в папки. Папки, в свою очередь, могут вкладываться в другие папки и т. д. (рис. 2.35).

Главная (корневая) вершина этой иерархии соответствует определённому устройству внешней памяти:

Для того чтобы найти файл в иерархической файловой структуре, можно указать путь к файлу. В путь к файлу входят записываемые через разделитель «\» логическое имя диска и последовательность имен вложенных друг в друга папок, в последней из которых находится нужный файл.

Например, пути к файлам на рис. 2.35 можно записать так:

С:\Проекты\История\
C:\Проекты\Информатика\
С:\Рисунки\

Путь к файлу вместе с именем файла называют полным именем файла.

Примеры полных имен файлов:

С:\Проекты\История\Эпоха\Возрождения.doc С:\Проекты\Информатика\Интернет.doc С:\Проекты\Информатика\Компьютерные вирусы.doc
С:\Рисунки\Закат.jpg
С:\Рисунки\Зимa.jpg

Операционная система позволяет получить на экране компьютера изображение файловой системы в виде дерева (рис. 2.36).