Абстрактный метод ничего не делает, но определяет параметры и возвращаемое значение.

Назначение абстрактных методов:

1. описание абстракции, которая не в более конкретизированном виде не может быть реализована;

2. формальное (без реализации — есть или нет) удовлетворение требований о наличии статических методов при обращении к ним для прохождения проверки компилятора статической типизации, когда реализация их будет определена динамически (в процессе работы программы).

Иногда возникает необходимость определить класс, который не предполагает создания конкретных объектов. Например, класс фигуры. В реальности есть конкретные фигуры: квадрат, прямоугольник, треугольник, круг и так далее. Однако абстрактной фигуры самой по себе не существует. В то же время может потребоваться определить для всех фигур какой-то общий класс, который будет содержать общую для всех функциональность. И для описания подобных сущностей используются абстрактные классы.

Абстрактные классы - это классы, которые содержат или наследуют без переопределения хотя бы одну чистую виртуальную функцию. Абстрактный класс определяет интерфейс для переопределения производными классами.

Что такое чистые виртуальные функции (pure virtual functions)? Это функции, которые не имеют определения. Чтобы определить виртуальную функцию как чистую, ее объявление завершается значением "=0". Например, определим абстрактный класс, который представляет геометрическую фигуру:

Класс Figure является абстрактным, потому он содержит как минимум одну чистую виртуальную функцию. А в данном случае даже три таких функции. И ни одна из функций не имеет никакой реализации. Реализацию должны определять классы-наследники.

При этом мы не можем создать объект абстрактного класса.

Стоит отметить, что абстрактный класс может определять и обычные функции, и переменные, может иметь несколько конструкторов, но при этом нельзя создавать объекты этого абстрактного класса.

23. Бинарные деревья, основные понятия: дерево, корень, предок, потомок, лист, высота дерева, упорядоченное дерево.

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

- узел, называемый корнем;

- двоичное дерево, называемое левым поддеревом;

- двоичное дерево, называемое правым поддеревом.

Таким образом, двоичное дерево — это рекурсивная структура данных.

Каждый узел двоичного дерева можно представить в виде структуры данных, состоящей из следующих полей:

- данные, обладающие ключом, по которому их можно идентифицировать;

- указатель на левое поддерево;

- указатель на правое поддерево;

- указатель на родителя (необязательное поле).

Значение ключа уникально для каждого узла.

Узел, находящийся на самом верхнем уровне (не являющийся чьим-либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.

Каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

Терминология

Древовидная структура характеризуется множеством узлов (nodes), происходящих от единственного начального узла, называемого корнем (root). На Рис. 3 корнем является узел А. В терминах генеалогического дерева узел можно считать родителем (parent), указывающим на 0, 1 или более узлов, называемых сыновьями (children). Например, узел В является родителем сыновей E и F. Родитель узла H - узел D. Дерево может представлять несколько поколений семьи. Сыновья узла и сыновья их сыновей называются потомками (descendants), а родители и прародители – предками (ancestors) этого узла. Например, узлы E, F, I, J – потомки узла B. Каждый некорневой узел имеет только одного родителя, и каждый родитель имеет 0 или более сыновей. Узел, не имеющий детей (E, G, H, I, J), называется листом (leaf).

Каждый узел дерева является корнем поддерева (subtree), которое определяется данным узлом и всеми потомками этого узла. Узел F есть корень поддерева, содержащего узлы F, I и J. Узел G является корнем поддерева без потомков. Это определение позволяет говорить, что узел A есть корень поддерева, которое само оказывается деревом.

Рис.3.

Переход от родительского узла к дочернему и к другим потомкам осуществляется вдоль пути (path). Например, на Рис. 4 путь от корня A к узлу F проходит от A к B и от B к F. Тот факт, что каждый некорневой узел имеет единственного родителя, гарантирует, что существует единственный путь из любого узла к его потомкам. Длина пути от корня к этому узлу есть уровень узла. Уровень корня равен 0. Каждый сын корня является узлом 1-го уровня, следующее поколение – узлами 2-го уровня и т.д.

Глубина (depth) дерева есть его максимальный уровень. Понятие глубины также может быть описано в терминах пути. Глубина дерева есть длина самого длинного пути от корня до узла.

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